CSC497/590Y Mathematical Analysis of Algorithms Winter 2002 =========== =================================== =========== Instructor: Daniel Panario. ========== e-mail: daniel@math.carleton.ca ====== Office: HP 4372 ====== Lectures: Mondays 11:30 - 13:00 and Thursdays 13:00 - 14:30, place 4342 ME ======== Mathematics for the analysis of algorithms is presented in the page of Analysis of Algorithms (http://pauillac.inria.fr/algo/AofA) as: Analysis of Algorithms is a field in Computer Science whose overall goal is an understanding of the complexity of algorithms. (...) The subject was founded by D. Knuth (who coined the term "analysis of algorithms" in the mid-sixties), and is well illustrated by his monumental series, "The Art of Computer Programming". The field entertains close ties with a number of areas like discrete mathematics, combinatorial analysis, probability theory, analytic number theory, asymptotic analysis, complexity theory and sometimes statistical physics. This course will cover mathematical tools for analyzing algorithms. The focus will be on simple algorithms where big-Oh worst-case bounds are easy to derive. Some possible algorithms are quicksort, hashing techniques, random mappings, simple integer factorization methods. The full analysis of these algorithms is more involved. What we have in mind here are studies such as average-case analysis, deviations from these means, probability properties that explain the behavior of the algorithms, and so on. The study of these algorithms will serve as a justification for presenting some useful techniques in the analysis of algorithms: the symbolic method and asymptotic analysis tools. The symbolic method allows the study of combinatorial properties of the algorithms by means of generating functions. The extraction of coefficients is then done using asymptotic analysis techniques based on real and complex analysis. Prerequisities: =============== mathematical maturity is required; courses in analysis, algebra, discrete mathematics, combinatorics and data structures are useful. Courses like 69.384 and 70.385 would be appropriate prerequisites. Textbooks: ========= there is no textbook for the course. We will take material from several papers, and from the books below. 1. P. Flajolet and R. Sedgewick, "Analytic Combinatorics", Addison-Wesley, Reading, MA, in preparation. 2. R. Sedgewick and P. Flajolet, "An Introduction to the Analysis of Algorithms", Addison-Wesley, Reading, MA, 1996. 3. D.E. Knuth, "The art of computer programming, vol.1: fundamental algorithms", Addison-Wesley, Reading, MA, (3rd Ed.) 1997. 4. D.E. Knuth, "The art of computer programming, vol.2: seminumerical algorithms", Addison-Wesley, Reading, MA, (3rd Ed.) 1997. 5. D.E. Knuth, "The art of computer programming, vol.3: sorting and searching", Addison-Wesley, Reading, MA, (2nd Ed.) 1998. Other texts for consult: ======================= 1. R. Graham, D.E. Knuth and O. Patashnik, "Concrete Mathematics", Addison-Wesley, Reading, MA, (2nd Ed.) 1994. 2. D.H. Greene and D.E. Knuth, "Mathematics for the analysis of algorithms", Birkhauser, Boston, (3rd Ed.) 1990. 3. W. Szpankowski, "Average-case analysis of algorithms on sequences", Wiley Interscience Series in Discrete Mathematics, 2001. We intend to distribute notes of the lectures. Most material is ready and will be distributed before we teach the lecture covering that material. Some students attending this course may be asked to type notes in LaTeX of some classes. A teacher advises his students: "Be a scribe! It saves you from toil and protects you from all kinds of work. It spares you from using hoe and mattock, that you need not carry a basket. It keeps you from wielding the oar and spares you torment, so that you are not subject to many masters and endless bosses. ...Now the scribe, he directs all the work in this land." Tomb Inscription, Valley of the Kings, 1300 B.C. R. Gore, "Ramses the Great", National Geographic #179 (1991) pp. 2--31 Course Outline (tentative): ========================== Topic Approx. number of weeks ---------------------------------- ----------------------- Introduction, sorting, recurrences 1.5 Generating functions 1.5 Real asymptotics 2 Symbolic method, examples 3 Complex asymptotics 1.5 Hashing 1 Random mappings, integer factorization 1 Polynomials over finite fields 1 -------- 12.5 Marking Scheme: ============== 3 Assignments at 15% each 45% Participation in class 5% 1 Minor project (abstract) 5% 1 Major project (10 pages) 35% 1 Oral presentation 10% -------- 100% The minor project is a brief description of the topic intended for the project including the student approach to the work as well as bibliographic references. It should be less than 1 page. A list of suggested topics for the major project will be given in February. This list is not intended as a complete account of the possibilities. In particular, students are ENCOURAGED to find project topics that suit better their interests. In this case, the student MUST consult and discuss the project topic with the lecturer. The oral presentation will last 25 minutes (plus 5 minutes for questions), and will verse in the student's project. Web page: ======== http://www.math.carleton.ca/~daniel/teaching/497/index.html Schedule: ======== First lecture - Monday January 7, 2002 Winter break - February 18 - 22, 2002 Last lecture - Monday April 1, 2002 Remark: the lectures of Thursday January 3 and Thursday April 4 will be taught at a different date (during February). Assignment Hand-out Date Due Date ---------- ------------- -------- 1 Jan 24 Feb 14 2 Feb 14 Mar 14 3 Mar 14 Apr 3 Minor project deadline - Thursday March 7, 2002 Major project deadline - Wednesday April 10, 2002 Oral presentation - April 11-12, 2002 The deadlines for assignments and minor project are not firm. Work handed-in some days after the deadline will carry no penalties. However, the student must agree with the lecturer on a new deadline for the work.