Syllabus
Preliminary Examination
in Mathematical Computer Science
Algorithms and Complexity Cluster
This is one of four possible preliminary exams in computer science.
Past exams should be
available from the Mathematics Library or the office of the Director of
Graduate Studies or the MCS web home page.
Questions are drawn from the following areas and their prerequisites.
Algorithms Portion of Prelim Syllabus
Courses in Algorithms:
The relevant course for the Algorithms part of the Prelim is
 MCS 501 Computer Algorithms II
Topics in Algorithms:
 Algorithm design techniques
Divide and conquer
Dynamic programming
Greedy method
 Algorithm analysis
Recurrences
Expectedcase analysis
Amortized analysis
 Sorting and merging algorithms
Lower bounds for sorting and merging
Straight insertion sort
Quicksort
Heapsort
Merging and mergesort
Lineartime methods
 Selection algorithms
Selection in linear time (expected case)
Selection in linear time (worst case)
 Searching algorithms
Priority queues
Binary heaps
Binomial heaps
Dictionaries
Hash tables (open address and chained)
General dynamic lists
Binary search trees
Redblack trees
Btrees
Skip lists
Splay trees
 Data compression algorithms
Huffman compression
LempelZiv compression
 Numbertheoretic algorithms
RSA data encryption
Primality testing
 String matching algorithms
String matching with finite automata
The KnuthMorrisPratt algorithm
The BoyerMoore algorithm
 The FFT and applications
The FFT
Polynomial multiplication
 NP completeness
Polynomialtime reductions
Cooke's theorem
References in Algorithms:
 Thomas H. Cormen, Charles E. Leiserson, and Ronald
Rivest, "Introduction to Algorithms", The MIT Press, 1990.
 Sara Baase, "Computer Algorithms: Introduction to
Design and Analysis, Second Edition", AddisonWesley, 1988.
Complexity Theory Portion of Prelim Syllabus
Courses in Complexity Theory:
The relevant courses for the Complexity Theory part of this
Prelim are
 MCS 541 Computational Complexity
 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
NPcompleteness
NPcomplete problems
References in Complexity Theory:

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

H.R.Lewis, C.H.Papadimitriou: Elements of the Theory of
Computation, PrenticeHall, 1981.
Chapters 4,5,6,7.

C.H.Papadimitriou: Computational Complexity, AddisonWesley, 1994.
Chapters 2,3,7,8,9.

M.Sipser: Introduction th the Theory of Computation,
PWS Publ. Comp., 1997.
Click to Go To Mathematical Computer Science
Preliminary Examination Library Page
Web Source: http://www.math.uic.edu/~hanson/AlgorComplexPrelimSyllabus.html
Email Comments or Questions to Professor Hanson