# 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 compressionSingle-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 IVNetwork 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