Computer Science: Algorithms & Data Structures II

CSC 226, Fall 2022

Lectures: Mondays and Wednesdays 4:30pm - 5:50pm, ECS 125
Instructor: Nishant Mehta
TAs: Ali Mortazavi (<firstname>themorty@gmail), Azadeh Mousavi (as<lastname>@uvic>)

Labs: 50 minutes, Mondays starting at 12pm, 1:30pm, 2:30pm or Tuesdays starting at 12:30pm, ECS 258

Nishant's office hours: Tuesdays 4pm - 5pm and Wednesdays 2:30pm - 3:30pm, ECS 608

Textbooks:


Syllabus
Date Title Topics Reading
9/7 Intro, Big-O, RAM model Course overview, Asymptotic notation, RAM model
slides
CLRS: Chapters 1–3
Graph algorithms
9/12 Minimum spanning trees I Minimum spanning tree problem, Kruskal's algorithm, Prim's algorithm KT: Section 4.5  or  CLRS: Chapter 23
9/14 Minimum spanning trees II Kruskal's algorithm, Prim's algorithm
slides
KT: 4.6  or  CLRS: Sections 21.1–21.3
Problem Set 1 (to be released on Sep 14 night) - Due Friday, Sep 30 at 11:55pm
9/19 No face-to-face lecture!!
Minimum spanning trees III (brief)
Union-Find I (main part)
Watch recorded lectures from Spring 2021 (linked below)
Prim's algorithm: slides      video
Dynamic connectivity problem, Union-Find: notes      slides      video
9/21 Union-Find II
Shortest paths I
Weighted Quick-Union, Path compression
Single-source shortest paths problem: slides
CLRS: Chapter 24 (everything except for Section 24.4)
9/26 Shortest paths II Single-source shortest paths problem, BFS solution, DFS-based solution
slides
9/28 Shortest paths III Dijkstra's algorithm, Bellman-Ford algorithm
slides
10/3 Shortest paths IV
Network flows I
Bellman-Ford continued, All-pairs shortest paths problem, Floyd-Warshall algorithm
Flow networks
slides
KT: Sections 7.1-7.2
10/5 Network flows II Max-Flow problem, Min-Cut problem
Augmenting paths, Ford-Fulkerson algorithm
slides
10/10 NO CLASS Thanksgiving
10/12 Network flows III Analysis of Ford-Fulkerson algorithm, Max-Flow Min-Cut Theorem
slides
CLRS: Sections 26.1 - 26.2 (for analysis of Edmonds-Karp)
Midterm - Monday, October 17th
Randomized Algorithms
10/19 Edmonds-Karp algorithm Edmonds-Karp
10/24 Selecting the kth smallest element Quickselect with median of medians pivot
slides
• CLRS: Section 9.3
Avrim Blum's notes: Section 4.3
10/26 Randomized Quickselect and Quicksort Basic probability: slides
Randomized Quickselect: slides
Luca Trevisan's notes: Sections 1 and 2 (Basic probability)
Randomized analysis handout
• KT: Section 13.5  or  CLRS: Chapter 7
10/31 Randomized Quickselect and Quicksort Randomized Quickselect and Randomized Quicksort CLRS: Chapter 11
(Section 11.3.3 is recommended; Section 11.5 is optional)
11/2 Hashing I Direct-address tables, Hash tables, Average-case analysis
slides
11/7 Hashing II Universal hashing, Open addressing
11/9 NO CLASS Reading break
Algorithms
11/14 Hashing III
Amortized Analysis I
Open addressing
Aggregate analysis, Accounting method: slides
CLRS: Chapter 17
11/16 Amortized Analysis II Accounting method (Dynamic tables) CLRS: Chapter 32 (excluding section 32.4)
11/21 Amortized Analysis III
String search I
Accounting method (Dynamic tables)
Substring search problem, Rabin-Karp algorithm: slides
11/23 String search II Knuth-Morris-Pratt algorithm KT: Sections 4.1-4.3 (but 4.3 is optional)
11/28 Greedy algorithms Interval scheduling, Interval partitioning, Scheduling to minimize lateness
slides
KT: Sections 6.1-6.4
11/30 Dynamic programming Weighted interval scheduling, Knapsack
slides
CLRS: Section 15.4