About this course: 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).
Who is this class for: 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.
Created by: Stanford University
Taught by: Tim Roughgarden, Professor
Computer Science
| Basic Info | Course 4 of 4 in the Algorithms Specialization |
| Level | Intermediate |
| Commitment | 4 weeks of study, 4-8 hours/week |
| Language | English |
| How To Pass | Pass all graded assignments to complete the course. |
| User Ratings |
Syllabus
WEEK 1
Week 1
The Bellman-Ford algorithm; all-pairs shortest paths.
14 videos, 4 readings
- 阅读: Week 1 Overview
- 阅读: Overview, Resources, and Policies
- 阅读: Lecture Slides
- Video: Optimal Substructure
- Video: The Basic Algorithm I
- Video: The Basic Algorithm II
- Video: Detecting Negative Cycles
- Video: A Space Optimization
- Video: Internet Routing I [Optional]
- Video: Internet Routing II [Optional]
- Video: Problem Definition
- Video: Optimal Substructure
- Video: The Floyd-Warshall Algorithm
- Video: A Reweighting Technique
- Video: Johnson's Algorithm I
- Video: Johnson's Algorithm II
- 阅读: Optional Theory Problems (Week 1)
Graded: Problem Set #1
Graded: Programming Assignment #1
WEEK 2
Week 2
NP-complete problems and exact algorithms for them.
11 videos, 2 readings
- 阅读: Week 2 Overview
- Video: Reductions and Completeness
- Video: Definition and Interpretation of NP-Completeness I
- Video: Definition and Interpretation of NP-Completeness II
- Video: The P vs. NP Question
- Video: Algorithmic Approaches to NP-Complete Problems
- Video: The Vertex Cover Problem
- Video: Smarter Search for Vertex Cover I
- Video: Smarter Search for Vertex Cover II
- Video: The Traveling Salesman Problem
- Video: A Dynamic Programming Algorithm for TSP
- 阅读: Optional Theory Problems (Week 2)
Graded: Problem Set #2
Graded: Programming Assignment #2
WEEK 3
Week 3
Approximation algorithms for NP-complete problems.
6 videos, 1 reading
- 阅读: Week 3 Overview
- Video: Analysis of a Greedy Knapsack Heuristic I
- Video: Analysis of a Greedy Knapsack Heuristic II
- Video: A Dynamic Programming Heuristic for Knapsack
- Video: Knapsack via Dynamic Programming, Revisited
- Video: Ananysis of Dynamic Programming Heuristic
Graded: Problem Set #3
Graded: Programming Assignment #3
WEEK 4
Week 4
Local search algorithms for NP-complete problems; the wider world of algorithms.
11 videos, 3 readings
- 阅读: Week 4 Overview
- Video: The Maximum Cut Problem II
- Video: Principles of Local Search I
- Video: Principles of Local Search II
- Video: The 2-SAT Problem
- Video: Random Walks on a Line
- Video: Analysis of Papadimitriou's Algorithm
- Video: Stable Matching [Optional]
- Video: Matchings, Flows, and Braess's Paradox [Optional]
- Video: Linear Programming and Beyond [Optional]
- Video: Epilogue
- 阅读: Optional Theory Problems (Week 4)
- 阅读: Info and FAQ for final exam
Graded: Problem Set #4
Graded: Programming Assignment #4
Graded: Final Exam
FAQs
How It Works
课程作业
每门课程都像是一本互动的教科书，具有预先录制的视频、测验和项目。
来自同学的帮助
与其他成千上万的学生相联系，对想法进行辩论，讨论课程材料，并寻求帮助来掌握概念。
证书
获得正式认证的作业，并与朋友、同事和雇主分享您的成功。
Creators
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.
Pricing
| Purchase Course | |
|---|---|
| Access to course materials | Available |
| Access to graded materials | Available |
| Receive a final grade | Available |
| Earn a shareable Course Certificate | Available |
Ratings and Reviews
This was definitely a challenging yet extremely rewarding experience. The lectures were top notch. In fact I was taking another algorithms course at the time, but I felt it lacked the necessary proofs and in my opinion just jumped to the conclusion. I tried listening to the lectures from this course and immediately switched over. The projects also trained me to use efficient data structures and be aware of memory management. The quizzes also required in depth understanding of the material, while the discussion forums provided lots useful hints in that regard. Overall, it's definitely a good use of time and I'm glad I completed the entire specialization!
One of the best specializations on this site. Highly recommended!
diffcult
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
SV
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. :-)