4003-700 Homework, Quizzes, and Reading

• Monday, November 26
  • Buy the book!
  • Read ahead (optional): Chapter 0.

• Wednesday, November 28
  • Read: Chapter 0, notes from last class.
  • Quiz 1: There will be a short quiz at the start of class on Section 0.2, except for the 1-page "Strings and Languages" subsection. You will need to show basic discrete math reading/writing/reasoning skills.
  • Read ahead (optional): p44/45 from "The Regular Operations" to the end of Example 1.24, start of Chapter 1.

• Monday, December 3
  • Read: Chapter 1, pp 31-40 and notes from last class.
  • If you did badly on quiz 1, you should work hard on your discrete math skills.
  • To do: Try to draw the state diagrams for the final two examples of slide 5.
  • Quiz 2: There will be a short quiz at the start of class on "Strings and Languages": See the 1-page "Strings and Languages" subsection of Section 0.2, p44/45 from "The Regular Operations" to the end of Example 1.24, slides 7-14 from the notes on Chapter 0, and what we did in class on this topic.
  • Look over Homework 1.
  • Read ahead (optional): More of Chapter 1.

• Wednesday, December 5
  • Read: Section 1.1 and related notes.
  • Quiz 3: There will be a short quiz at the start of class on finite automata (Sipser, pp. 31-43 and related notes).
  • Homework 1, due 12/5 2:00pm.

• Monday, December 10
  • Read: Section 1.1, page 45-47, and notes on closure properties.
  • Quiz 4: There will be a short quiz at the start of class on the reading assignment (i.e., page 45-47 from Section 1.1 and notes on closure properties).
  • Look over Homework 2.
  • If you have never seen NFAs, read Section 2.1, up to page 54.

• Wednesday, December 12
  • Read: Section 1.1, pages 47-58, notes.
  • Quiz 5: There will be a short quiz at the start of class in NFAs (Section 2.1, pages 47-54 and notes on this topic).
  • Homework 2, due 12/12 2:00pm.
  • Read ahead (optional): Rest of Section 1.2.

• Monday, December 17
  • Read: Section 1.2, start of Section 1.3, and notes.
  • Finish the last two regular expression examples from the last slide from last class and answer the question on that slide.
  • Quiz 6: There will be a short quiz at the start of class on Section 1.2 and related notes.
  • Look over Homework 3. Note: In question 5, your regular expressions should not be overly complicated.
  • Read ahead (optional): Rest of Section 1.3.

• Wednesday, December 19
  • Read: Section 1.3 and notes.
  • Quiz 7: There will be a short quiz at the start of class on regular expressions (Section 1.3, pages 63-66) and related notes.
  • Homework 3, due 12/19 2:00pm. Note: In question 5, your regular expressions should not be overly complicated.

• Monday, January 7
  • Read: notes from last class, Algorithm from Problem 7.42.
  • Quiz 8: There will be a short quiz at the start of class on the notes from last class, slides 1-6.
  • Look over Homework 4.
  • Read ahead (optional): Section 1.4.

• Wednesday, January 9
  • Read: Section 1.4.
  • Quiz 9: There will be a short quiz at the start of class on minimizing DFAs.
  • Homework 4, due 1/9 2:00pm.

• Monday, January 14
  • Read: Start of Chapter 2.
  • Quiz 10: There will be a short quiz at the start of class on Section 1.4.

• Wednesday, January 16
  • Midterm!

• Monday, January 21
  • Read: Section 2.1. If you have never seen PDAs, skim the start of Section 2.2.
  • Quiz 11: There will be a short quiz at the start of class on Section 2.1 (except the Chomsky normal form subsection).

• Wednesday, January 23
  • Read: Section 2.2 until page 116,
  • Finish the PDA examples from the last slide we did last class.
  • Quiz 12: There will be a short quiz at the start of class on Section 2.2 until page 116.
  • Homework 5, due 1/23 2:00pm.

• Monday, January 28
  • Read: notes from last class.
  • Read ahead (not optional): Chapter 3, pages 165-173.
  • Quiz 13: There will be a short quiz at the start of class on Chapter 3, pages 165-173. You will have to give the sample run (as a sequence of configurations) of a Turing machine on a given input. For example, see page 172, Exercise 3.1, and Exercise 3.2.
  • Look over Homework 6.

• Wednesday, January 30
  • No class today. See email.
  • Read: 2.3, start of Chapter 3.
  • Quiz 14: There will be a short quiz at the start of class on Section 2.3 and related notes.
  • Homework 6, due 1/30 2:00pm.

• Monday, February 4
  • Read: Chapter 3 (skip enumerators).
  • Quiz 14: There will be a short quiz at the start of class on Section 2.3 and related notes.

• Wednesday, February 6
  • Read: Section 3.3, Section 4.1, pp. 193-197, and notes from last class.
  • Quiz 15: There will be a short quiz at the start of class on pages 193-197 (and related notes and what we did in class).
  • Homework 7, due 2/6 2:00pm.

• Monday, February 11
  • Read: Chapter 4 (but skip everything about the diagonalization method) and related notes.
  • Quiz 16: There will be a short quiz at the start of class on Section 4.1, related notes, and what we did in class.

• Wednesday, February 13
  • Read: TBA.
  • Take on-line Quiz 17 before midnight on February 13.
  • Homework 8, due 2/13 2:00pm.

4003-700.