Об этом курсе: 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).
Для кого этот курс: 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.
Автор: Стэнфордский университет
Преподаватели: Tim Roughgarden, Professor
Computer Science
| Основные сведения | Course 4 of 4 in the Algorithms Specialization |
| Уровень | Учащийся среднего уровня |
| Выполнение | 4 weeks of study, 4-8 hours/week |
| Язык | English |
| Как пройти курс | Чтобы пройти курс, выполните все оцениваемые задания. |
| Оценки пользователей |
Программа курса
НЕДЕЛЯ 1
Week 1
The Bellman-Ford algorithm; all-pairs shortest paths.
14 видео, 4 материала для самостоятельного изучения
- Reading: Week 1 Overview
- Reading: Overview, Resources, and Policies
- Reading: Lecture Slides
- Видео: Optimal Substructure
- Видео: The Basic Algorithm I
- Видео: The Basic Algorithm II
- Видео: Detecting Negative Cycles
- Видео: A Space Optimization
- Видео: Internet Routing I [Optional]
- Видео: Internet Routing II [Optional]
- Видео: Problem Definition
- Видео: Optimal Substructure
- Видео: The Floyd-Warshall Algorithm
- Видео: A Reweighting Technique
- Видео: Johnson's Algorithm I
- Видео: Johnson's Algorithm II
- Reading: Optional Theory Problems (Week 1)
Оцениваемый: Problem Set #1
Оцениваемый: Programming Assignment #1
НЕДЕЛЯ 2
Week 2
NP-complete problems and exact algorithms for them.
11 видео, 2 материала для самостоятельного изучения
- Reading: Week 2 Overview
- Видео: Reductions and Completeness
- Видео: Definition and Interpretation of NP-Completeness I
- Видео: Definition and Interpretation of NP-Completeness II
- Видео: The P vs. NP Question
- Видео: Algorithmic Approaches to NP-Complete Problems
- Видео: The Vertex Cover Problem
- Видео: Smarter Search for Vertex Cover I
- Видео: Smarter Search for Vertex Cover II
- Видео: The Traveling Salesman Problem
- Видео: A Dynamic Programming Algorithm for TSP
- Reading: Optional Theory Problems (Week 2)
Оцениваемый: Problem Set #2
Оцениваемый: Programming Assignment #2
НЕДЕЛЯ 3
Week 3
Approximation algorithms for NP-complete problems.
6 видео, 1 материал для самостоятельного изучения
- Reading: Week 3 Overview
- Видео: Analysis of a Greedy Knapsack Heuristic I
- Видео: Analysis of a Greedy Knapsack Heuristic II
- Видео: A Dynamic Programming Heuristic for Knapsack
- Видео: Knapsack via Dynamic Programming, Revisited
- Видео: Ananysis of Dynamic Programming Heuristic
Оцениваемый: Problem Set #3
Оцениваемый: Programming Assignment #3
НЕДЕЛЯ 4
Week 4
Local search algorithms for NP-complete problems; the wider world of algorithms.
11 видео, 3 материала для самостоятельного изучения
- Reading: Week 4 Overview
- Видео: The Maximum Cut Problem II
- Видео: Principles of Local Search I
- Видео: Principles of Local Search II
- Видео: The 2-SAT Problem
- Видео: Random Walks on a Line
- Видео: Analysis of Papadimitriou's Algorithm
- Видео: Stable Matching [Optional]
- Видео: Matchings, Flows, and Braess's Paradox [Optional]
- Видео: Linear Programming and Beyond [Optional]
- Видео: Epilogue
- Reading: Optional Theory Problems (Week 4)
- Reading: Info and FAQ for final exam
Оцениваемый: Problem Set #4
Оцениваемый: Programming Assignment #4
Оцениваемый: Final Exam
Часто задаваемые вопросы
Как это работает
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.
Авторы
Стэнфордский университет
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.
Стоимость
| Приобрести курс | |
|---|---|
| Получить доступ к материалам курса | Доступен |
| Получить доступ к оцениваемым материалам курса | Доступен |
| Получить итоговую оценку | Доступен |
| Earn a shareable Course Certificate | Доступен |
Рейтинги и отзывы
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, ….
Great one for people with advanced understanding! Others will find it slightly hard to follow!
This was the hardest course in this specialization. But the quality of the course material and the instructor's way of explaining kept me engaged and motivated. The problems and the programming assignments were significantly harder than the earlier courses in this specialization - but it felt that much more satisfying after completing the course. Special thanks to Prof. Roughgarden for creating such an amazing course. :-)
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
BG
Excellent course! Bravo to the teacher for the commitment provided in this course. Kind regards.