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

4 vidéos, 2 lectures

Reading: Getting Started
Vidéo: A Scientific Approach
Vidéo: Example: Quicksort
Vidéo: Resources
Reading: Exercises from Lecture 1
Discussion Prompt: Exercises from Lecture 1

Noté: Analysis of Algorithms

SEMAINE 2

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 vidéos, 1 lecture, 2 quiz pour s'exercer

Vidéo: Telescoping
Practice Quiz: Pop Quiz on Telescoping
Vidéo: Types of Recurrences
Vidéo: Mergesort
Vidéo: Master Theorem
Practice Quiz: Pop Quiz on the Master Theorem
Reading: Exercises from Lecture 2
Discussion Prompt: Exercises from Lecture 2

Noté: Recurrences

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

5 vidéos, 1 lecture

Vidéo: Counting with Generating Functions
Vidéo: Catalan Numbers
Vidéo: Solving Recurrences
Vidéo: Exponential Generating Functions
Reading: Exercises from Lecture 3
Discussion Prompt: Exercises from Lecture 3

Noté: Generating Functions

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

4 vidéos, 1 lecture

Vidéo: Manipulating Expansions
Vidéo: Asymptotics of Finite Sums
Vidéo: Bivariate Asymptotics
Reading: Exercises from Lecture 4
Discussion Prompt: Exercises from Lecture 4

Noté: Asymptotics

SEMAINE 5

Analytic Combinatorics

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.

4 vidéos, 2 lectures

Vidéo: Labelled Objects
Vidéo: Coefficient Asymptotics
Reading: Errata
Vidéo: Perspective
Reading: Exercises from Lecture 5
Discussion Prompt: Exercises from Lecture 5

Noté: Analytic Combinatorics

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

4 vidéos, 1 lecture

Vidéo: Binary Search Trees
Vidéo: Path Length
Vidéo: Other Types of Trees
Reading: Exercises from Lecture 6
Discussion Prompt: Exercises from Lecture 6

Noté: Trees

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

5 vidéos, 1 lecture

Vidéo: Sets of Cycles
Vidéo: Left-Right-Minima
Vidéo: Other Parameters
Vidéo: BGFs and Distributions
Reading: Exercises from Lecture 7
Discussion Prompt: Exercises from Lecture 7

Noté: Permutations

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

5 vidéos, 1 lecture

Vidéo: Languages
Vidéo: Tries
Vidéo: Trie Parameters
Vidéo: Exercises
Reading: Exercises from Lecture 8
Discussion Prompt: Exercises from Lecture 8

Noté: Strings and Tries

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

6 vidéos, 1 lecture

Vidéo: Birthday Problem
Vidéo: Coupon Collector Problem
Vidéo: Hash Tables
Vidéo: Mappings
Vidéo: Exercises
Reading: Exercises from Lecture 9
Discussion Prompt: Exercises from Lecture 9

Noté: Strings and Words

Niveau	Avancées
Langue	English
Comment réussir	Réussissez tous les devoirs notés pour terminer le cours.
Notes des utilisateurs	4.8 étoiles Note moyenne des utilisateurs 4.8Voir ce que disent les étudiants