



Computer Science 690 







Location and time 
Monday and Wednesday, 8:3010am. Lectures start on Wednesday, August 28, 2024 and run until Wednesday, December 4, 2024. No lectures on October 14 and 16 (reading break). There won't be any lectures on Monday, September 2 (Labour Day), The lectures of September 9 and 11 will be replaced. There will be lectures on Friday, September 6 and 20, from 8:30 until 10 am instead. 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. The Fourth Edition of this book, without Erös, was published in 2016. B. Bollobas, Random Graphs, Academic Press, New York, 1985. Second edition from 2001. 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. 


