Home Page for CS350---Section 1 (Spring 2006)

Schedule

• Monday, Wednesday, Friday, 9:00am--9:50am in Roberts 208

Textbook

• Introduction to Theory of Computation, by Michael Sipser, PWS (First Edition).

Instructor: Dr. Binhai Zhu

• Office: EPS 355
• Office hours: Wed, Fri: 10-11am, 2pm-3pm (or by appointment)
• Email: bhz@cs.montana.edu
• Phone: X4836

Syllabus by lecture

• This is the syllabus from last year, be prepared for constantly changes. At this point, all the page numbers are referred to the 1st edition. A few of you who use the 2nd edition of the textbook should adjust accordingly.
• Jan 11 --- Course overview, self-evaluation.
• Jan 13 --- Definitions for sets, sequences, tuples and graphs; proving by direct argument and induction (read page 1-9).
• Jan 16 --- No class.
• Jan 18 --- Prove by direct argument and contradiction (read page 9-25).
• Jan 20 --- Definitions for functions, relations, equivalence relations. Proving by construction. More proof examples (read page 9-25).
• Jan 23 --- Definitions for languages, strings. Finite state automaton examples. Construct FDAs. Regular languages (read page 31-43).
• Jan 25 --- Regular languages and regular operations (read page 31-45). Nondeterministic finite automaton (read page 45-52).
• Jan 27 --- NFA=DFA (read page 53-58).
• Jan 30 --- Closure of NFA under regular operations. Regular expressions. (read page 58-65).
• Feb 1 --- Equivalence between regular languages (DFA) and regular expressions (read page 66-74).
• Feb 3 --- cont. Equivalence between regular languages (DFA) and regular expressions (read page 74-76).
• Feb 6 --- Nonregular languages and the pumping lemma (read page 77-80).
• Feb 8 --- cont. Nonregular languages and the pumping lemma (read page 77-83).
• Feb 10 --- Context-free languages. Designing context-free grammars (read page 91-98).
• Feb 13 --- Chomsky normal form (read page 98-101).
• Feb 15 --- Pushdown automata (read page 101-106).
• Feb 17 --- Equivalence between PDA and CFL (read page 106-114).
• Feb 20 --- No class, President's Day.
• Feb 22 --- cont. Equivalence between PDA and CFL. Pumping lemma and its applications (read page 114-119).
• Feb 24 --- Test 1.
• Feb 27 --- Pumping lemma and its applications (read page 114-119).
• Mar 1 --- Pumping lemma and its applications (read page 114-119).
• Mar 3 --- Turing machines (read page 125-135). Church-Turing thesis (read page 142-145).
• Mar 6 --- Decidable languages (read page 153-159).
• Mar 8 --- Decidable languages. The diagonalization method (read page 151-164).
• Mar 10 --- Halting problem is undecidable (read page 159-167).
• Mar 13 - 17 --- no classes, Spring break.
• Mar 20 --- Reducibility (read page 167-175).
• Mar 22 --- Reduction from computation histories. PCP (read page 176-184).
• Mar 24 --- Reduction from computation histories (read page 176-182). Big-O notations and properties.
• Mar 27 --- Big-O notations. Time complexity (read page 225-232).
• Mar 29 --- Test 2.
• Mar 31 --- Time complexity (read page 225-232).
• Apr 3 --- The class of P (read page 233-241).
• Apr 5 --- The class of P, dynamic programming (read page 233-241).
• Apr 7 --- The class NP (read page 241-247).
• Apr 10 --- NP-completeness, polynomial reduction (read page 247-261). HC < TSP.
• Apr 12 --- More NP-complete examples: VC < CLIQUE, 3SAT < Vertex Cover (read page 261-262 and handouts).
• Apr 14 --- Good Friday, no class.
• Apr 17 --- More NP-complete examples: 3SAT < Clique, Subset-Sum < Rectangle Packing (read page 262-271 and handouts).
• Apr 19 --- More NP-complete examples: VC < Hitting Set, IS < Set Packing, 3SAT < Subset-Sum (read page 262-271 and handouts).
• Apr 21 --- Introduction to approximation algorithms (read page 333-335 and handout).
• Apr 24 --- Preview for the Final and Test 3.
• Apr 26 --- Test 3.
• Apr 28 --- Review of Test 3 and question answering.

Tests (30%)

• CS350 - test 1 (Test 1 is scheduled on Feb 24, during regular class time. Only one A4 'cheat sheet' is allowed.)
• CS350 - test 2 (Test 2 is scheduled on Mar 29, during regular class time.)
• CS350 - test 3 (Test 3 is scheduled on Apr 26, during regular class time.)

Assignments (40%)

• CS350 - assignment 1 (pdf) or CS350 - assignment 1 (ps) (Due: Jan 30, 2006.)
• CS350 - assignment 2 (pdf) or CS350 - assignment 2 (ps) (Due: Feb 22, 2006. You can pick up the solution out of my office starting 8:00am, Feb 23)
• CS350 - assignment 3 (pdf) or CS350 - assignment 3 (ps) (Due: Mar 8, 2006. A typo i Q4 is fixed: U->0U00|#)
• CS350 - assignment 4 (pdf) or CS350 - assignment 4 (ps) (Due: Mar 24, 2006.)
• CS350 - assignment 5 (pdf) or CS350 - assignment 5 (ps) (Due: Apr 21, 2006.)

Final Exam (30%): May 1, 8:00am-9:50am

Final Grade