Syllabus
Preliminary Examination
in Mathematical Computer Science
Algorithms and Complexity Cluster

Courses in Algorithms:

The relevant course for the Algorithms part of the Prelim is

• MCS 501 Computer Algorithms II

Topics in Algorithms:

1. Algorithm design techniques
   
   Divide and conquer
   Dynamic programming
   Greedy method

2. Algorithm analysis
   
   Recurrences
   Expected-case analysis
   Amortized analysis

3. Sorting and merging algorithms
   
   Lower bounds for sorting and merging
   Straight insertion sort
   Quicksort
   Heapsort
   Merging and mergesort
   Linear-time methods

4. Selection algorithms
   
   Selection in linear time (expected case)
   Selection in linear time (worst case)

5. Searching algorithms
   
   Priority queues
   
   Binary heaps
   Binomial heaps
   
   Dictionaries
   
   Hash tables (open address and chained)
   
   General dynamic lists
   
   Binary search trees
   Red-black trees
   B-trees
   Skip lists
   Splay trees

6. Data compression algorithms
   
   Huffman compression
   Lempel-Ziv compression

7. Number-theoretic algorithms
   
   RSA data encryption
   Primality testing

8. String matching algorithms
   
   String matching with finite automata
   The Knuth-Morris-Pratt algorithm
   The Boyer-Moore algorithm

9. The FFT and applications
   
   The FFT
   Polynomial multiplication

10. NP completeness
    
    Polynomial-time reductions
    Cooke's theorem

References in Algorithms:

1. Thomas H. Cormen, Charles E. Leiserson, and Ronald Rivest, "Introduction to Algorithms", The MIT Press, 1990.

2. Sara Baase, "Computer Algorithms: Introduction to Design and Analysis, Second Edition", Addison-Wesley, 1988.

Courses in Complexity Theory:

The relevant courses for the Complexity Theory part of this Prelim are

1. MCS 541 Computational Complexity

   and/or

2. MCS 542 Theory of Computation II

Topics in Complexity Theory:

Turing machines
Modifications of Turing machines
Church's thesis
Recursive and recursively enumerable languages
Universal Turing machine, halting problem
Rice's theorem
Post Correspondance problem
Undecidable problems for grammars


Time and space complexity
Linear speedup theorem
Reduction of the number of tapes
Gap theorem
Hierarchy theorems
Nondeterministic machines
Savitch's theorem
P and NP
Reductions
NP-completeness
NP-complete problems

References in Complexity Theory:

1. J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation , Addison-Wesley, 1979.
   Chapters 7,8,12,13.

2. H.R.Lewis, C.H.Papadimitriou: Elements of the Theory of Computation, Prentice-Hall, 1981.
   Chapters 4,5,6,7.

3. C.H.Papadimitriou: Computational Complexity, Addison-Wesley, 1994.
   Chapters 2,3,7,8,9.

4. M.Sipser: Introduction th the Theory of Computation, PWS Publ. Comp., 1997.