Princeton University

Analysis of Algorithms

Taught in English

Some content may not be translated

91,660 already enrolled

Course

Gain insight into a topic and learn the fundamentals

Robert Sedgewick

Instructor: Robert Sedgewick

4.4

(776 reviews)

Advanced level
Designed for those already in the industry
20 hours to complete
3 weeks at 6 hours a week
Flexible schedule
Learn at your own pace

Details to know

Assessments

11 quizzes

See how employees at top companies are mastering in-demand skills

Placeholder

There are 9 modules in this course

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.

What's included

4 videos2 readings1 quiz1 discussion prompt

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.

What's included

5 videos1 reading3 quizzes1 discussion prompt

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.

What's included

5 videos1 reading1 quiz1 discussion prompt

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.

What's included

4 videos1 reading1 quiz1 discussion prompt

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.

What's included

4 videos2 readings1 quiz1 discussion prompt

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.

What's included

4 videos1 reading1 quiz1 discussion prompt

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.

What's included

5 videos1 reading1 quiz1 discussion prompt

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.

What's included

5 videos1 reading1 quiz1 discussion prompt

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.

What's included

6 videos1 reading1 quiz1 discussion prompt

Instructor

Instructor ratings
4.3 (183 ratings)
Robert Sedgewick
Princeton University
7 Courses1,717,500 learners

Offered by

Recommended if you're interested in Algorithms

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

Showing 3 of 776

4.4

776 reviews

  • 5 stars

    62.46%

  • 4 stars

    25.44%

  • 3 stars

    6.68%

  • 2 stars

    1.79%

  • 1 star

    3.59%

HL
5

Reviewed on Mar 9, 2018

AV
5

Reviewed on Aug 24, 2020

SS
5

Reviewed on Feb 11, 2024

New to Algorithms? Start here.

Placeholder

Open new doors with Coursera Plus

Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Frequently asked questions