CSE105F24

Dates: 9/23/24 - 10/6/24
Welcome! Please take our pre-class survey on Canvas. See you Friday 9am in Catalyst 125. Notes for class are linked below: we recommend attending class in person each day (if you can). We'll be working directly on quiz and homework questions in many classes to help you get started with problem solving. Discussion sections will include a review of the lecture material for the week and example problems. They are scheduled for Wednesdays at 4pm in WLH 2001.

Dates: 10/7/24 - 10/13/24.

Dates: 10/14/24 - 10/20/24

Dates: 10/21/24 - 10/27/24

Dates: 10/28/24 - 11/3/24.

Dates: 11/4/24 - 11/10/24. Test 1 in CBTF this week. The test covers material in Weeks 1 through 4 and Monday of Week 5. In particular, you should make sure you can:

• Distinguish between alphabet, language, sets, and strings
• Translate a decision problem to a set of strings coding the problem
• Use regular expressions and relate them to languages and automata
• Write and debug regular expressions using correct syntax
• Determine if a given string is in the language described by a regular expression
• Use precise notation to formally define the state diagram of DFA, NFA and use clear English to describe computations of DFA, NFA informally.
• State the formal definition of (deterministic) finite automata
• Trace the computation of a finite automaton on a given string using its state diagram
• Translate between a state diagram and a formal definition
• Determine if a given string is in the language described by a finite automaton
• Design and analyze an automaton that recognizes a given language
• Specify a general construction for DFA based on parameters
• Design and analyze general constructions for DFA
• Motivate the use of nondeterminism
• Trace the computation(s) of a nondeterministic finite automaton
• Determine the language recognized by a given NFA
• Design and analyze general constructions for NFA
• Choose between multiple models to prove that a language is regular
• Explain nondeterminism and describe tools for simulating it with deterministic computation.
• Find equivalent DFA for a given NFA
• Convert between regular expressions and automata
• Classify the computational complexity of a set of strings by determining whether it is regular
• Explain the limits of the class of regular languages
• Identify some nonregular sets
• Use the pumping lemma to prove that a given language is not regular.
• Justify why the Pumping Lemma is true
• Apply the Pumping Lemma in proofs of nonregularity
• Use precise notation to formally define the state diagram of PDA and use clear English to describe computations of PDA informally.
• Define push-down automata informally and formally
• Trace the computation of a push-down automaton
• Determine the language recognized by a given PDA
• Design push-down automata to recognize specific languages
• Determine whether a language is recognizable by a (D or N) FA and/or a PDA
• Use context-free grammars and relate them to languages and pushdown automata.
• Identify the components of a formal definition of a context-free grammar (CFG)
• Derive strings in the language of a given CFG
• Determine the language of a given CFG
• Design a CFG generating a given language

To study for the exam, we recommend reviewing class notes (e.g. annotations linked on the class website, podcast, supplementary video from the class website), reviewing homework (and its posted sample solutions), and in particular *working examples* (extra examples in lecture notes, textbook examples listed in hw, review quizze, discussion examples) and getting feedback (office hours and Piazza).

Dates: 11/11/24 - 11/17/24. No class on Monday (in observance of Veterans Day). Asynchronous class on Wednesday: please read Chapter 4 in the textbook and watch the supplementary videos linked below and post questions on Piazza. We'll be back to synchronous, in-person class on Friday.

Dates: 11/18/24 - 11/24/24

Dates: 11/25/24 - 12/1/24. Test 2 in CBTF this week. No class on Friday in observance of Thanksgiving. The test covers material in Weeks 5 through 8 and Monday of Week 9. In particular, you should make sure you can:

• State the definition of the class of context-free languages
• Explain the limits of the class of context-free languages
• Identify some context-free sets and some non-context-free sets
• Use general constructions to prove closure properties of the class of context-free langugages.
• Use counterexamples to prove non-closure properties of the class of context-free langugages.
• Motivate the definition of a Turing machine
• Trace the computation of a Turing machine on given input
• Describe the language recognized by a Turing machine
• Determine if a Turing machine is a decider
• Given an implementation-level description of a Turing machine
• Use high-level descriptions to define and trace Turing machines
• Apply dovetailing in high-level definitions of machines
• State the definition of the class of recognizable languages
• State the definition of the class of decidable languages
• State the definition of the class of co-recognizable languages
• Apply a general construction to create a new Turing machine from an example one.
• Formalize a general construction from an informal description of it.
• Use general constructions to prove closure properties of the class of decidable langugages.
• Use general constructions to prove closure properties of the class of recognizable langugages.
• Give examples of sets that are decidable.
• Give examples of sets that are recognizable.
• Connect languages and computational problems
• Describe and use the encoding of objects as inputs to Turing machines
• Trace high-level descriptions of algorithms for computational problems
• Describe common computational problems with respect to DFA, NFA, regular expressions, PDA, and context-free grammars.
• Give high-level descriptions of Turing machines that decide common computational problems with respect to DFA, NFA, regular expressions, PDA, and context-free grammars.
• Define and explain the definitions of computational problems, including the acceptance, language emptiness, and language equality problems for DFA, NFA, REX, CFG, PDA, and TM, as well as the halting problem for TM.
• Trace the argument that proves the acceptance problem for Turing machines is undecidable and explain why it works.
• Define computable functions, and use them to give mapping reductions between computational problems
• Build and analyze mapping reductions between computational problems
• Deduce the decidability or undecidability of a computational problem given mapping reductions between it and other computational problems, or explain when this is not possible.
• State, prove, and use theorems relating decidability, recognizability, and co-recognizability.
• Prove that a language is decidable or recognizable by defining and analyzing a Turing machines with appropriate properties.

To study for the exam, we recommend reviewing class notes (e.g. annotations linked on the class website, podcast, supplementary video from the class website), reviewing homework (and its posted sample solutions), and in particular *working examples* (extra examples in lecture notes, textbook examples listed in hw, review quizzes, discussion examples) and getting feedback (office hours and Piazza).

Dates: 12/2/24 - 12/8/24.

Project due