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 |