



Computer Science 690 







Location and time 
Monday and Wednesday, 8:3010am. Lectures start on Wednesday, August 30, 2023 and run officially until Monday, December 4, 2023. No lectures on October 9 and 11 (reading break). There won't be any lectures on Monday, September 4 (Labour Day), but there is an extra lecture on November 30, same place, same time. We meet in McConnell 321 (the lounge). Course notes will be handed out in class. 







Contents 


Evaluation 
About nine sets of theoretical problems will be assigned. 

Textbook 
There is no specific textbook. Course notes will be handed out. 

Selected references 
Some references are given below. N. Alon, J. Spencer, and P. Erdös, The Probabilistic Method, John Wiley, New York, 1992. B. Bollobas, Random Graphs, Academic Press, New York, 1985. L. Devroye, "Branching processes in the analysis of the heights of trees," Acta Informatica, vol. 24, pp. 277298, 1987. L. Devroye, "Applications of the theory of records in the study of random trees," Acta Informatica, vol. 26, pp. 123130, 1988. S. Janson, T. Luczak, A. Rucinski, Random Graphs, WileyInterscience, New York, 2000. R. M. Karp, "The probabilistic analysis of some combinatorial search algorithms," in: Algorithms and Complexity, ed. J. F. Traub, pp. 119, Academic Press, New York, 1976. R. M. Karp and J. M. Steele, "Probabilistic analysis of heuristics," in: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, pp. 181205, John Wiley, New York, 1985. D. E. Knuth, The Art of Computer Programming, Vol. 3 : Sorting and Searching, AddisonWesley, Reading, Mass, 1973. H. M. Mahmoud, Evolution of Random Search Trees, John Wiley, New York, 1992. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. E. M. Palmer, Graphical Evolution, John Wiley, New York, 1985. J. Pearl, Heuristics. Intelligent Search Strategies for Computer Problem Solving (Chapter 5), AddisonWesley, Reading, Mass, 1984. W. Szpankowski, Average Case Analysis of Algorithms on Sequences, SpringerVerlag, New York, 2001. J. S. Vitter and P. Flajolet, "Averagecase analysis of algorithms and data structures," in: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, ed. J. van Leeuwen, pp. 431524, MIT Press, Amsterdam, 1990. 


