



Computer Science 690 








Wednesday, Friday 8:3010am. Lectures start on Wednesday, September 1, 2021 and run officially until Friday, December 3, 2021. The December 1 and December 3 lectures are moved to November 1 and 15, respectively, same place, same time. We meet in McConnell 103. Course notes will be handed out in class. A bit of what happened between March 2020 and August 2021: Realizing that live lectures are far superior to virtual lectures (for clarity, feedback, mental health, entertainment, blood pressure and social happiness), and that outdoor spaces beat indoor spaces in our fight against the spread of covfefe, I asked McGill's politburo for permission to hold live lectures under an open tent or canopy on the lower campus. The proposal was approved at all levels (with thanks to the School of Computer Science and the Faculty of Science) and then coldbloodedly killed by the central Kommandaturan obscure committee called the EOC (Emergency Operations Centre). A request to teach outdoors in 2021 without a tent was also declined. We are forced to teach inside and McGill University insists that unvaccinated students should be allowed to mingle with the rest, a decision that is medically illadvised, legally troublesome, and ethically corrupt. [Those responsible for that decision include Christopher Manfredi, Christopher Buddle and Fabrice Labeau.] I will teach, but I will ask the students to please please please be careful and mindful. 

















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. 


