CSC2420 (Algorithm Design, Analysis and Theory) Home Page (Spring 2012)

This page will provide WWW access to various documents concerning CSC2420. Announcements will also be made on this page. This page will become more current when the spring 2012 term begins. The class will be held Mondays 10-12 in BA 3012. Please consult the CSC 2420 Fall 2010 web page for lecture notes from that term.

Announcements for week of April 23.

I made some change to part (b) of question 1. I hope that there are no further changes to problem set 3 (still due this Wed) and I apologize for all the previous changes. I am not scheduling any specific office hours this week but I am in this week and usually will be in my office. You can drop by whenever. If you want to be sure to see me then email me with some suggested times.

Please send any comments or questions to the instructor:

bor..at..cs.toronto.edu

This course is the second offering of a new graduate level introduction to the design and analysis of algorithms. The course will serve as a foundational course, appropriate for students in computer science, computer engineering, and mathematics. However, the course should also be of interest to ``theory students'' looking for research topics. We will begin with topics normally discussed in undergraduate courses such as our CSC373/CSC375 using some less standard examples and also discussing some precise models for standard algorithmic paradigms such as greedy, local search and dynamic programming algorithms. Other possible topics include: randomized algorithms and Markov chains, linear and submodular maximization subject to independence constraints, LP and SDP relaxations, primal dual algorithms, online primal dual algorithms, sublinear time algorithms, embedding techniques, data stream algorithms, multiplicative weights algorithms, spectral methods, algorithmic aspects of mechanism design, social networks and information retrieval.

We will not use any one text book for this course. There are a number of excellent undergraduate texts (e.g. "Algorithm Design" by Jon Kleinberg and Eva Tardos; "Introduction to Algorithms" by Corman, Leiserson, Rivest and Stein; ``Algorithmics: Theory and Practice" by Brassard and Bratley; and "Algorithms" by DsGupta, Papadimitriou and U. Vazirani) that cover the standard topics and include advanced material. There are also a number of texts on somewhat specialized topics (e.g. "Approximation Algorithms" by V. Vazirani; "A First Course in Combinatorial Optimization", by James Lee; and "Randomized Algorithms" by Motwani and Raghaven). There are also many web accessible courses that indicate the diversity of topics taught in graduate algorithms courses. For example, you may want to consider the following sources: http://www.cs.washington.edu/education/courses/521, http://www.cs.washington.edu/education/courses/522, http://math.mit.edu/~goemans/18433.html, http://stellar.mit.edu/S/course/18/fa08/18.415/index.html, http://www.cs.cornell.edu/courses/cs6820/2009fa/, http://www.cs.cmu.edu/~avrim/451f09/index.html. http://pages.cs.wisc.edu/~shuchi/courses/880-S07/#lect

Lecture outlines will be posted here