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%)
Final Exam (30%): May 6, 8:00am-9:50am
Dr. Binhai Zhu
Professor
Department of Computer Science
Montana State University
Bozeman, MT 59717
Email: bhz At cs DoT montana DoT edu
Office: EPS 355
Phone: 406-994-4836
Fax: 406-994-4376