Analysis of Algorithms

Offered By

Analysis of Algorithms

Princeton University

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.... 

100% online courses

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Advanced Level

Approx. 25 hours to complete

Suggested: 7 hours/week...

English

Subtitles: English...

100% online courses

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Advanced Level

Approx. 25 hours to complete

Suggested: 7 hours/week...

English

Subtitles: English...

Syllabus - What you will learn from this course

Week

2 hours to complete

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....

4 videos (Total 76 min), 2 readings, 1 quiz

4 videos

History and Motivation11m

A Scientific Approach 16m

Example: Quicksort 30m

Resources 17m

2 readings

Getting Started10m

Exercises from Lecture 110m

1 practice exercise

Analysis of Algorithms4m

Week

2 hours to complete

Recurrences

We begin this lecture with an overview of recurrence relations, which provides 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....

5 videos (Total 71 min), 1 reading, 3 quizzes

5 videos

Computing Values10m

Telescoping15m

Types of Recurrences 12m

Mergesort 18m

Master Theorem 14m

1 reading

Exercises from Lecture 210m

3 practice exercises

Pop Quiz on Telescoping2m

Pop Quiz on the Master Theorem2m

Recurrences4m

Week

2 hours to complete

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....

5 videos (Total 84 min), 1 reading, 1 quiz

5 videos

Ordinary Generating Functions16m

Counting with Generating Functions27m

Catalan Numbers14m

Solving Recurrences18m

Exponential Generating Functions7m

1 reading

Exercises from Lecture 310m

1 practice exercise

Generating Functions6m

Week

2 hours to complete

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....

4 videos (Total 83 min), 1 reading, 1 quiz

4 videos

Standard Scale18m

Manipulating Expansions 19m

Asymptotics of Finite Sums 16m

Bivariate Asymptotics 28m

1 reading

Exercises from Lecture 410m

1 practice exercise

Asymptotics4m

Instructor

Robert Sedgewick

William O. Baker *39 Professor of Computer Science

Computer Science

About Princeton University

Princeton University is a private research university located in Princeton, New Jersey, United States. It is one of the eight universities of the Ivy League, and one of the nine Colonial Colleges founded before the American Revolution....

Frequently Asked Questions

When will I have access to the lectures and assignments?
Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.
What will I get if I purchase the Certificate?
When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.
What is the refund policy?
Is financial aid available?
Can I earn a certificate in this course?
No. As per Princeton University policy, no certificates, credentials, or reports are awarded in connection with this course.

More questions? Visit the Learner Help Center.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.