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
  • Finding Rank - Merge 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