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

Schedule

• Tuesday, Thursday, 9:30am--10:45am in Roberts 321

Textbook

• Introduction to Theory of Computation, by Michael Sipser, PWS.

Instructor: Dr. Binhai Zhu

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

TA: Christopher Marth

• Office hours: EPS 110 Consulting: Fri, 4pm-5pm; Other hours: Mon: 4-5pm, Wed: 2-3pm, Thu: 10-11am.
• Email: christopherm@cs.montana.edu

Syllabus by lecture

• This is the syllabus from last year, be prepared for possible changes.
• Jan 13 --- Definitions for sets, sequences, tuples and graphs; proving by direct induction (read page 1-9).
• Jan 18 --- Definitions for functions, relations, equivalence relations; proving by direct argument (read page 9-25).
• Jan 20 --- Prove by direct argument, construction and contradiction. More proof examples.
• Jan 25 --- Definitions for languages, strings. Finite state automaton examples. Construct FDAs. Regular languages and regular operations (read page 31-45).
• Jan 27 --- Nondeterministic finite automaton, NFA=DFA (read page 45-60).
• Feb 1 --- NFA=DFA, closure of NFA under regular operations, regular expressions (read page 56-65).
• Feb 3 --- Equivalence between regular languages (DFA) and regular expressions (read page 66-76).
• Feb 8 --- cont. Equivalence between regular languages (DFA) and regular expressions (read page 66-76). Nonregular languages and the pumping lemma (read page 77-80).
• Feb 10 --- Nonregular languages and the pumping lemma (read page 77-83).
• Feb 15 --- Context-free languages (read page 91-96).
• Feb 17 --- Designing context-free grammars. Chomsky normal form (read page 95-101).
• Feb 22 --- Pushdown automata (read page 101-106).
• Feb 24 --- Test 1.
• Mar 1 --- Equivalence between PDA and CFL (read page 106-114).
• Mar 3 --- Pumping lemma and its applications (read page 114-119).
• Mar 8 --- Turing machines (read page 125-135). Church-Turing thesis (read page 142-145). Decidable languages (read page 151-153).
• Mar 10 --- Decidable languages (read page 153-159).
• Mar 15 & 17 --- no classes, Spring break.
• Mar 22 --- Halting problem is undecidable (read page 159-167).
• Mar 24 --- Reducibility (read page 167-175).
• Mar 29 --- Reduction from computation histories. PCP (read page 176-184).
• Mar 31 --- Test 2.
• Apr 5 --- Time complexity (read page 225-232).
• Apr 7 --- The class of P (read page 233-241).
• Apr 12 --- The class NP (read page 241-247).
• Apr 14 --- NP-completeness, polynomial reduction (read page 247-261).
• Apr 19 --- More NP-complete examples: HC < TSP, VC < IS < CLIQUE, VC < Hitting Set (read page 262-271 and handouts).
• Apr 21 --- More NP-complete examples: IS < Set Packing, 3SAT < Subset-Sum, Subset-Sum < Rectangle Packing (read page 262-271 and handouts).
• Apr 26 --- Test 3.
• Apr 28 --- Space complexity (read page 277-282). Review for Final.

• CS350 - test 1 (Test 1 is scheduled on Feb 24, during regular class time.)
• CS350 - test 2 (Test 2 is scheduled on Mar 31, 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: February 3, 2005.)
• CS350 - assignment 2 (pdf) or CS350 - assignment 2 (ps) (Due: February 17, 2005.)
• CS350 - assignment 3 (pdf) or CS350 - assignment 3 (ps) (Due: March 10, 2005.)
• CS350 - assignment 4 (pdf) or CS350 - assignment 4 (ps) (Due: April 7, 2005.)
• CS350 - assignment 5 (pdf) or CS350 - assignment 5 (ps) (Due: April 21, 2005.)

Final Exam (30%): May 4, 4:00pm-5:50pm

Final Grade