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

Schedule

• Monday, Wednesday, Friday, 8:00am--8:50am in EPS 108

Textbook

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

Instructor: Dr. Binhai Zhu

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

Syllabus by lecture

• Jan 16 --- Course overview, self-evaluation.
• Jan 18 --- Definitions for sets; proving by direct argument and induction (read page 1-9).
• Jan 21 --- No class, Martin Luther King holiday.
• Jan 23 --- Definitions for sequences, tuples and graphs; proving by induction and contradiction. Definitions for functions, relations, equivalence relations (read page 9-25).
• Jan 25 --- More proof examples (read page 9-25). Proving by construction. Definitions for languages, strings. Finite state automaton examples (read page 31-36).
• Jan 28 --- Construct FDAs. Regular languages and regular operations (read page 31-46).
• Jan 30 --- Nondeterministic finite automaton (read page 47-52).
• Feb 1 --- NFA=DFA (read page 53-58). Closure of NFA under regular operations.
• Feb 4 --- Regular expressions. Equivalence between regular languages (DFA) and regular expressions (read page 59-74).
• Feb 6 --- Equivalence between regular languages (DFA) and regular expressions (read page 66-74). Regular grammar.
• Feb 8 --- Nonregular languages and the pumping lemma (read page 77-80).
• Feb 11 --- cont. Nonregular languages and the pumping lemma (read page 77-83).
• Feb 13 --- Context-free languages. Designing context-free grammars (read page 91-98).
• Feb 15 --- Chomsky normal form (read page 98-101).
• Feb 18 --- No class, President's Day.
• Feb 20 --- Pushdown automata (read page 101-106).
• Feb 22 --- Test 1.
• Feb 25 --- Equivalence between PDA and CFL (read page 106-114).
• Feb 27 --- cont. Equivalence between PDA and CFL. Pumping lemma and its applications (read page 114-119).
• Feb 29 --- Pumping lemma and its applications (read page 114-119).
• Mar 3 --- Pumping lemma and its applications (read page 114-119). Countability of sets (read page 174-176).
• Mar 5 --- The diagonalization method (read page 174-178). Turing machines (read page 137-147). Church-Turing thesis (read page 151-159).
• Mar 7 --- Decidable languages (read page 165-173).
• Mar 10 - 14 --- no classes, Spring break.
• Mar 17 --- Decidable languages (read page 165-173). The diagonalization method (read page 178-181).
• Mar 19 --- Halting problem is undecidable (read page 173-182).
• Mar 21 --- No class, University Day holiday.
• Mar 24 --- Reducibility (read page 187-1xx).
• Mar 26 --- Reduction from computation histories. PCP (read page 176-184).
• Mar 28 --- Reduction from computation histories (read page 176-182). Big-O notations and properties.
• Mar 31 --- Big-O notations. Time complexity (read page 225-232).
• Apr 2 --- Time complexity (read page 225-232).
• Apr 4 --- The class of P (read page 233-241).
• Apr 7 --- Test 2.
• Apr 9 --- The class of P, dynamic programming (read page 233-241).
• Apr 11 --- The class NP (read page 241-247). Polynomial reduction, HC < TSP.
• Apr 14 --- NP-completeness, polynomial reduction (read page 247-261). VC < CLIQUE (read page 261-262 and handouts).
• Apr 16 --- More NP-complete examples: VC < IS, IS < CLIQUE, 3SAT < Vertex Cover (read page 261-262 and handouts).
• Apr 18 --- More NP-complete examples: 3SAT < Vertex Cover, 3SAT < Clique, Subset-Sum < Rectangle Packing (read page 262-271 and handouts).
• Apr 21 --- More NP-complete examples: 3SAT < Subset-Sum (read page 262-271 and handouts).
• Apr 23 --- More NP-complete examples: VC < Hitting Set, IS < Set Packing.
• Apr 25 --- Introduction to approximation algorithms (read page 333-335 and handouts).
• Apr 28 --- Introduction to approximation algorithms (read page 333-335 and handouts). Preview for Test 3.
• Apr 30 --- Test 3.
• May 2 --- Review of Test 3, preview for the Final and question answering.

Tests (30%)

• CS350 - test 1 (Test 1 is scheduled on Feb 22, during regular class time. Contents: everything covered up to the end of Feb 11 class. Only one A4 'cheat sheet' is allowed.)
• CS350 - test 2 (Test 2 is scheduled on Apr 7, during regular class time. Contents: everything covered from the Feb 11 class to the Mar 28 class. Only one A4 'cheat sheet' is allowed.)
• CS350 - test 3 (Test 3 is scheduled on Apr 30, during regular class time. Contents: everything covered from the Mar 31 class to the Apr 23 class (i.e., approximation algorithms will not be tested). Only one A4 'cheat sheet' is allowed.)

Assignments (40%)

• CS350 - assignment 1 (pdf) (Due: Feb 4, 2008.)
• CS350 - assignment 2 (pdf) (Due: Feb 15, 2008.)
• CS350 - assignment 3 (pdf) (Due: Mar 17, 2008.)
• CS350 - assignment 4 (pdf) (Due: Apr 2, 2008.)
• CS350 - assignment 5 (pdf) (Due: Apr 25, 2008.)

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

Final Grade