This course is offered through Coursera — you can add it to your Accredible profile to organize your learning, find others learning the same thing and to showcase evidence of your learning on your CV with Accredible's export features.
Course Date: 05 September 2014 to 17 October 2014 (6 weeks)
This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton, where he was the founding chair of the Department of Computer Science. He received the Ph.D. degree from Stanford University, in 1975. Prof. Sedgewick also served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Palo Alto, CA, Institute for Defense Analyses, Princeton, NJ, and INRIA, Rocquencourt, France. He is a member of the board of directors of Adobe Systems. Prof. Sedgewick's interests are in analytic combinatorics, algorithm design, the scientific analysis of algorithms, curriculum development, and innovations in the dissemination of knowledge. He has published widely in these areas and is the author of several books.
Analysis of Algorithms aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the scientific analysis of algorithms in computer science and for the study of scientific models in many other disciplines, including probability theory, statistical physics, computational biology and information theory. This course covers recurrence relations, generating functions, asymptotics, and fundamental structures such as trees, permutations, strings, tries, words, and mappings, in the context of applications to the analysis of algorithms.
Does Princeton award credentials or reports regarding my work in this course?
No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.
Lecture 1 Analysis of Algorithms
Lecture 2 Recurrences
Lecture 3 Solving recurrences with GFs
Lecture 4 Asymptotics
Lecture 5 The symbolic method
Lecture 6 Trees
Lecture 7 Permutations
Lecture 8 Strings and Tries
Lecture 9 Words and Mappings
There will be one lecture (about 80 minutes) and a problem set each week.