AI630 | Advanced Analysis of Algorithms
  • Rating: 4.85
  • (439)
Course overview

Design and Analysis of Algorithms introduces algorithms by looking at the real-world problems that motivate students. The course teaches students a range of design and analysis techniques for problems that arise in computing applications. The course encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

What you will learn
Greedy Algorithms
Largest Number, Car Fueling, Grouping Children, Fractional Knapsack
Divide-and-Conquer
Linear & Binary Search, Master Theorem, Selection, Merge, and Quick Sort
Dynamic Programming
The Alignment Game, Computing Edit Distance Knapsack
Decomposition of Graphs
Directed Acyclic Graphs, Paths in Graphs, Dijkstra's Algorithm, Bellman-Ford Algorithm, Minimum Spanning Trees
Shortest Paths
Bidirectional Dijkstra, A* Algorithm, Performance of A*, Bidirectional A* Witness Search, Query, Node Ordering
Flows in Networks
Network Flows, Residual Networks, Maxflow-Mincut, The Ford–Fulkerson Algorithm, The Edmonds–Karp Algorithm, Bipartite Matching
Linear Programming
Linear Algebra: Method of Substitution, Gaussian Elimination, Convexity, Duality, The Simplex Algorithm, The Ellipsoid Algorithm
NP-Complete Problems
Brute Force Search, Traveling Salesman Problem, Hamiltonian Cycle Problem, Longest Path Problem, P and NP, NP-completeness
Course program
Lessons Name Description Duration Week Slides
1 Algorithm Warm-Up Fibonacci Numbers, GCD, Big-O Notation 3 hours 1 A3S2201
2 Greedy Algorithms Car Fueling, Grouping Children, Fractional Knapsack 3 hours 2 A3S2202
3 Divide-and-Conquer Searching, Sorting, Polynomial Multiplication, Master Theorem 6 hours 3,4 A3S2203
4 Dynamic Programming Change Problem, String Comparison, Edit Distance, Optimal Alignment 9 hours 5,6,7 A3S2204
5 Decomposition of Graphs 01 Representing and Exploring Graphs, Connectivity, Pre and Post Visits 6 hours 8,9 A3S2205-01
6 Decomposition of Graphs 02 DAG, Topological Sorting, Strongly Connected Components 6 hours 10,11 A3S2205-02
7 Paths in Graph 01 Breadth First Search, Dijkstra's Algorithm 3 hours 12 A3S2205-03