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
Expected-case analysis
Amortized analysis
- Sorting and merging algorithms
Lower bounds for sorting and merging
Straight insertion sort
Quicksort
Heapsort
Merging and mergesort
Linear-time 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
Red-black trees
B-trees
Skip lists
Splay trees
- Data compression algorithms
Huffman compression
Lempel-Ziv compression
- Number-theoretic algorithms
RSA data encryption
Primality testing
- String matching algorithms
String matching with finite automata
The Knuth-Morris-Pratt algorithm
The Boyer-Moore algorithm
- The FFT and applications
The FFT
Polynomial multiplication
- NP completeness
Polynomial-time 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", Addison-Wesley, 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
NP-completeness
NP-complete problems
References in Complexity Theory:
-
J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory,
Languages and Computation , Addison-Wesley, 1979.
Chapters 7,8,12,13.
-
H.R.Lewis, C.H.Papadimitriou: Elements of the Theory of
Computation, Prentice-Hall, 1981.
Chapters 4,5,6,7.
-
C.H.Papadimitriou: Computational Complexity, Addison-Wesley, 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