Общая
Пройти курс Algorithms: Design and Analysis, Part 2 by Tim Roughgarden на Coursera
Продолжаю изучать алгоритмы с учётом опыта полученного в первой части. А опыт сей подсказывает что нужно читать попутно книгу Introduction to Algorithms (Third Edition), потому как мне одних лекций не хватает по не которым темам. И не откладывать просмотр лекций и выполнение задания на последний момент.
Критерий завершения
Получен сертификат
Личные ресурсы
Немного времени
-
Week 1
Topics
- Two Motivating Applications (Sequence Alignment and Internet Routing)
- Selected Review from Part I (Optional)
- Introduction to Greedy Algorithms
- A Scheduling Application
- Prim's Minimum Spanning Tree Algorithm
Homework
- Due April 5:
- Problem Set #1: Greedy algorithms and MSTs
- Programming Assignment #1: Greedy scheduling and Prim's MST algorithm
-
Week 2
Topics
- Kruskal's Minimum Spanning Tree Algorithm
- Clustering
- Advanced Topics: On the Union-Find Data Structure
- Huffman Codes
Homework
- Due April 12:
- Problem Set #2: More MSTs, and Huffman codes
- Programming Assignment #2: Clustering
-
Week 3
Topics
- Dynamic Programming and Applications
- The Knapsack Problem
- Sequence Alignment
- Optimal Search Trees
Homework
- Due April 19:
- Problem Set #3: Dynamic Programming
- Programming Assignment #3: The Knapsack Problem
-
Week 4
Topics
- More Dynamic Programming and Shortest Paths
- SIngle-Source Shortest Paths, Revisited
- The Bellman-Ford Algorithm
- Internet Routing
- The All-Pairs Shortest Paths Problem
- The Floyd-Warshall Algorithm
- Johnson's Algorithm
Homework
- Due April 26:
- Problem Set #4: Shortest Paths
- Programming Assignment #4: All-Pairs Shortest Paths
-
Week 5
Topics
- P, NP, and What They Mean
- Reductions Between Problems
- NP-Complete Problems
- The P vs. NP Problem
- Solvable Special Cases of NP-Complete Problems
- Smarter (But Still Exponential-Time) Search Algorithms for NP-Complete Problems
Homework
- Due May 3:
- Problem Set #5: NP-Complete Problems and Smarter Search Algorithms for Them
- Programming Assignment #5: The Traveling Salesman Problem
-
Week 6
Topics
- Heuristics with Provable Guarantees
- Greedy and Dynamic Programming Heuristics for the Knapsack Problem
- Local Search: General Principles, Max Cut, and 2SAT
Homework
- Due May 10:
- Problem Set #6: Approximation Algorithms and Local Search
- Programming Assignment #6: 2SAT
-
Final Exam
Не пропустите новые записи!
Подпишитесь на цель и следите за ее достижением
