UR-CS Comps Syllabus: Theory Spring 2001 (Last modified 2001/01/23/1PM) =============== 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) Parallel algorithms: CLR[28-30]. e) Synchronous Network Algorithms: L[3-7]. f) Asynchronous Shared Memory Algorithms: L[10,12,13]. NOTE: L[12,13] not included in 2000. g) Asynchronous Network Algorithms: L[15]. KEY: BC = Introduction to the Theory of Complexity, D. Bovet and P. Crescenzi, Prentice Hall, 1993. CLR = Introduction to Algorithms, Cormen, Leiserson, and Rivest, MIT Press and McGraw-Hill Book Company, 1990. HMU = Introduction to Automata and Language Theory, 2nd edition, J. Hopcroft, R. Motwani, J. Ullman, Addison-Wesley, 2001. L = Distributed Algorithms, N. Lynch, Kaufmann Publishers, 1996. 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.