Об этом курсе: 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
| Основные сведения | Курс 4 из 4 — Algorithms Specialization |
| Уровень | Учащийся среднего уровня |
| Выполнение | 4 weeks of study, 4-8 hours/week |
| Язык | Английский |
| Как пройти курс | Чтобы пройти курс, выполните все оцениваемые задания. |
| Оценки пользователей |
Программа курса
НЕДЕЛЯ 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.
Стоимость
| Приобрести курс | |
|---|---|
| Получить доступ к материалам курса | Доступен |
| Получить доступ к оцениваемым материалам курса | Доступен |
| Получить итоговую оценку | Доступен |
| Получите сертификат о прохождении курса, ссылкой на который можно делиться с другими людьми | Доступен |
Рейтинги и отзывы
This is the most challenging course in this specialization. Assignments as well as test questions require good amount of thinking.
One of the best courses I did on Coursera.
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.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
b
Great material!