Advanced Algorithms and Complexity
- Offered byCoursera
Advanced Algorithms and Complexity at Coursera Overview
Duration | 27 hours |
Start from | Start Now |
Total fee | Free |
Mode of learning | Online |
Difficulty level | Advanced |
Official Website | Explore Free Course  |
Credential | Certificate |
Advanced Algorithms and Complexity at Coursera Highlights
- Shareable Certificate Earn a Certificate upon completion
- 100% online Start instantly and learn at your own schedule.
- Course 5 of 6 in the Data Structures and Algorithms Specialization
- Flexible deadlines Reset deadlines in accordance to your schedule.
- Advanced Level
- Approx. 27 hours to complete
- English Subtitles: Arabic, French, Portuguese (European), Italian, Vietnamese, German, Russian, English, Spanish
Advanced Algorithms and Complexity at Coursera Course details
- You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.
Advanced Algorithms and Complexity at Coursera Curriculum
Flows in Networks
Introduction
Network Flows
Residual Networks
Maxflow-Mincut
The Ford?Fulkerson Algorithm
Slow Example
The Edmonds?Karp Algorithm
Bipartite Matching
Image Segmentation
About University
Slides and Resources on Flows in Networks
Rules on the academic integrity in the course
Available Programming Languages
FAQ on Programming Assignments
Flow Algorithms
Linear Programming
Introduction
Linear Programming
Linear Algebra: Method of Substitution
Linear Algebra: Gaussian Elimination
Convexity
Duality
(Optional) Duality Proofs
Linear Programming Formulations
The Simplex Algorithm
(Optional) The Ellipsoid Algorithm
Slides and Resources on Linear Programming
Linear Programming Quiz
NP-complete Problems
Brute Force Search
Search Problems
Traveling Salesman Problem
Hamiltonian Cycle Problem
Longest Path Problem
Integer Linear Programming Problem
Independent Set Problem
P and NP
Reductions
Showing NP-completeness
Independent Set to Vertex Cover
3-SAT to Independent Set
SAT to 3-SAT
Circuit SAT to SAT
All of NP to Circuit SAT
Using SAT-solvers
Slides and Resources on NP-complete Problems
Minisat Installation Guide
NP-complete Problems
Coping with NP-completeness
Introduction
2-SAT
2-SAT: Algorithm
Independent Sets in Trees
3-SAT: Backtracking
3-SAT: Local Search
TSP: Dynamic Programming
TSP: Branch and Bound
Vertex Cover
Metric TSP
TSP: Local Search
Slides and Resources on Coping with NP-completeness
Coping with NP-completeness
Streaming Algorithms (Optional)
Introduction
Heavy Hitters Problem
Reduction 1
Reduction 2
Basic Estimate 1
Basic Estimate 2
Final Algorithm 1
Final Algorithm 2
Proofs 1
Proofs 2
Quiz: Heavy Hitters
Advanced Algorithms and Complexity at Coursera Admission Process
Important Dates
Other courses offered by Coursera
Student Forum
Anything you would want to ask experts?