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

 

Topics in Algorithms:

  1. Algorithm design techniques

  2. Algorithm analysis

  3. Sorting and merging algorithms

  4. Selection algorithms

  5. Searching algorithms

  6. Data compression algorithms

  7. Number-theoretic algorithms

  8. String matching algorithms

  9. The FFT and applications

  10. NP completeness

 

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.


Complexity Theory Portion of Prelim Syllabus

 

Courses in Complexity Theory:

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

  1. MCS 541 Computational Complexity

  2. MCS 542 Theory of Computation II

 

Topics in Complexity Theory:

 

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.


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