Course Summary
Learn about advanced algorithms and complexity through this course. Explore topics such as greedy algorithms, dynamic programming, and network flow. Gain skills that can be applied to real-world problems.Key Learning Points
- Learn how to analyze algorithms and understand their complexity
- Explore advanced algorithms such as greedy algorithms and dynamic programming
- Apply skills to real-world problems
Related Topics for further study
Learning Outcomes
- Ability to analyze algorithms and understand their complexity
- Proficiency in advanced algorithms such as greedy algorithms and dynamic programming
- Skills to apply learned concepts to real-world problems
Prerequisites or good to have knowledge before taking this course
- Basic understanding of data structures and algorithms
- Familiarity with a programming language such as Python or Java
Course Difficulty Level
AdvancedCourse Format
- Online
- Self-paced
Similar Courses
- Algorithms, Part I
- Algorithms and Data Structures
- Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Related Education Paths
Related Books
Description
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.
Outline
- 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
Summary of User Reviews
Learn Advanced Algorithms and Complexity on Coursera. This course has received positive reviews from users who found it challenging and informative. One key aspect that many users appreciated was the instructor's clear explanations and engaging teaching style.Pros from User Reviews
- Challenging and informative course material
- Clear explanations and engaging teaching style from the instructor
- Opportunity to learn from a renowned expert in the field
Cons from User Reviews
- Some users found the assignments to be too difficult
- Limited interaction with the instructor and other students
- Course may not be suitable for beginners or those without a strong background in computer science
Alexander S. Kulikov
4.6 Raiting
Complete UiPath RPA Developer Course: Build 7 Robots
- 4.6
-
![]()
![]()
![]()
![]()
![]()
Master Robotic Process Automation (RPA) and UiPath - go from beginner to advanced. Learn and master UiPath Studio and then build state-of-the-art software robots from scratch....
Artificial Neural Networks for Business Managers in R Studio
- 4.4
-
![]()
![]()
![]()
![]()
![]()
You do not need coding or advanced mathematics background for this course. Understand how predictive ANN models work You've found the right Neural Networks course!...
Cyber Security - Python and Web Applications
- 0.0
-
![]()
![]()
![]()
![]()
![]()
Learn Cyber Security, build analysis tools with Python, protect systems and web apps from vulnerabilities and more! *** Course updated 10/30/2018 (always kept up-to-date) ***...
Algorithms for Searching, Sorting, and Indexing
- 4.6
-
![]()
![]()
![]()
![]()
![]()
This course covers basics of algorithm design and analysis, as well as algorithms for sorting arrays, data structures such as priority queues, hash functions, and applications such as Bloom filters....
