Algorithm Design and Analysis: Spring 2022

setup

Introduction to Algorithm Analysis

Motivation: why study algorithms? Greatest hits. RSA algorithm. Slides 01.01. Example. Video explanation: link. Reading: link.

Algorithm Design Basics. Formalizing problems. Pseudocode. Analysing running time. Slides 01.02.
Exploring big Oh. Slides 01.03. Readings: ADA*: 1.1 - 1.2.

Data Structures

Basic Data Structures: Review

Arrays. Slides 02.01. Video. Dynamic Arrays. Slides 02.02. Video. Linked Lists. Slides 02.03. Video.
Notion of Abstract Data Types (ADT). Stack and Queue ADT. Slides 02.04. Video. Readings: ADA*: 2.1 - 2.2.

Priority Queue ADT. Slides 02.05. Video. Implementing Priority Queue using Binary Heaps. Slides 02.06. Video.
Using Data Structures for Algorithm Design: Heap Sort. Slides 02.07. Video. Readings: ADA*: 5.1 - 5.4.

Set and Map ADT. Hash Tables. Slides 02.08. Video. Readings: ADA*: 6.1 - 6.3.

Local Range ADT. Slides 02.09. Video. Tree Data Structure. Types of tree traversals. Slides 02.10. Video. Readings: ADA*: 2.3.
Binary Search Trees (BST). Slides 02.11. Video. Readings: ADA*: 3.1 - 3.2. Balancing BSTs with tri-node restructuring. Slides 02.12. Video. Readings: ADA*: 4.1 - 4.2.

Basic ADT and Data Structures Summary

Data Structures

Graphs

Review of Graph ADT. Data structures for representing Graphs: Adjacency List and Adjacency Matrix. Slides 03.01. Algorithms for Graph traversals: Breadth-First Search and Deapth-First Search. Role of Stack and Queue ADT. Recursive and Iterative DFS. Slides 03.02. Readings: ADA*: 13.1 - 13.4.

baseline

Exhaustive Search

Implementing algorithms. Automated correctness tests. Comparative performance. Tutorial. Sample code: Python.

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. Readings: ADA*: 1.3.

Using exhaustive graph traversals for problem solving. Topological sorting. Slides 04.02. Readings: ADA*: 13.4.4.
Strongly Connected Components. Slides 04.03. Readings: A Chapter from a different book.

Exhaustive algorithms: summary. Slides 04.04.

safe moves

Greedy Algorithms

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. Readings: ADA*: 10.1 - 10.3 plus this short book chapter.

Greedy algorithms on graphs. Min-cost Spanning Trees (MST). MST algorithms: Prim-Jarnik, Kruskal. Slides 05.03. Proof of correctness. Cut Crossing Theorem. Slides 05.04. Efficient implementation of Kruskal's algorithm using new data structure: Union-Find. Slides 05.05. Readings: ADA*: 15.1 - 15.4.

subproblems

Divide-and-Conquer Algorithms

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. Merge Sort. Running time of Merge Sort. Lower bound on comparison-based sorting. Non-comparison based sorting: Count Sort. Slides 06.02. Representative problems. Counting inversions in loglinear time. Closest pair in loglinear time. Slides 06.03. Randomized approaches. Quicksort. Randomized Quicksort: expected running time. Difference between Las Vegas and Monte Carlo randomized algorithms. Slides 06.04. Readings: ADA*: 8.1 - 8.3.

Deriving running time of recursive algorithms from recurrence relation. Master theorem. Slides 06.05. Readings: ADA*: 11.1.

bottom-up approach

Dynamic Programming Algorithms

Intuition. Shortest paths in a special grid. Overlapping subproblems. Recursion with memoization. Bottom-up approach. Edit Distance problem. Slides 07.01. Readings: ADA*: 12.2.

Representative problems. Discrete Knapsack. Slides 07.02. Subset sum. Slides 07.03. Exercises: LINK. Readings: ADA*: 12.6.

Designing algorithms with Edit Graph. Longest Common Subsequence and string similarity. Slides 07.04. Edit distance in linear space via divide-and-conquer = Hirschberg algorithm. Slides 07.05. Readings: ADA*: 12.5.

Shortest paths in graphs: revisited. Review of the Dijkstra algorithm. Slides 07.06. Problem with negative edge costs and negative cycles. Dynamic Programming approaches to algorithms on graphs. The Bellman-Ford algorithm for single-source shortest paths with negative edge costs. Slides 07.07. All-pairs shortest paths problem. The Floyd-Warshall algorithm. Slides 07.08. The Johnson algorithm. Slides 07.09. Readings: ADA*: 14.1 - 14.5.

hard problems

Dealing with Intractable Problems

Tractability as polynomial-time solvability. Decision, Construction and Optimization problems. Complexity classes P and NP. Slides 08.01. Classifying problems by relative hardness. Proof by reduction. Dealing with NP-complete problems. Slides 08.02. Readings: ADA*: 17.1 - 17.4.