CISC 4090: Theory of Computation
Class times: Monday and Thursday, 11:30am – 12:45pm, FMH 316 (NOTE: FMH)
Instructor: Prof. Daniel D. Leeds (my homepage)
Office: JMH 332
E-mail: 
Office hours: Monday 1-2pm, Thursday 4-5pm
Full syllabus is available here.
Course announcements and assignments will be posted over the
course of the semester.
Course text: "Introduction to Theory of Computation", Michael Sipser 2nd or 3rd edition
Sections below:
- Announcements
- Slides
- Resources
- Assignments
Announcements:
November 21, 1:40am Quiz 4 is on Thursday, November 30. Final exam is Monday, December 18 at 9:30am.
November 2, 9:40am Quiz 3 is on Monday, November 6.
October 11, 5:00am I am offline 5pm Oct 11 to around 9pm Oct 14. I will reply Saturday night to e-mails sent during my offline time. Prof. Zhao is covering class Thursday.
October 3, 12:30am Office hours this week are Mon 1-2pm and Tues 2-4pm; next week they are Tues 2-4pm
September 28, 8:30am Quiz 2 will be on October 5. The midterm will be October 16 October 19!
September 20, 5:50pm Office hours this week were Monday 1-2 and Tuesday 2-4pm. Prof Trovato will be teaching this Thursday, starting on Lecture 3. We will return to Lecture 1 when I come back Monday.
September 11, 11:55pm Office hours this week will be Tuesday 2-4pm and Thursday 4-5pm. Quiz 1 will be held at the beginning of class Monday September 18.
August 31, 2:15pm Next Wednesday (Sept 6) is a Monday schedule. I will be out but Lisha Zhou will be teaching. I also will be unavailable for my Thursday(and Wednesday) office hours next week. Instead, I will be available for office hours Tuesday next week, 3-4pm. I am sorry for the inconvenience!
Slides:
Check slides after each lecture - I sometimes update the slides with additional content based on class discussion
Lecture 0, Course introduction and background mathematics
Lecture 1, Finite state automata
Lecture 2, The pumping lemma
Lecture 3, Context free grammars and push down automata; Updated with additional solutions; Recorded Lecture
Lecture 4, Intro to Turing machines; Recorded intro lecture
Lecture 5, Turing machines continued
Lecture 6, Decidability
Lecture 7, Complexity
Resources:
Quiz 1 Answers
- 30-34 "A range"
- 26-30 "B range"
- 22-26 "C range"
Practice Midterm questions! - color coded red, green, and blue. Answer one color at a time and then check out the corresponding answers.
- Answers for Red questions, Q5 corrected Oct 16 11:45pm
- Answers for Blue questions
- Answers for Green questions
Quiz 2 Answers
- 19.5-25 "A range"
- 16-19.5 "B range"
- 12-16 "C range"
- 8-12 "D range"
- Graded exams will be distributed on Monday October 16. Dr Zhao will be covering class Thursday October 12.
Midterm Answers
- 61-73 "A range"
- 51-61 "B range"
- 41-51 "C range"
- 31-41 "D range"
Quiz 3 practice problems
- Quiz 3 practice answers
Quiz 3 Answers
- 31-35 "A range"
- 25-31 "B range"
- 19-25 "C range"
- 13-19 "D range"
Quiz 4 Answers
- 18-22 "A range"
- 15-18 "B range"
- 12-15 "C range"
Practice Final questions! - color coded. Answer one color at a time and then check corresponding answers
- Answers for Red questions
- Answers for Blue questions
- Answers for Green questions
Assignments:
HW 0 is due September 14 --- now due Thursday, not Monday!
HW 0 Answers
- 99-110 "A range"
- 88-99 "B range"
HW 1 is due September 25
HW 1 Answers
- 66-75 "A range"
- 56-66 "B range"
- 46-56 "C range"
- 37-46 "D range"
HW 2 is due October 16, but you should be able to finish it by October 5.
HW 2 Answers
- 54-68 "A range"
- 44-54 "B range"
- 34-33 "C range"
- 24-34 "A range"
HW 3 is due November 2.
HW 3 Answers
- 76-88 "A range"
- 62-76 "B range"
- 48-62 "C range"
- 34-48 "D range"
HW 4 is due November 30, I recommend doing it by November 27.
HW 4 Answers
- 49-65 "A range"
- 37-49 "B range"
- 26-37 "C range"