CISC 4090: Theory of Computation

CISC 4090: Theory of Computation

Class times: Monday and Thursday, 11:30am – 12:45pm, JMH 330
Instructor: Prof. Daniel D. Leeds (my homepage)
Office: JMH 332
E-mail:
Office hours: Monday 3-4pm, Thursday 1-2pm

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:
Dec 8, 3:50pm: I will hold finals office hours Tuesday and Thursday 11am to noon.
Dec 5, 12:40am: Office hours today (Dec 5) are 10:30-11:30am (as announced by e-mail).
Nov 24, 5:05pm: Office hours tomorrow (Nov 25) are 10:30-11:30am (as announced in class Thursday).
The final exam will be Dec 16, 10am-noon.
Nov 20, 10:30pm: Office hours tomorrow (Nov 21) are 10:30-11:30am (as announced in class Monday).
Nov 15, 3:15pm: Quiz 4 will be Monday Nov 25.
Nov 7, 11:59pm: We will have our make-up class Mon Nov 11, 1-2:15pm in JMH 342 computer lab. I also will post a recording of it, but I highly recommend you intend in person if possible.
Nov 4, 11:59pm: I will be in my office 12-3pm Tuesday. Also, quiz 3 is November 11!
Oct 23, 11:52pm: I will be in my office before the midterm, 10:15-11:15am Oct 24.
Oct 11, 4:45pm: We will not have class Monday October 21; I will schedule a makeup class. (There also is no school Mon Oct 14.)

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 machines and regular languages
Lecture 2, The pumping lemma
Lecture 3, Context free grammars and push-down automata
Lecture 4, Intro to Turing machines; Audio from makeup lecture, Digital white board slides: slide1, slide2, slide3, slide4, slide5
Lecture 5, Decidability; Audio from makeup lecture, Digital white board slides: slide1, slide2, slide3
Lecture 6, Complexity

Resources:
Example quiz questions and Example answers Quiz 1 practice answers corrected Sept 15, 3:42pm!

Quiz 1 answers

31-28 A range

24-28 B range

20-24 C range

Quiz 2 answers

20-25 A range

16-20 B range

12-16 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

Answers for Blue questions

Answers for Green questions

Midterm answers

64.5-74 A range

55-64.5 B range

45.5-55 C range

NOTE: the grade ranges listed on the board in class were slightly off. My apologies!

Quiz 3 answers

36-40 A range

31-36 B range

27-31 C range

23-27 D range

Quiz 4 answers

40-50 A range

30-40 B range

20-30 C range

10-20 D 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:
Homework 0 due Sept 9
- Update Aug 29 afternoon: STILL WILL be due Sept 9
- Update Sep 4 afternoon: Ignore question 2e. It accidentally has the same answer as 2b

Homework 0 answers

88-98 A range

78-88 B range

68-78 C range

Homework 1 due Sept 26 23, apologies for the earlier typo!; Correction to Q9 made on Sept 18

Homework 1 answers

72-83 A range

60-72 B range

48-60 C range

36-48 D range

Homework 2 due Oct 10
Question 7 diagram corrected Oct 7 8:40pm --- ε,ε->ε instead of ε,ε->$

Homework 2 answers
Homework 3 due Nov 7