CSE 355: Introduction to Theoretical Computer Science
Class: WGHL 101, T/Th, 3:00--4:15PM
Office Hours: BYENG 594, T/Th, 5:30--6:30PM
Recitations (TA: Mehrdad): BYAC 190, W 9:40-10:30AM, W 10:45-11:35AM
Office Hours (TA: Mehrdad): Centerpoint, W 1:00-2:00PM, F 11:00AM-noon
Recitations (TA: Ze): BYAC 190, Th 4:30-5:20PM
Office Hours (TA: Ze): Centerpoint, M 2:00-3:00PM, W 11:00AM-noon
| Course home | Syllabus | Schedule | Student Projects |
Subject to change. Check back frequently for updates.
Last updated: November 2, 2017
| Date | Topics | Lecture Notes |
Reading/Project Assignments | Deadlines | Important Dates |
| Th. 08/17 | Course introduction. | Sipser, Third Edition, Sec. 0.1, 0.2 and 1.1 | Quiz 1, due August 22, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Tue. 08/22 | Finite Automata. |
Lecture Slides (up to regular language) |
Sipser, Third Edition, Sec. 0.3, 0.4 and http://jflap.org/tutorial/- > Finite Automata - > Construct and Run - > Building Your First Finite Automaton (up to Running the Finite Automaton on Multiple Strings) Software link available in slides | Quiz 2, due August 24, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | |
| Th. 08/24 | Finite Automata (cont.) |
Lecture Slides (starting from regular language) |
Sipser, Third Edition, Sec. 1.1 (up to page 58, closure under the regular operations) | Quiz 3, due August 29, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | Homework 1, due August 31, 11:59PM (homeworks available at BB- >Content- >Homeworks) |
| Tue. 08/29 | Nondeterministic Finite Automata | Sipser, Third Edition, Sec. 1.1, 1.2 (page 58 - 66, up to Equivalence with Finite Automata) | Quiz 4, due August 31, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Th. 08/31 | Regular Expressions and Operations | Sipser, Third Edition, Sec. 1.3 (page 66 - 77, Equivalence with Finite Automata) | Quiz 5, due September 5, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | Homework 2, due September 8, 11:59PM (homeworks available at BB- >Content- >Homeworks) | |
| Tue. 09/05 | Regular Expressions and its Equivalence with FA | Sipser, Third Edition, Sec. 1.4 (nonregular langauges) | Quiz 6, due September 7, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Th. 09/07 | Nonregular Languages | Sipser, Third Edition, Sec. 2.1 (CFG) | Quiz 7, due September 12, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) |
Midterm #1 (Chapter 1), September 19, in class Homework 3, due September 15, 11:59PM (homeworks available at BB- >Content- >Homeworks) |
|
| Tue. 09/12 | Context Free Grammars | Sipser, Third Edition, Sec. 2.2 (up to page 118) (PDA) | Quiz 8, due September 12, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Th. 09/14 | Pushdown Automata (PDA) | Sipser, Third Edition, Sec. 2.2 (PDA) | Quiz 9, due September 21, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Tue. 09/19 | In class midterm 1 | ||||
| Th. 09/21 | Pushdown Automata (PDA) (cont.) | Sipser, Third Edition, Sec. 2.2 (revisit proofs) and Sec. 2.4 (130-134 until Theorem 2.43) (PDA) | Quiz 10, due September 26, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | Homework 4, due October 4, 11:59PM (homeworks available at BB- >Content- >Homeworks) Group part included. | |
| Tue. 09/26 | Review of mid-term | Project , due October 20, 11:59PM | |||
| Th. 09/28 | PDA (cont.) and Project Discussion | Sipser, Third Edition, Sec. 2.3 | Quiz 11, due October 3, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Tue. 10/03 | NCFL | ||||
| Th. 10/05 | CFL review | Sipser, Third Edition, Sec. 3.1 | Quiz 12, due October 12, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Tue. 10/10 | Fall break; class excused | ||||
| Th. 10/12 | Turing machines | Sipser, Third Edition, Sec. 3.2 | Quiz 13, due October 17, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) |
Midterm #2 (Chapters 2 and 3), October 26, in class |
|
| Tue. 10/17 | Turing machines II | Sipser, Third Edition, Sec. 3.3 | Homework 5, due October 24, 11:59PM. | ||
| Th. 10/19 | Turing machines II (cont.) | ||||
| Tue. 10/24 | Midterm II review | ||||
| Th. 10/26 | In class Midterm II | ||||
| Tue. 10/31 | Decidability | Sipser, Third Edition, Sec. 4.1 | Quiz 14, due Nov 2, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Th. 11/02 | Decidability (cont.) | Sipser, Third Edition, Sec. 6.1 | Quiz 15, due Nov 7, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | Homework 6, due November 11, 11:59PM. | |
| Tue. 11/07 | Midterm review | ||||
| Th. 11/09 | Recursion theorem | Sipser, Third Edition, Sec. 5.1 | Quiz 16, due Nov 14, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) |
Midterm #1 (Chapter 4, 5, 6.1), November 21, in class Project #2, due November 27, 11:59PM. |
|
| Tue. 11/14 | Reducibility | Sipser, Third Edition, Sec. 5.3 | Quiz 17, due Nov 16, 3PM (quizzes available at BB- >Content- >Quizzes until the due time) | ||
| Th. 11/16 | Mapping Reducibility | Sipser, Third Edition, Sec. 5.3 | Homework 7 (optional), due Nov 19, 11:59PM. | ||
| Tue. 11/21 | In class Midterm III | ||||
| Th. 11/23 | Happy Turkey day! | ||||
| Tue. 11/28 | Complexity theory |
 Homework 8, due Dec 4, 11:59PM.
|
|||
| Th. 11/30 | P and NP |