This course provides a comprehensive introduction to the fundamental strategies for designing and analyzing efficient algorithms, including greedy methods, divide-and-conquer, dynamic programming, reductions, and randomization. Students will explore key algorithmic paradigms and gain insights into computational intractability, with a focus on NP-complete problems and strategies to address them, such as approximation algorithms and heuristics. By the end of the course, students will be equipped with essential tools to solve complex computational challenges and develop a strong foundation for advanced topics in computer science.
Induction & Combinatorics
Introduction: Overview of the course material; Goals and Applications; Basics for Analysis of Algorithms.
RAM & Turing Machines Model of Computation: Worst, Average, and Best Case analysis of a problem; Soundness and Correctness; Example: Gale & Shapley for Stable Matching & Asymptotics: Big-Oh Notation; Useful properties.
Recall: Arrays, Lists, Trees; Main Example: Safe Uninitialized Array; Amortized vs Worst-Case Analysis; Main Example: Binary Counter Aggregation and Accountant/Banking Method.
Union-Find: Unsorted Array; Up-tree; Union by Rank; Path Compression; Log(n) analysis; inverse Ackerman reference.
Properties of binary trees: Height;Size;Leaf nodes; Heap operations:Shift Up/Shift Down; Insert/SearchMin/Delete/Heapify O(nlogn) & O(n) (Aggregation Analysis)/Heapsort
BFS & Shortest Paths; DFS & Korajaru Strongly Connected Components; Topological Order
MergeSort Algorithm: Correctness, Complexity; Master Theorem. Binary Search and Lower bounds in the Comparison model for search and sort / Binary search in the solution space.
Counting Inversions, CountingSort, RadixSort, Integer Multiplication, Repetitive Exponentiation, Matrix Multiplication, Closed Pairs, Max Subarray.
Bins & Balls, Birthday Paradox, Chaining, Average Case Analysis, Bounding Maximum Load (on expectation and with high probability).
Rank vs Select Problem, Median of Medians, QuickSelect, Quick Sort. Average and Worst Case Performance; High Probability and Concentration Measures.
Freivald Algorithm for Matrix Multiplication; Las Vegas, Monte Carlo, and Atlantic City Algorithms; Polynomial Equality.
Exchange Argument & Stay Always Ahead: Minimum Coins Exchange, Positive set alignment, Positive Function Optimization, Interval Scheduling.
Huffmann Code and Offline Cache Paging.
Factorial, Fibonacci Sequence, Memoization, DAG computation, Shortest paths in DAGs.
Coin Collection: Recursively, Backward, Forward, Space Optimization.
Djikstra Algorithm
Bellman-Ford Algorithm
Kruskal & Prim’s Algorithm & Applications in Clustering
Ford-Fulkerson’s Algorithm
Floyd-Warshall Algorithm
Reducing Negatively Weighted Graphs using Johnson’s Algorithm
Logic, Russell’s Paradox, Godel’s Incompleteness Theorem, Turing Machines, Halting Problem and P vs NP
Cook-Levin’s Theorem about SAT
Independent-Set, Vertex-Cover, Clique, Super-Mario Nintendo Game
Generalization, Knapsack,Subset Sum, Hamilton-Paths, 3D Matching & Partition Problems
Presentation of Coding Challenges