关于此课程： 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.
制作方： Stanford University
教学方： Tim Roughgarden, Professor
Computer Science
| 基本信息 | 课程 4（共 4 门，Algorithms Specialization ） |
| 级别 | Intermediate |
| 承诺学习时间 | 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
- 视频: Single-Source Shortest Paths, Revisted
- 视频: 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
- 视频: Polynomial-Time Solvable Problems
- 视频: 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
- 视频: A Greedy Knapsack Heuristic
- 视频: 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 I
- 视频: 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.
制作方
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.
价格
| 购买课程 | |
|---|---|
| 访问课程材料 | 可用 |
| 访问评分的材料 | 可用 |
| 收到最终成绩 | 可用 |
| 获得可共享的课程证书 | 可用 |
评分和审阅
tough course
Thanks a lot. It is time consuming, need a lot of thinking and practising to finish the homework. And it is worth taking. After this, we can go deep into cs.
unlike previous 3 courses
some of course 4's quiz problems are really difficult and not sure how to approach...
DK
nice challenging problems, good algo design practice