CSC2414F Topics in Applied Discrete Mathematics Fall 1998 =============================================== ========= Instructor: Daniel Panario. ========== e-mail: daniel@cs.toronto.edu ====== Office: SF3302C ====== Lectures: Thursdays 2:00--4:00, place SS1078 ======== This year's topic for the course is: Mathematics for the analysis of algorithms. As presented in the new page of Analysis of Algorithms (http://pauillac.inria.fr/algo/AofA): 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. Prerrequisities: =============== mathematical maturity is required; courses in analysis, algebra, discrete mathematics, combinatorics and data structures may be useful. 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. We intend to distribute notes of the lectures. Students attending this course (either for credits or auditing) will be asked to type notes in LaTeX (once for all the term). 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 2 Real asymptotics 1 Symbolic method, examples 3 Complex asymptotics 2.5 Hashing 1.5 Limit distributions 1 Polynomials over finite fields 1 Decomposable structures, schemas 1 -------- 13 Marking Scheme: ============== 3 Assignments at 15% each 45% 1 Minor project at 5% 5% 1 Major project at 40% 40% 1 Oral presentation at 10% 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 1 page long. A list of suggested topics for the major project will be given by October 15. 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 30 minutes and will verse in the student's project. Web page: ======== http://www.cs.toronto.edu/~daniel/teaching/2414/index.html Schedule: ======== First lecture - Sep 17 Assignment Hand-out Date Due Date ---------- ------------- -------- 1 Sep 24 Oct 8 2 Oct 22 Nov 12 3 Nov 12 Nov 26 Minor project - October 30 Last lecture - December 10 Oral presentation - December 14-18, 1998 Major project - December 18, 1998 The deadlines for assignments, and minor and major projects 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.