CSE 598B Theory of Computation, Spring 2008

Welcome to the course web page for CSE 598B!

Course Staff

Office Phone Email @cse.psu.edu Office Hours
Prof. Sofya Raskhodnikova IST 343F x3-0608 sofya Mon 3--5pm


Feb 15
Exam 1 Announcement

Tentative Schedule and Handouts

Lec.DateTopicsReadingHomework, exams and handouts
1Mon, Jan 14Introduction, finite automataChapters 0-1.1General Course Information
2Wed, Jan 16Regular operations, nondeterminism, closure properties, regular expressionsChapters 1.2-1.3 HW 1 out
3Wed, Jan 23Closure properties, equivalence of DFAs and regular expressions, pumping lemma for regular languagesChapters 1.2-1.4HW1 due, HW 2 out
4Mon, Jan 28 Context-free grammars and pushdown automataChapters 2.1-2.2
5Wed, Jan 30Equivalence of CFGs and PDAs, pumping lemma for context-free languagesChapters 2.2-2.3 HW2 due, HW 3 out
6Fri, Feb 1 at 10:30am in IST 333 Make up lecture: Finish pumping lemma for CFLs. Turing machines Extra office hours: 4pm-5pm Chapters 3.1-3.3
Mon, Feb 4 Lecture and office hours are cancelled
Wed, Feb 6 Lecture is cancelled. Slip HW3 under my office door ChaptersHW3 due, HW 4 out
7Mon, Feb 11TM variants. Enumerators.Chapters 3.2-3.3 You can resubmit optional problem on HW3 with HW4
8Wed, Feb 13Decidable languages. Review.Chapter 4.1HW4 due at 11:59am on Thursday
9Mon, Feb 18Undecidability. Halting problem. Diagonalization.Chapters 4.2, 5.1 Exam 8:15-10:15pm in 103 Walker, Chapters 0-4.1
10Wed, Feb 20Mapping reducibility. Turing-unrecognizable languages.Chapters 5.1, 5.3HW 5 out
11Fri, Feb 22 at 10:30am in IST 333 Make up lecture: Computation history metod. Undecidability of E_LBA and POSTChapters 5.1, 5.2
12Mon, Feb 25 Computation history metod: undecidability of ALL_PDA. Recursion TheoremChapters 5.1, 6.1
13Wed, Feb 27Problem solving sessionHW5 due, HW 6 out
14Mon, Mar 3Asymptotic notation; measuring complexityChapter 7.1
15Wed, Mar 5Complexity relationships among models. Class P.Chapter 7.2HW6 due, HW 7 out
Mar 10-14 Have a good spring break!
16Mon, Mar 17Class NPChapters 7.3-7.4
17Wed, Mar 19NP-completeness. Cook-Levin TheoremChapter 7.4HW7 due, HW 8 out
18Mon, Mar 24Examples of NP-complete problemsChapter 7.5
19Wed, Mar 26Review and problem solvingHW8 due
20Mon, Mar 31Savitch's TheoremChapters 8.1 Exam 8:15-10:15pm in 103 Walker
21Wed, Apr 2PSPACE and PSPACE-completenessChapters 8.2HW 9 out
22Mon, Apr 7PSPACE-completeness. Problem solving session.Chapters 8.3
23Wed, Apr 9L and NL. NL-completenessChapters 8.4-8.5HW9 due, HW 10 out
24Mon, Apr 14NL-completeness. NL=coNLChapters 8.5-8.6
25Wed, Apr 16Hierarchy theoremsChapter 9.1HW10 due, HW 11 out
26Mon, Apr 21Oracles and relativizationChapter 9.2
27Wed, Apr 23ChaptersHW11 due, HW12 out
28Mon, Apr 28Chapters
29Wed, Apr 30ChaptersHW12 due
Mon, May 5Final exam 10:30am-1:30pm, IST 333

Sofya Raskhodnikova