Explore

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Approx. 14 hours to complete

Save Course

Go to Course

Course Summary

Learn about NP-Complete problems and algorithms to solve them in this course. Gain a deep understanding of theoretical computer science concepts and how they apply to real-world problems.

Key Learning Points

Understand the theory behind NP-Complete problems and how to identify them
Learn about different algorithms to solve NP-Complete problems
Apply these algorithms to real-world problems and analyze their efficiency

Learning Outcomes

Identify NP-Complete problems and understand their theoretical complexity
Implement and analyze different algorithms to solve NP-Complete problems
Apply these algorithms to real-world problems and evaluate their efficiency

Prerequisites or good to have knowledge before taking this course

Basic understanding of computer science concepts
Familiarity with programming languages such as Python

Course Difficulty Level

Intermediate

Course Format

Self-paced
Online
Video Lectures
Assignments and Quizzes

Similar Courses

Algorithms, Part I
Algorithms, Part II

Related Education Paths

Notable People in This Field

Scott Aaronson
Christos Papadimitriou

Related Books

Description

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).

Outline

Week 1
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
Week 1 Overview
Overview, Resources, and Policies
Lecture Slides
Optional Theory Problems (Week 1)
Problem Set #1
Programming Assignment #1

Week 2
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
Week 2 Overview
Optional Theory Problems (Week 2)
Problem Set #2
Programming Assignment #2

Week 3
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
Week 3 Overview
Problem Set #3
Programming Assignment #3

Week 4
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
Week 4 Overview
Optional Theory Problems (Week 4)
Info and FAQ for final exam
Problem Set #4
Programming Assignment #4
Final Exam

Summary of User Reviews

Learn about NP-complete algorithms with this highly-rated course from Coursera. Users have praised the challenging content and insightful lectures, making it a great resource for expanding your knowledge. However, some users have noted that the course may be difficult for beginners to grasp.

Key Aspect Users Liked About This Course

Insightful lectures

Pros from User Reviews

Challenging content that expands your knowledge
Clear and concise explanations from the instructor
Great for those looking to deepen their understanding of algorithms

Cons from User Reviews

May be difficult for beginners to understand
Can be time-consuming to complete
Course material may be outdated
Some users felt that the assignments were too difficult

Recommended for you

The Complete Data Structures and Algorithms Course in Python

Data Structures and Algorithms from Zero to Hero and Crack Top Companies 100+ Interview questions (Python Coding) After finishing this course, you will be able to:...

Save Course