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.