Fall 2022 Algorithms with Peter Sadowski and run within Laulima.
- Schedule: Weekly readings/videos, problem sets, and exams.
- Syllabus: Basic course information.
- Section 1: MW 0100-0240p WEB 101
- Section 2: MW 0300-0440p WEB 101
This course covers the following topics. See Schedule for more detail.
- #1 - Introduction to Course: CLRS Chapter 1; Topic 01 Notes
- #2 - Examples of Analysis with Insertion and Merge Sort: CLRS Chapter 2; Topic 02 Notes
- #3 - Growth of Functions and Asymptotic Concepts: CLRS Chapter 3; Topic 03 Notes
- #4 - Basic ADTs (Stacks, Queues, Lists and Trees): CLRS Chapter 10; Topic 04 Notes
- #5 - Probabilistic Analysis and Randomized Algorithms: CLRS Sections 5.1-5.3, 5.4.1; Goodrich & Tamassia section on Skip Lists; Topic 05 Notes
- #6 - Hash Tables: CLRS Sections 11.1-11.4; Topic 06 Notes
- #7 - Divide & Conquer and Analysis of Recurrences: CLRS Chapter 4 (4.1 & 4.3-4.5); Topic 07 Notes
- #8 - Binary Search Trees: CLRS Sections 12.1-12.3 (see also Theorem 12.4); Topic 08 Notes
- #9 - Heaps, Heapsort and Priority Queues: CLRS Chapter 6 (all); Topic 09 Notes
- #10 - Quicksort, Theoretical Limits, and O(n) Sorts: CLRS Chapters 7 & 8; Topic 10 Notes
- #11 - Balanced Trees (2-3-4 and Red-Black): Sedgewick Chapter 15 & CLRS Chapter 13; Topic 11 Notes
- #12 - Dynamic Programming: CLRS Chapter 15 (and optionally Sedgewick Chapter 37); Topic 12 Notes
- #13 - Greedy Algorithms & Huffman Codes: CLRS Sections 16.1-16.3; Topic 13 Notes
- #14 - Graph Representations and Basic Algorithms: CLRS Chapter 22; Goodrich & Tamassia excerpt on Representations; Topic 14 Notes
- #15 - Amortized Analysis: CLRS Chapter 17 Sections 17.1-17.2; Topic 15 Notes (leave out the Potential method), AND:
#16 - Sets and Union-Find: CLRS Sections 21.1, 21.3 and Theorem 21.14 (read beginning of 21.4 through definition of α and the theorem); Topic 16 Notes (leave out the linked representation)
- #17 - Minimum Spanning Trees: CLRS Chapter 23; Topic 17 Notes
- #18 - Single-Source Shortest Paths: CLRS Sections 24.1-24.3; Topic 18 Notes
- #19 - All-Pairs Shortest Paths: CLRS Chapter 25; Topic 19 Notes
- #20 - Maximum Flow: CLRS Sections 26.1-26.3; Topic 20 Notes
- #22 - Multithreading: CLRS Chapter 27 (emphasis on sections 27.1 and 27.3), Topic 22 Notes
- #24 - NP-Completeness and Complexity Theory: CLRS Chapter 34; Topic 24 Notes (no homework)
Other topics not covered:
- #21 - Linear Programming: Sedgewick (1983) Chapters 5 and 38 (read these first); CLRS Sections 29.0-29.3 (half way); Topic 21 Notes
- #23 String Matching: CLRS Chapter 32 (emphasis on sections 32.1 and 32.3); Topic 23 Notes
- #25 - Approximation Algorithms: CLRS Chapter 35; Topic 25 Notes (no homework)
- Public Key Encryption: CLRS Chapter 31 (emphasis on 31.7). No web notes or videos have been made.