CS3500 Section C, Fall 2000

CS3500: Theory I
Section C
Fall 2000

Instructor:

Ion Mandoiu
Office Hours: Tue., Wed., Th. 2-3
Office: CCB 245
Phone: 894-9443
E-mail: mandoiu@cc.gatech.edu

Teaching Assistants:

Bhaskar Dutt
Office Hours: Mon. 12-1, Tue. 11-12, Th. 11-12 (CCB 226d)
E-mail: bdutt@cc.gatech.edu

Duke Hutchings
Office Hours: Tue. 9-12 (CCB Commons Area)
E-mail: hutch@cc.gatech.edu

Newsgroup: git.cc.class.cs3500c

Textbooks:

Mid-term exam topics:

Regular languages: DFAs (1.1), NFA (1.2), regular expressions (1.3), pumping lemma (1.4), closure properties;
Context-free languages: context-free grammars + Chomsky normal form (2.1), pumping lemma (2.3), PDAs (2.2), closure properties;
Turing machines: deterministic TMs (3.1), multi-tape and non-deterministic TMs + Turing enumerators (3.2), closure properties, Turing undecidable and Turing unrecognizable languages (4.2), reductions (5.1).

Sample mid-term: Postscript PDF Solutions: Postscript PDF

Final exam topics:

Asymptotic notation (CLR 2.1); recurrences (substitution & iteration methods, the master theorem, CLR 4.1-3);
divide and conquer (merge sort, quicksort, Strassen's matrix multiplication algorithm, closest pair, CLR 1.3, 8.1-2, 8.4, 31.1 & 35.4);
medians and order statistics (CLR 10.1-3); lower bound for comparison sorting (CLR 9.1);
dynamic programming (matrix-chain multiplication, CLR 16.1-2, optimum binary search trees, knapsack problem, CFL membership testing, Sipser 240-241);
greedy algorithms(activity selection, Huffman codes (CLR 17.1-3);
binary heaps (CLR 7.1-3 & 7.1-5);
graph algorithms (Kruskal's and Prim's MST algorithms, breadth-first search, the Bellman-Ford and Dijkstra algorithms for single-source minimum-weight paths, the Floyd-Warshall's algorithm for all-pairs minimum-weight paths, CLR 24.1-2, 25.1-3, 26.2);
NP-completeness (definitions of P and NP, polynomial-time reducibility, simple NP-completeness proofs, from Chapter 7 of Sipser).

Sample exam with solutions: Postscript PDF