URCS Theory Comps Syllabus 


a) Machines, Computability, and Undecidability:
         HMU[8,9], P[2,3], R[14.1-14.3,14.8].

b) Complexity, Completeness, and Reducibility:
         BC[3-5,7,8], P[7-10,14,17].

c) Cryptography:
         P[12], S.

d) Foundations of Algorithms and Their Analysis:
         CLRS[1-5]

e) Advanced Algorithms:
         CLRS[26-35], MR[5.3].

KEY:

BC =   Introduction to the Theory of Complexity, D. Bovet and P.
       Crescenzi, Prentice Hall, 1993.

CLRS = Introduction to Algorithms, 2nd edition, Cormen, Leiserson, 
       Rivest, and Stein, MIT Press and McGraw-Hill Book Company,
       2001.

HMU =  Introduction to Automata and Language Theory, 2nd edition,
       J. Hopcroft, R. Motwani, J. Ullman, Addison-Wesley, 2001.

MR  =  Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge
       University Press, 1995.

P =    Computational Complexity, C. Papadimitriou, Addison-Wesley, 1994.

R =    The Theory of Recursive Functions and Effective Computability,
       H. Rogers, Jr., MIT Press, 1987.

S =    A Survey of One-Way Functions in Complexity Theory, A. Selman,
       Mathematical Systems Theory, 25(3), pp. 203--221, 1992.