Welcome to Week 6 of Analysis of Algorithms. This week we complete our survey of important combinatorial classes and applications in the analysis of algorithms.

Lecture 8: Strings and Tries. From DNA sequences to web indices, strings (sequences of characters) are ubiquitous in modern computing applications, so we use analytic combinatorics to study their basic properties and then introduce the trie, an essential and fundamental structure not found in classical combinatorics.

Lecture 9: Words and Mappings. We view strings as sets of characters or as functions from [1..N] to [1..M] to study classical occupancy problems and their application to fundamental hashing algorithms. Functions from [1..N] to [1..N] are mappings, which have an interesting and intricate structure that we can study with analytic combinatorics.

RS

Fri 15 Apr 2016 6:00 PM CEST

Welcome to Week 5 of Analysis of Algorithms. This week we address two familiar and fundamental combinatorial structures and the use of analytic combinatorics to study them, including coverage of several applications.

Lecture 6: Trees. The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications. You can find broad coverage in the textbook, but the lecture focuses on the use of analytic combinatorics to enumerate various types of trees and study parameters

Lecture 7: Permutations.The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.

RS

Fri 8 Apr 2016 6:00 PM CEST

Welcome to Week 4 of Analysis of Algorithms. On Friday at noon EDT, we will release the lectures for this week, which introduce classical approximation methods and then our main topic.

Lecture 4: Asymptotics. Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.

Lecture 5: Analytic Combinatorics. With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods that we have been considering. We introduce unlabeled and labelled combinatorial classes and motivate our basic approach to studying them, with numerous examples.

RS

Fri 1 Apr 2016 6:00 PM CEST

Welcome to Week 3 of Analysis of Algorithms. On Friday at noon EDT, we will release the lecture for this week, which covers a classical approach to solving recurrences.

Lecture 3: Generating Functions. Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.

RS

Fri 25 Mar 2016 5:00 PM CET

Welcome to Week 2 of Analysis of Algorithms. On Friday at noon EDT, we will release the lecture for this week, which surveys a basic mathematical tool that has been used for scientific studies for centuries and is a natural starting point for the analysis of algorithms.

Lecture 2: Recurrences. We begin the course with an overview of recurrence relations, which provide us with a direct mathematical model for the analysis of algorithms.
We finish by examining the fascinating oscillatory behavior of the divide-and-conquer recurrence corresponding to the mergesort algorithm and the general "master theorem" for related recurrences.

RS

Fri 18 Mar 2016 5:00 PM CET

Welcome to Week 1 of Analysis of Algorithms. Each Friday at noon EDT, we will release the course materials for the week: lectures and two sets of exercises and experiments. After three weeks, we will pick up the pace and do two lectures at a time. The exercises are not to be submitted or graded and the experiments are optional---both are for self-assessment and to focus discussion in the forums. 

Each lecture corresponds to a chapter in An Introduction to the Analysis of Algorithms, 2nd edition, so everyone is encouraged to study the corresponding chapter in conjunction with the lectures. The coverage in the book is somewhat encyclopedic, so I am only expecting that people will turn to the material associated with what's in the lecture, perhaps scanning through the rest to see what's there and perhaps find something else of interest.

We begin our course with an overview of the use of the scientific method for studying algorithm performance, one of the motivating applications for analytic combinatorics.

Lecture 1: Analysis of Algorithms. We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort. The lecture concludes with a discussion of some resources that you might find useful during this course.

RS

Fri 11 Mar 2016 6:00 PM CET

Welcome to Analysis of Algorithms. This is Week 0 of the course, where we give everyone a chance to take a look at the course materials and to prepare for delving into the analysis of algorithms.

The video From Analysis of Algorithms to Analytic Combinatorics: A Journey with Philippe Flajolet is now available on the course website. It is an optional overview that tries to answer the question "What is Analytic Combinatorics" and to give some historical perspective.

If you are completely new to the material, you might wish to skip this video or come back to it later on. Most of it is covered, at a much slower pace, later in the course. 

We will begin next week with our first lecture, corresponding to Chapter 1 in An Introduction to the Analysis of Algorithms, 2nd edition. You might wish to read the preface to the book and access the booksite to prepare for that lecture.

RS

Fri 4 Mar 2016 6:00 PM CET

Thanks for enrolling in my course Analysis of Algorithms. I'm excited to let you know that the course will get started this Friday with an overview; then the lectures will start the following Friday and will run for six weeks. You can review the syllabus and schedule to see what's coming. I'll also send weekly announcements summarizing what's to happen each week.

The course is based on a variety of materials:

• The lecture videos and lecture slides.
  
  
• The textbook An Introduction to the Analysis of Algorithms, 2nd edition, our basic reference. Although the lectures are designed to be self-contained, the textbook provides thorough coverage of the material. Addison-Wesley is offering Coursera students a 35% discount when purchased from InformIT. To receive the discount, enter the code COURSERA during checkout.
  
  
• The booksite, which is open to everyone and contains a wealth of supplementary information, including synopses of the textbook, answers to some exercises, code, and other resources.
  
  
• Selected exercises from the textbook, which are also released each week in the lecture slides, the booksite and the Coursera site. These are for self-assessment and to focus discussion in the forums.
  
  
• Optional experiments, usually introduced in the lecture slides and also released each week in the booksite and the Coursera site. Again, these are for self-assessment and to focus discussion in the forums.
  

To maximize your learning outcome in this course, you should get in the mindset of being an active participant who solves problems, studies the available resources, and engages in the discussion forums, as opposed to a passive participant who just watches the lectures. I don't plan any online assessments, but expect that the forums will provide some help for people who have trouble completing the assignments.

Best of luck,
RS

Wed 2 Mar 2016 6:00 AM CET

All video recordings, assessments and other materials made available in connection with this course are subject to copyright protection and may be used only for private study by persons who are enrolled in this course. Any other use of these materials must be with the express, written permission of Robert Sedgewick.

No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

Fri 11 Sep 2015 6:00 PM CEST