CISC 4090: Theory of Computation
Class times: Monday and Thursday, 2:30 – 3:45pm, John Mulcahy Hall (JMH) 302
Instructor: Prof. Daniel D. Leeds (my homepage)
Office: JMH 332
E-mail: 
Office hours: Monday 4:30 – 5:30 pm and Thursday 11:30am – 12:30pm, and by appointment
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
- Answers
Announcements:
April 30, 1:30pm Office hours Monday May 1 have been rescheduled to 11:30-12:45. I also will hold office hour Monday May 8, 3:30-5:30pm.
April 20, 11:30pm Our final exam will be May 11, 1:30-3:30!
April 16, 5:30pm As announced in class on Thursday, we will have quiz 4 on April 24. HW 4 will be do April 27. Check out already-answered problems in Chapters 4, 5, and 7 for practice!
April 10, 11:50am Regular office hours today (4:30-5:30) are cancelled. I am available earlier (11:30-12:30) for any questions.
March 28, 9:10pm Quiz 3 is on April 3.
February 13, 5:40pm The midterm will be on March 6. Quiz 2 will be on February 23.
February 9, 12:15am Our snow day means I will be out during scheduled office hours. However, I will be available by e-mail 11:30-12:30 and 4:30-5:30 Thursday to answer questions related to HW1. HW1 is still due Monday. Good luck!
January 26, 10:40pm As announced in class, Quiz 1 will be given at the start of class February 2. Note: The quiz will take place at the start of class!
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 and regular languages
Lecture 2, Non-regular languages
Lecture 3, Context-Free Grammars and Push Down Automata
Lecture 4, Intro to Turing Machines
Lecture 5, Decidability
Lecture 6, Complexity
Lecture 7, Applications
Resources:
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
NEW! Quiz 3 practice problems
NEW! Quiz 3 practice answers
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
- Answers for Blue questions - correction made to Q2 at 10:15pm, Mar 4
- Answers for Green questions - additional corrections March 5 morning
A few students have requested some more fully-worked examples of conversion to Chomsky Normal Form. Three new examples can be found here!
Assignments:
Homework 0 due January 30 (no longer January 26!) - for question 7, assume you cannot have an edge from a node back to itself.
Homework 0 answers
99-110 - A range
88-99 - B range
77-88 - C range
Homework 1 now due February 13; question 5a has also been modified
Homework 1 answers
94-107 - A range
81-94 - B range
68-81 - C range
55-68 - D range
Homework 2 due February 27; final version posted 8:40pm February 21 (questions 4-6 are new! question 3 slightly shorter!)
- HW 2 answers - Question 6 answer updated with alternative correct answer 5pm March 2.
- 60-72 - A range
- 48-60 - B range
- 36-48 - C range
- 24-36 - D range
Homework 3 due March 30 - ammended Q5 and 6 according to my e-mail from March 28
- HW 3 answers
- 51-60 - A range
- 42-51 - B range
- 33-42 - C range
- 24-33 - D range
Homework 4 due April 27
- HW 4 answers
- 64-81 - A range
- 52-64 - B range
- 40-52 - C range
- 28-40 - D range
Answers:
Quiz 1 Answers
Grade assignment
- 35-39 - A range
- 31-35 - B range
- 27-31 - C range
Quiz 2 Answers - Question 4b has an alternative answer that is technically correct, that I incorrectly marked as wrong. Contact me if you had the technically correct answer and I can review your paper.
Grade assignment
- 28-33 - A range
- 23-28 - B range
- 18-23 - C range
- 13-18 - D range
Midterm answers
Grade assignment
- 65-72 - A range
- 58-65 - B range
- 51-58 - C range
- 43-51 - D range
Quiz 3 Answers
Grade assignment
- 52-60 - A range
- 44-52 - B range
- 36-44 - C range
- 28-36 - D range
Quiz 4 Answers - useful to look at while completing the homework
- 23-30 - A range
- 17-23 - B range
- 12-17 - C range