À propos de ce cours : The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).

Les destinataires de ce cours : Learners with at least a little bit of programming experience who want to learn the essentials of algorithms. In a University computer science curriculum, this course is typically taken in the third year.

Créé par : Stanford University

Enseigné par : Tim Roughgarden, Professor
Computer Science

Informations de base	Cours 4 de 4 dans Algorithms Specialization
Niveau	Intermédiaire
Engagement	4 weeks of study, 4-8 hours/week
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

Programme de cours

SEMAINE 1

Week 1

The Bellman-Ford algorithm; all-pairs shortest paths.

14 vidéos, 4 lectures

Reading: Week 1 Overview
Reading: Overview, Resources, and Policies
Reading: Lecture Slides
Vidéo: Optimal Substructure
Vidéo: The Basic Algorithm I
Vidéo: The Basic Algorithm II
Vidéo: Detecting Negative Cycles
Vidéo: A Space Optimization
Vidéo: Internet Routing I [Optional]
Vidéo: Internet Routing II [Optional]
Vidéo: Problem Definition
Vidéo: Optimal Substructure
Vidéo: The Floyd-Warshall Algorithm
Vidéo: A Reweighting Technique
Vidéo: Johnson's Algorithm I
Vidéo: Johnson's Algorithm II
Reading: Optional Theory Problems (Week 1)

Noté: Problem Set #1

Noté: Programming Assignment #1

SEMAINE 2

Week 2

NP-complete problems and exact algorithms for them.

11 vidéos, 2 lectures

Reading: Week 2 Overview
Vidéo: Reductions and Completeness
Vidéo: Definition and Interpretation of NP-Completeness I
Vidéo: Definition and Interpretation of NP-Completeness II
Vidéo: The P vs. NP Question
Vidéo: Algorithmic Approaches to NP-Complete Problems
Vidéo: The Vertex Cover Problem
Vidéo: Smarter Search for Vertex Cover I
Vidéo: Smarter Search for Vertex Cover II
Vidéo: The Traveling Salesman Problem
Vidéo: A Dynamic Programming Algorithm for TSP
Reading: Optional Theory Problems (Week 2)

Noté: Problem Set #2

Noté: Programming Assignment #2

SEMAINE 3

Week 3

Approximation algorithms for NP-complete problems.

6 vidéos, 1 lecture

Reading: Week 3 Overview
Vidéo: Analysis of a Greedy Knapsack Heuristic I
Vidéo: Analysis of a Greedy Knapsack Heuristic II
Vidéo: A Dynamic Programming Heuristic for Knapsack
Vidéo: Knapsack via Dynamic Programming, Revisited
Vidéo: Ananysis of Dynamic Programming Heuristic

Noté: Problem Set #3

Noté: Programming Assignment #3

SEMAINE 4

Week 4

Local search algorithms for NP-complete problems; the wider world of algorithms.

11 vidéos, 3 lectures

Reading: Week 4 Overview
Vidéo: The Maximum Cut Problem II
Vidéo: Principles of Local Search I
Vidéo: Principles of Local Search II
Vidéo: The 2-SAT Problem
Vidéo: Random Walks on a Line
Vidéo: Analysis of Papadimitriou's Algorithm
Vidéo: Stable Matching [Optional]
Vidéo: Matchings, Flows, and Braess's Paradox [Optional]
Vidéo: Linear Programming and Beyond [Optional]
Vidéo: Epilogue
Reading: Optional Theory Problems (Week 4)
Reading: Info and FAQ for final exam

Noté: Problem Set #4

Noté: Programming Assignment #4

Noté: Final Exam

FAQ

Quand aurai-je accès aux vidéos de cours et aux devoirs ?

Que dois-je faire si j'ai besoin de plus de temps pour terminer le cours ?

À quoi ai-je droit si je paie ce cours ?

Puis-je suivre ce cours gratuitement ?

Quelle est la politique de remboursement ?

Une aide financière est-elle disponible ?

Comment cela fonctionne

Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from Your Peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

Créateurs

Stanford University

The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is an American private research university located in Stanford, California on an 8,180-acre (3,310 ha) campus near Palo Alto, California, United States.

Tarification

	Acheter le cours
Accéder au contenu du cours	Disponible
Accéder au contenu noté	Disponible
Recevoir une Note Finale	Disponible
Obtenir un Certificat de Cours partageable	Disponible

Notation et examens

Note moyenne 4.8 sur 5 sur 316 notes

Really happy to finish this specialization and I will still study algorithms in the future.

Excellent course! Bravo to the teacher for the commitment provided in this course. Kind regards.

A very nice introduction to algorithms from a high-level mathematical perspective. This course is great for building intuition about key concepts. Highly recommended. I did the Princeton algorithms course first. Both are great. The first tests one more on the implementation side and requires Java. This course is more focused on theory and a great complement. Too bad there is not a Part 5, 6, ….