CS510 - Design and Analysis of Algorithms

---

Course Description:
This is a graduate-level course on the design and analysis of algorithms. After a quick review of basic algorithm design techniques such as divide-and-conquer, greedy algorithms, and dynamic programming, the course covers introductory complexity theory and advanced topics in algorithms such as network flows, randomized algorithms, approximation algorithms, and linear programming.

Prerequisites:

• An undergraduate course in Discrete Mathematics, Data Structures, Algorithms and Probability.
• Strong problem solving skills and some background in programming.

Textbook(s)/Supplementary Readings:

• Algorithm Design Jon Kleinberg and Éva Tardos

Lectures:

Topic	Slides	Notes	Problem Sets
Algorithmic Thinking Problem Formulation Multiplication example using pen and paper	Slides	Notes
Asymptotic Analysis Runtime Analysis ang Big Oh Complexity Classes and Curse of Exponential Time Relational Properties: Big Omega, Big Theta, Little Oh	Slides Slides Slides	Notes	PS
Design Paradigm: Divide and Conquer Quick Sort Karatsuba Algorithm for Integers Multiplication Finding Closest Pair in Plane Convex Hull	Slides Slides Slides	Notes	PS
Single Source Shortest Path Weighted Graphs and Shortest Paths Dijkstra Algorithm Proof of Correctness Implementation & Runtime	Slides Slides Slides Slides	Notes	PS
Prim's Algorithm Minimum Spanning Tree Prim's Algorithm for MST Cuts in Graphs Correctness and Optimality Implementation & Runtime	Slides Slides Slides Slides Slides	Notes	PS
Kruskal's Algorithm The Cycle Property (Red Rule) Reverse Delete Algorithm for MST Kruskal's Algorithm for MST Runtime and Implementation Disjoint Sets Data Structure	Slides Slides Slides	Notes
Dynamic Programming Computing Fibonacci Numbers Optimal Substructure Memoization	Slides	Notes	PS
Weighted Independent Sets (Weighted) Independent Set in Graphs Weighted Independent Sets in Path Dynamic Programming Formulation Implementation and Backtracking	Slides Slides Slides Slides
The Knapsack Problem The Knapsack Problem Dynamic Programming Formulation Implementation Fractional Knapsack and Subset Sum Problem	Slides Slides Slides Slides
Sequence Alignment Sequence Analysis The Sequence Alignment Problem Dynamic Programming Formulation	Slides Slides Slides
Matrix Chain Multiplication Matrix Chain Multiplication
Intractable Problems Efficiently Solvable vs. Hard (Intractable) Problems Clique, Independent Set Vertex Cover, Set Cover, Set Packing Hamiltonian Cycle, Path and TSP Coloring and Partitioning Numeric and Number Theoretic Problems Satisfiability Problems	Slides Slides Slides Slides Slides Slides Slides
Polynomial Time Reduction Polynomial Time Reduction Definition Reduction by Equivalence Reduction from Special Cases to General Case Reduction by Encoding with Gadgets-I Reduction by Encoding with Gadgets-II Transitivity of Reductions Decision, Search and Optimization Problem Self-Reducibility	Slides Slides Slides Slides Slides Slides Slides Slides	Notes	PS
Classes of Problems Polynomial Time Verification The Classes P and NP The Classes EXP and coNP NP-Hard and NP-Complete Problems Proving NP-Hardness A First NP-Complete Problem	Slides Slides Slides Slides Slides Slides
Proving NP-Complete Problems The Cook-Levin Theorem: SAT is NP-Complete NP-Complete Problems from known Reductions NP-Complete Applications	Slides
Coping with NP-Hardness Strategies to deal with hard problems Algorithms for Special Cases Fixed Parameter Tractability Intelligent Exhaustive Search Backtracking Branch and Bound Dynamic Programming for TSP	Slides Slides Slides Slides Slides Slides	Notes
Approximation Algorithms Approximation Algorithms for Optimization Problems Absolute Approximation Algorithms Inapproximability by Absolute Approximate Algorithms Relative Approximation Algorithm Inapproximability by Relative Approximate Algorithms Polynomial Time Approximation Schemes Fully Polynomial Time Approximation Schemes	Slides Slides Slides Slides Slides Slides Slides	Notes	PS
Randomized Algorithms Deterministic and Randomized Algorithms Probability Review Probabilistic Analysis of Quick-Sort Algorithm Randomized-Select Max-Cut Min-Cut Max-3-Sat and Derandomization Closest Pair Hashing, Bloom Filters, Streams	Slides Slides Slides Slides Slides Slides Slides Slides Slides	Notes	PS
Local Search Local Search for MAX-CUT Gradient Descent Metropolis Algorithm Simulated Annealing	Slides	Notes

Homeworks

• In this homework, we will develop our concepts for divide and conquer based algorithms for sorting an array of n numbers. [Homework]
• With this homework, we will develop a divide and conquer based algorithm for the general problem of selection of an order statistics of an array. [Homework]
• Homework-3 is specially designed for thoroughly understanding the concepts of Bipartite-Graph and matching. We will develop a combinatorial algorithm for matching in Bipartite-Graphs. This is a classic combinatorial optimization problem with many applications. The algorithm is very simple and simply beautiful. [Homework]
• With this set of problems, we will develop algorithms for All-Pairs Shortest Paths (APSP) in graphs. [Homework]

Back to Top