CS310 - Algorithms

---

Course Description:
This is an undergraduate-level course on the design and analysis of algorithms. We will cover basic algorithm design techniques such as divide-and-conquer, greedy algorithms, and dynamic programming. The course also covers introductory complexity theory and advanced topics in algorithms such as network flows.

Prerequisites:

• Undergraduate courses in Computer Programming, Discrete Mathematics, and Data Structures

Textbook(s)/Supplementary Readings:

• Algorithms Dasgupta, Vazirani, Papadimitrious
• Algorithm Design Jon Kleinberg, Éva Tardos

Lectures:

Topic	Slides	Notes	Problem Sets
Algorithmic Thinking Problem Formulation Implementing the Definition Algorithms Runtime Analysis Basic Numbers and Vectors Arithmetic	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
Searching and Sorting Linear and Binary Search Order Statistics - Min and Max Comparison Based Sorting Algorithms: Selection, Bubble, Insertion Sort Lower Bound on Comparison based sorting Non-Comparison Based Sorting: Counting, Radix Sort	Slides Slides Slides Slides Slides	Notes	PS
Design Paradigm: Divide and Conquer Finding Rank - Merge Sort Karatsuba Algorithm for Integers Multiplication Counting Inversions Finding Closest Pair in Plane	Slides Slides Slides Slides	Notes	PS
Graphs and Trees Directed and Undirected Graphs Graph Representation Graph Connectivity Trees and Forest Bipartite Graphs	Slides	Notes	PS
Basic Graph Algorithms Exploring Graphs Depth First Search DFS Forest - Start and Finish Time DAG, Topological Sorting Strongly Connected Components Breadth First Search Bipartite Matchings extended to Gale Shapely	Slides Slides Slides Slides 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
Greedy Interval Scheduling Compatible and Conflicting Requests Greedy Algorithms Earliest Finish time First Algorithm Correctness and Optimality Implementation and Runtime	Slides Slides Slides	Notes	PS
Greedy Interval Coloring Interval Coloring - Degree, Depth, Lower Bound Greedy Interval Coloring Interval Coloring with Unknown Depth	Slides		PS
Huffman Code Data Compression Lossy and Lossless Compression Adaptive and non-Adaptive Compression Fixed and Variable length Codes Prefix Free Codes Binary Tree Representation Goodness Measure Generic Greedy Algorithm Huffman Code Optimality and Implementation	Slides Slides 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
Weighted Interval Scheduling Weighted Interval Scheduling Dynamic Programming Formulation	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
Single Source Shortest Paths Problem Single Source Shortest Paths Problem SSSP Dynamic Programming Formulation Bellman-Ford Algorithm	Slides Slides Slides
Floyd-Warshall Algorithm All-Pairs Shortest Paths Problem APSP Dynamic Programming Formulation Floyd-Warshall Algorithm	Slides Slides Slides
Network Flow Maximum Flow: Problem Formulation Maximum Flow: Upper Bound Maximum Flow: Adding flow along paths Residual Network and Augmenting Path Ford-Fulkerson Algorithm -- Max-Flow-Min-Cut Theorem Edmond-Karp Algorithm Maximum Flow: Variants and Applications	Slides Slides Slides Slides Slides Slides Slides	Notes	PS
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

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