Theory - CS 3500D

Instructor: Edyta Szymanska

Class: MTWF 2:05-2:55 in B6A Boggs-Chemistry

Office Hours: Wednesday 10:00-11:00 or by appointment;

Teacher Assistants:

Thomas Bankston
Ying Yang
Office hours: M 12-1pm, T 12-2 or by appointment, CCB 154 F 12-2pm, Commons area
Phone:

Textbooks:

  • Introduction to the Theory of Computation by Michael Sipser, PWS Publishing, 1997
  • Introduction to Algorithms by T. Cormen, Ch. Leiserson, R. Rivest(2nd edition) The MIT Press

    • Grading:

    Homeworks: 25%, two Mid-terms: 30%, Project: 15% Final exam: 30%.

    Tentative Important Dates:

      Mid-term 1: Monday, February 10
      Mid-term 2: Friday, March 28
      Final exam: Thursday, May 1, 11:30-2:20

    Class newsgroup: git.cc.class.cs3500d

    To see your grades go to: WebCT


    No. Date Material covered Homework[DueDate] Comments, handouts
    1 01/06 Introductory concepts in strings and languages. syllabus
    2 01/07 Finite Automata. Regular languages. Closure under union. (1.1)
    3 01/08 Regular operations. Nondeterministic finite automata.(1.2)
    4 01/10 Equivalence of NFAs and DFAs.(1.2) 1.4 ab, 1.5 ab, 1.7(for 1.4cd), 1.8(for 1.4n)/p.84 1.9, 1.12a /p.85 [01/15] AssignmentGuide
    5 01/13 Closure under regular operations.(1.2)
    6 01/14 Regular expressions. (1.3)
    7 01/15 Equivalence of regular expressions and finite automata.(1.3)
    8 01/17 Converting DFAs into regular expressions.(1.3) 1.14bc, 1.15befh, 1.16b/86, 1.24, 1.25, 1.29/89[01/22]
    9 01/21 Pumping lemma for regular languages. (1.4)
    10 01/22 Nonregular languages. (1.4)
    11 01/24 Applications of the pumping lemma. Context-free grammars. 1.17ac/86, 1.23b/88, 1.28, 1.36, 1.37/89, 1.38/90[01/29]
    12 01/27 Parse trees. Ambiguous grammars.
    13 01/28 Chomsky normal form of a CFG.
    14 01/29 Pushdown automata.
    15 01/31 Pushdown Automata and CFG. 2.3, 2.6a, 2.7(for 2.6a only!)/120, 2.10, 2.14, 2.19/121 [02/05]
    16 02/03 Equivalence of PDAs and CFGs. MidtermExamInfo
    17 02/04 Pumping lemma for CFLs.
    18 02/05 Non-context-free languages. SampleExamProblems
    19 02/07 Review. No homework this week.
    20 02/10 MIDTERM EXAM
    21 02/11 Turing machines.
    22 02/12 Computing functions with TM. Variants of Turing machines.
    23 02/14 Nondeterministic Turing machines. 3.2e/147, 3.14ae/149, 3.19/149 plus problems [02/19] Convert_ps2pdf
    24 02/17 Turing decidable languages.
    25 02/18 The halting problem.
    26 02/19 The halting problem (cont.). Introduction to the complexity theory.
    27 02/21 Complexity classes P and NP. 4.1/168, 4.2/169, 4.3/169 plus problems [02/26]
    28 02/24 NP Problems. Polynomial-time reductions.
    29 02/25 NP Completeness.
    30 02/26 Proving NP completeness.
    31 02/28 More NP-complete problems. No homework this week but PROJECT-Part I [03/17] New version of p4.TM !
    32 03/10 Introduction to algorithms.
    33 03/11 Insertion sort and merge sort.
    34 03/12 Divide and conquer paradigm. Strassen's algorithm.
    35 03/14 Quicksort algorithm. Sipser: 7.7/271, 7.29/274 (describe the algorithm and argue its running time), 7.34/275 hint, CLR: 2-1/37, 28.2-1/741, 4.3-1/75 [03/19]
    36 03/17 Recurrences.
    37 03/18 Master method for solving recurrences.
    38 03/19 Randomized Quicksort. Heapsort.
    39 03/21 Heapsort cont. No homework this week BUT Practise Problems(not for credit)
    40 03/24 Lower bound for comparison sorts. Counting sort.
    41 03/25 Medians and order statistics: linear time selection algorithm. MidtermExam2Info
    42 03/26 Review.
    43 03/28 MIDTERM EXAM #2
    44 03/31 Dynamic programming: Longest Common Subsequence.
    45 04/01 Cocke-Kasami-Younger algorithm (Sipser: page 240).
    46 04/02 CYK algorithm. 0-1 knapsack problem.
    47 04/04 Midterm Problems - Solutions 15.4-4/356 plus 2 more problems [04/09] PROJECT-Part II
    48 04/07 Greedy algorithms. Huffman codes. Project2_Sample_Input_Output_JAVA_Submission
    49 04/08 Analysis of Huffman's algorithm.
    50 04/09 Introduction to graph algorithms. The MST problem.
    51 04/11 Kruskal's and Prim's algorithms. 16.3-2/392,22.2-6/539, 23.2-4/574 plus 22.4-1/551[04/22]
    52 04/14 Time complexity of MST algorithms. Depth First Search algorithm.
    53 04/15 DFS. Topological Sort.
    54 04/16 BFS. String matching.
    55 04/18 Knuth-Morris Pratt algorithm.
    56 04/21 Shortest Paths: Bellman-Ford and Dijkstra's algorithms.
    56 04/22 Correctnes of B-F and Dijkstra's algorithms.
    56 04/23 All-pairs shortest paths: Floyd-Warshall algorithm.
    FINAL EXAM INFORMATIONS Sample Problems
    56 04/25 REVIEW.

    Course Outline:

    1. Introductory concepts in formal languages and automata theory: languages, operations on languages, and basic machine models. (Sipser: Chapter 0)
    2. Regular languages: Deterministic and nondeterministic finite state automata. Closure under union, intersection, complementation, concatenation, and star operations. Equivalence of Non-deterministic finite state automata and deterministic finite state automata. Regular expressions and equivalence of regular expressions and regular languages. Pumping lemma. (Sipser: Chapter 1) (Optional: Myhill-Nerode theorem.)
    3. Context-free languages: Context-free grammars. Ambiguity. Normal forms such as Chomsky normal form. Closure under union, concatenation, and star operations. Non-closure under intersection and complementation operations. Parse-trees. Pumping lemma. Pushdown automata. Equivalence of pushdown automata and context-free grammars. (Sipser: Chapter 2) (Optional: Cocke-Kasami-Younger algorithm. Deterministic context-free languages. Parsing.) (Other references may have to be used for these optional topics. CKY is covered in Sipser's book (page 240).)
    4. Decidability: Turing machines. Recursively-enumerable and recursive languages. Equivalence of varieties of models such as multi-tape and non-deterministic Turing machines with the deterministic Turing machines. Diagonalization. Undecidability of the Halting problem. (Sipser: Chapter 3)
    5. Introductory concepts in algorithms: computational problems, models of computation, order notation, recurrences. (CLR: Chapters 1, 2.1, 4.3)
    6. Divide and Conquer: Strassen's matrix multiplication (CLR: Chapter 31.2), merge sort, divide and conquer recurrences (CLR: Chapter 4.3).
    7. Sorting: heap sort (CLR: Chapter 7), quick sort (CLR: Chapter 8), lower bound for comparison sorting (CLR: Chapter 9.1), counting sort (CLR: Chapter 9.2).
    8. Medians and order statistics: linear time selection algorithm (CLR: Chapter 10).
    9. Searching: Balanced binary search trees (CLR: Chapter 13).
    10. Dynamic programming: Matrix-chain multiplication (CLR: Chapter 16) Cocke-Kasami-Younger algorithm (Sipser: page 240).
    11. Greedy algorithms: Huffman codes (CLR: Chapter 17.3).
    12. Algorithms for elementary graph problems:
      • Graph traversal techniques and their applications (breadth-first search, depth-first search) (CLR: Chapter 23).
      • Minimum spanning trees (Kruskal's and Prim's algorithms) (CLR: Chapter 24).
      • Shortest paths (Dijkstra's algorithm and Bellman-Ford algorithm). (CLR: Chapter 25).
      • Warshall's algorithm for transitive closure. (CLR: Chapter 26.2).
    13. String matching: Knuth-Morris-Pratt algorithm. (CLR: Chapter 34.4).
    14. NP-Completeness: Basic notions such as reducibility and completeness. Examples of NP-Complete problems. (CLR: Chapter 36).

    Contact

    Edyta Szymanska
    room 123 CoC
    (404)385-2272
    College of Computing
    Georgia Institute of Technology
    Atlanta, Georgia