| Module and Duration | Topics | Lectures/Slides |
|---|---|---|
| Complexity Analaysis. Searching and Sorting.
(7 lectures) |
Overview of algorithm design and analysis. Basic problem solving techniques: brute-force search and problem reduction. O-notation. Sequential and binary search. Selection and Insertion Sort. Top-Down and Bottom-Up MergeSort. Quicksort. |
Overview of Algorithms Time/Space Complexity Analysis Basic Searching Mergesort Quicksort |
| Specialized Data Structures
(4 lectures) |
Heaps. HeapSort. Disjoint Set Data Structure. Union-Find algorithms. |
Heap and Heapsort Union-Find |
| Induction and Recursion
(8 lectures) |
Techniques based on Induction and Recursion. Recursive selection/ and insertion Sort. Converting recursion to iteration. Constructing a Latin square. Strong induction. Strengthening the induction hypothesis. Partitioning. Set Union. Polynomial evaluation. Integer exponentiation. Counting Sort. Radix Sort. | Induction Induction Part 2 Induction Part 3 Induction Part 4 |
|
Divide-and-Conquer
(5 lectures) |
Divide-and-Conquer. Finding Min and Max. Master Theorem. Constructing a tournament schedule. Multiplication of polynomials. | Divide-Conquer Part 1 Divide-Conquer Part 2 Divide-Conquer Part 3 |
| Dynamic Programming
(6 lectures) |
Dynamic Programming. Computing binomial coefficients. The Knapsack problem. The all-pairs shortest path problem. Floyd's Algorithm. |
Dynamic Programming Part 1 Dynamic Programming Part 2 |
|
Greedy strategy,
Graph algorithms (6 lectures) |
Greedy approach. Dijkstra's single source shortest path algorithm. Prim's and Kruskal's minimum spanning tree algorithms. Graph traversal (depth-first search and breadth-first search). Topological sorting. |
Graph Basics Graph Traversal - DFS Graph Traversal - BFS Greedy Strategy Greedy Algorithms for MST |
| Backtracking
(5 lectures) |
Backtracking. Graph Coloring. Subset Generation. | Backtracking Part 1 |
| NP-Completeness
(4 lectures) |
Introduction to NP-Completeness. Reducibility. The Halting problem. Techniques for dealing with hard problems. | Theory of NP |