CIS 575, Introduction to Algorithm Analysis
Spring 2022 Schedule

General remarks

Schedule

Class     Topics HomeworkExam
1: Wed
Jan 19		 Introduction (I)
  1. Course Syllabus
  2. Specifications & Implementations
  3. Specifying Sorting and Selection
2: Fri
Jan 21		 Introduction (II)
  1. Top-down Sorting
  2. Recursive Insertion Sort
  3. Iterative Insertion Sort
  4. Time & Space Analysis
HW #1 out
3: Mon
Jan 24		 Asymptotic Notation (I)
  1. Motivating Asymptotic Analysis
  2. Motivating Big-O Notation
  3. Reasoning About Big-O
4: Wed
Jan 26		 Asymptotic Notation (II)
  1. Big-Omega and Big-Theta
  2. Worst-Case Interpretation
  3. little-o, little-omega
HW #1 due
tomorrow night
5: Fri
Jan 28		 Analyzing Iterative Algorithms
  1. Motivate Sum Estimates
  2. Sum Estimates: Upper, Lower
  3. Sum Estimates: Recipe, Applications
  4. Pitfalls in Analysis
HW2 out
6: Mon
Jan 31		 Analyzing Recursive Algorithms (I)
  1. Motivate Recurrences
  2. Solving Recurrences
  3. Substitution Method
7: Wed
Feb 2		 Analyzing Recursive Algorithms (II)
  1. Substitution Method: Case 2
  2. Substitution Method: Case 3
  3. Master Theorem: Intuition
HW #2 due
tomorrow night
8: Fri
Feb 4		 Analyzing Recursive Algorithms (III),
Master Theorem:
  1. One Version, with Applications
  2. Comparing Various Versions
  3. Indirect Applications
  4. Proof Sketch (optional)
HW #3 out
9: Mon
Feb 7		 The Correctness of Algorithms (I)
  1. Loop Invariants & Proof Obligations
  2. Verifying a Simple Loop on Integers
  3. Constructing a Provably Correct Program
10: Wed
Feb 9		 The Correctness of Algorithms (II)
  1. Verifying a Simple Loop Reading Arrays
  2. Dutch National Flag: Problem
  3. Dutch National Flag: Solution
HW #3 due
tomorrow night
11: Fri
Feb 11		 The Correctness of Algorithms (III)
  1. Correctness of Iterative Insertion Sort
  2. Correctness of Recursive Algorithms
  3. Correctness of Recursive Insertion Sort
HW #4 out
12: Mon
Feb 14		 Graphs (I)
  1. Basic Concepts
  2. Trees
13: Wed
Feb 16		 Graphs (II)
  1. Representations
HW #4 due
tomorrow night
Fri
Feb 18		 Class Canceled
14: Mon
Feb 21		 Review session for Exam #1
15: Wed
Feb 23		 Exam #1
16: Fri
Feb 25		 Heaps (I)
  1. A Priority Queue and its Implementation
  2. The Heap Property and its Preservation
  3. A Binary Heap and its Representation
HW #5 out
17: Mon
Feb 28		 Heaps (II)
  1. Converting a Tree into a Heap
  2. HeapSort
18: Wed
Mar 2		 Divide & Conquer (I)
  1. Divide & Conquer Paradigm
  2. Merge Sort & Quicksort
  3. Analysis of Quicksort
HW #5 due
tomorrow night
19: Fri
Mar 4		 Divide & Conquer (II)
  1. Perspectives on Sorting
  2. Lower Bound for Sorting
HW #6 out
20: Mon
Mar 7		 Divide & Conquer (III)
  1. Multiplying Large Integers
  2. Multiplying Large Matrices
21: Wed
Mar 9		 Divide & Conquer (IV)
  1. The Selection Problem
  2. Linear Time Selection
HW #6 due
tomorrow night
Fri
Mar 11		 Class Canceled HW #7 out
22: Mon
Mar 21		 Dynamic Programming (I)
  1. Motivation
  2. Giving Exact Change
23: Wed
Mar 23		 Dynamic Programming (II)
  1. The Binary Knapsack Problem
HW #7 due
tomorrow night
24: Fri
Mar 25		 Dynamic Programming (III)
  1. All-Pairs Shortest Path
HW #8 out
25: Mon
Mar 28		 Dynamic Programming (IV)
  1. Chained Matrix Multiplication
  2. Optimality of SubSolutions
26: Wed
Mar 30		 Depth-First Search (I)
  1. DFS for UnDirected Graphs
  2. DFS for Directed Graphs
  3. Algorithms Based on DFS
HW #8 due
tomorrow night
27: Fri
Apr 1		 Depth-First Search (II)
  1. Topological Sort by DFS
  2. Articulation Points by DFS
28: Mon
Apr 4		 Review session for Exam #2
29: Wed
Apr 6		 Exam #2
Fri
Apr 8		 Class Canceled (Open House) HW #9 out
30: Mon
Apr 11		 Greedy Algorithms (I)
  1. Motivation
  2. Two Scheduling Problems with Greedy Solutions
  3. The Fractional Knapsack Problem
31: Wed
Apr 13		 Greedy Algorithms (II)
  1. Minimum-Cost Spanning Tree (MST)
  2. Kruskal's Algorithm for MST
  3. Prim's Algorithm for MST
HW #9 due
tomorrow night
Fri
Apr 15		 Class Canceled (Good Friday) HW #10 out
32: Mon
Apr 18		 Greedy Algorithms (III)
  1. Single-Source Shortest Path: Dijkstra's Algorithm
33: Wed
Apr 20		 Flow Networks (I)
  1. Basic Concepts
  2. Finding Maximal Flow
  3. The Ford-Fulkerson Method
  4. The Edmonds-Karp Algorithm
HW #10 due
tomorrow night
34: Fri
Apr 22		 Flow Networks (II)
  1. Minimal Cuts
  2. Bipartite Matching
HW #11 out
35: Mon
Apr 25		 Union-Find Structures
  1. Union-Find Data Structures
  2. Union By Rank
  3. Path Compression
36: Wed
Apr 27		 Miscellaneous Topics (I)
  1. Extreme Function Growth
HW #11 due
tomorrow night
37: Fri
Apr 29		 Miscellaneous Topics (II)
  1. Linear-Time Sorting Algorithms
  2. Huffman Codes
Mon
May 2		 Class Canceled (dead week)
Wed
May 4		 Class Canceled (dead week)
38: Fri
May 6		 Review session for Final exam
Mon
May 9 		Final exam
4:10--6:00pm