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

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: Anthony Arnone

• Office hours: EPS 110, Wed: 1pm-2pm
• Email: arnone@cs.montana.edu

Syllabus by lecture

• Jan 15 --- Definitions for sets, sequences, tuples and graphs; proving by direct argument (read page 1-9).
• Jan 20 --- Definitions for functions, relations, equivalence relations; proving by construction, contradiction and induction (read page 9-25).
• Jan 22 --- More proof examples. Definitions for languages, strings. Finite state automaton examples (read page 31-41).
• Jan 27 --- Construct FDAs. Regular languages and regular operations. Nondeterminism (read page 41-53).
• Jan 29 --- Nondeterministic finite automaton, NFA=DFA (read page 53-60).
• Feb 3 --- NFA=DFA, closure of NFA under regular operations, regular expressions (read page 56-65).
• Feb 5 --- Equivalence between regular languages (DFA) and regular expressions (read page 66-76).
• Feb 10 --- Nonregular languages and the pumping lemma (read page 77-83).
• Feb 12 --- Test 1.
• Feb 17 --- Context-free languages (read page 91-95).
• Feb 19 --- Designing context-free grammars. Chomsky normal form (read page 95-101).
• Feb 24 --- Pushdown automata (read page 101-106).
• Feb 26 --- Equivalence between PDA and CFL. Pumping lemma (read page 107-117).
• Mar 2 --- Applications of pumping lemma (read page 117-119). Turing machines (read page 125-135).
• Mar 4 --- Turing machines (read page 125-135). Church-Turing thesis (read page 142-145). Decidable languages (read page 151-153).
• Mar 9 --- Decidable languages (read page 153-159).
• Mar 11 --- Halting problem is undecidable (read page 159-168).
• Mar 16 & 18 --- no classes, study break.
• Mar 23 --- Reducibility (read page 171-175).
• Mar 25 --- Reduction from computation histories. PCP (read page 176-184).
• Mar 30 --- Test 2.
• Apr 1 --- Time complexity (read page 225-232).
• Apr 6 --- The class P (read page 233-241).
• Apr 8 --- The class NP (read page 241-247).
• Apr 8 --- The class NP (read page 241-247).
• Apr 13 --- NP-completeness, polynomial reduction (read page 247-261).
• Apr 15 --- More NP-complete examples. read page (262-271).
• Apr 20 --- More NP-complete examples. Space complexity (read page 277-282).
• Apr 22 --- Test 3.
• Apr 27 --- Introduction to Approximation Algorithms (read page 333-335).
• Apr 29 --- Review for Final.

Tests (30%)

• CS350 - test 1 (Test 1 is scheduled on February 12, during regular class time.)
• CS350 - test 2 (Test 2 is scheduled on March 30, during regular class time.)
• CS350 - test 3 (Test 3 is scheduled on April 22, during regular class time.)

Assignments (40%)

• CS350 - assignment 1 (pdf) or CS350 - assignment 1 (ps) (Due: February 10, 2004.)
• CS350 - assignment 2 (pdf) or CS350 - assignment 2 (ps) (Due: March 2, 2004.)
• CS350 - assignment 3 (pdf) or CS350 - assignment 3 (ps) (Due: March 23, 2004.)
• CS350 - assignment 4 (pdf) or CS350 - assignment 4 (ps) (Due: April 8, 2004.)
• CS350 - assignment 5 (pdf) or CS350 - assignment 5 (ps) (Due: April 27, 2004.)

Final Exam (30%): May 3, 2:00pm-3:50pm

Final Grade