Motivation. Greatest hits. RSA algorithm. Slides. Example. Video explanation: link. Reading: link.
Algorithm Design Basics. Formalizing problems. Pseudocode. Analysing running time. General steps in algorithm design. Two algorithms for computing Greatest Common Divisors. Algorithms for generating primes. Slides. Readings: Textbook Part I, Chapters 2, 3. Exploring big O. Slides.
Implementing algorithms. Automated correctness tests. Slides. Video recording. Comparative performance. Sample code: Python. Java.
Notion of Abstract Data Types (ADT). Review of Stack and queue ADT. Slides 02.01. Readings (optional): Textbook Part III, Chapter 10.
Review of Priority Queue ADT and its implementation using Binary Heaps. Slides 02.02.
Heap Sort. Slides 02.03. Readings: Textbook Part II, Chapter 6.
Review of Set and Map ADT. Hash table. Slides 02.04. Video recording.
Review of Local Range ADT. Tree Data Structure. Types of tree traversals. Slides 02.05.
Binary Search Trees (BST). Slides 02.06. Video recording.
Balancing BSTs with tri-node restructuring. Slides 02.07.
Video recording.
Readings: Chapter from the "Algorithm Design and Applications"
book.
ADT and Data Structures summary
Review of Graph ADT. Modeling problems with graphs. Slides 03.01.
Basic Graph Terminology. Slides 03.02.
Review of graph traversal algorithms. Breadth First Search (BFS).
Depth First Search (DFS). Role of Stack and Queue. Recursive DFS. Slides 03.03.
Readings: Chapter 22.
Exhaustive search basics. Generate and test. Representative problems. Optimizations: reducing the size of the candidate set, reusing computation between successive candidates, backtracking. Polynomial vs. exponential search space. Slides 04.01. Optimized exhaustive pattern search with Knuth, Morris and Pratt. Slides 04.02.
Using exhaustive graph traversals for problem solving. Topological sorting. Slides 04.03. Strongly connected components. Slides 04.04.
Exhaustive algorithms: summary. Slides 04.05.
Greedy approach to problem-solving: introduction. General Greedy strategy. Safe Move. Exchange Argument. Slides 05.01.
Representative problems. Interval scheduling. Slides 05.02. Huffman codes (recap). Reading: Section 16.3.
Greedy algorithms on graphs. Min-cost Spanning Trees (MST). Algorithms for constructing MSTs: Prim-Jarnik, Kruskal, Baruvka. Proof of correctness. Safe move. Slides 05.03. Efficient implementation of Kruskal algorithm using new data structure: Union-Find. Slides 05.04. Readings: Chapters 21 and 23.
Recursive approach to problem-solving. When to use recursion. Separate and conquer. Recap of binary search. Recursion tree. Slides 06.01.
Divide-and-conquer approach to problem-solving. Recap on Merge Sort. Running time of Merge Sort with recursion tree. Lower bound on comparison-based sorting. Non-comparison based sorting in linear time: Count Sort. Slides 06.02.
Representative problems. Counting inversions in loglinear time. Closest pair in loglinear time. Slides 06.03.
Deriving running time of recursive algorithms from recurrence relation. Master theorem. Slides 06.04. Readings: Chapter 11 from the "Algorithm Design and Applications" book.
Randomized approaches. Recap: Quicksort. Randomized Quicksort: expected running time. Difference between Las Vegas and Monte Carlo randomized algorithms. Slides 06.05.
Intuition. Shortest paths in a special grid. Overlapping subproblems. Recursion with memoization. Bottom-up approach. Edit Distance problem. Slides 07.01.
Representative problems. Money-change revisited. Discrete Knapsack. Slides 07.02. Subset sum. Optimal game strategy. Slides 07.03. Exercises: Slides 07.04.
Designing algorithms with Edit Graph. Longest Common Subsequence and string similarity. Slides 07.05. Edit distance in linear space via divide-and-conquer = Hirschberg algorithm. Slides 07.06. Faster Edit Distance computation. [Optional material]. Slides 07.07.
Shortest (min-cost) paths revisited. Review of the Dijkstra algorithm. Dynamic Programming approaches to shortest paths. The Bellman-Ford algorithm for single-source shortest paths
with negative edge costs. Slides 07.08. Readings: main textbook Chapter 24.1.
All-pairs shortest paths problem. The Floyd-Warshall algorithm. The Johnson algorithm.
Slides 07.09. Readings: Chapter 25.2.
Tractability as polynomial-time solvability. Complexity class P. Intractable problems: polynomial-time algorithm is not known. Knapsack. Notion of pseudo-polynomial algorithms. Classifying problems by hardness. Decision, Construction and Optimization problems. Example of a decision problem: 3SAT. Exhaustive solution via decision tree. Non-deterministic solution: random guess. Class NP: solution is verifiable in polynomial time. NP-complete problems: the hardest problems in NP. Cook-Levin theorem. Proof of NP-completeness by reduction. Dealing with NP-complete problems. Slides 08.01. Readings: Chapter 17 from the "Algorithm Design and Applications" book.
Course summary and future aspirations. Links and Pointers.