Course Information

Course syllabus, slides, lecture recordings, assignments, and important announcements will all be posted in Folio. Please check Folio frequently for updates.

Prerequisites

Recommended Textbook

Assessments

Your performance in this course will be measured by the following.

Assessment Type Number Percentage of Final Grade
Homework Assignments 4 50% (12.5% * 4)
Term Project 1 40%
Short Essay 1 5%
Participation 20 5%

Course Schedule (Updated Weekly)

Abbreviations:

All lecture slides and lecture recordings will be available in Folio.

Dates Prerequisite Topics (Background Knowledge) Lecture Topics Additional Materials
Week 1: - Sorting Algorithm: Asymptotic Notations: CLRS4/CLRS3 Sections:
  • "Insertion Sort" in 2.1 Insertion Sort
CLRS4
  • 3.1 O-notation, Ω-notation, Θ-notation
  • 3.2 Asymptotic notation
  • 3.3 Standard notations and common functions
Or CLRS3
  • 3.1 Asymptotic notation
  • 3.2 Standard notations and common functions
 Classes begin: Monday, 1/12

M0: Course Introduction
  • Read Course Syllabus posted on Folio
  • Complete the "Attendance Verification" via Folio at your earliest.
M1: Algorithm Foundations
  • Describe Algorithms in Pseudocode
  • Review: Asymptotic Notations
  • Analyzing Algorithms
 CLRS4/CLRS3 Sections:
  • 1.1 Algorithms
  • "Pseudocode conventions" in 2.1 Insertion Sort
  • 2.2 Analyzing algorithms
Online Resources:
Week 2: - Monday, 1/19: Martin Luther King Jr. Holiday - No Class
Sorting Algorithm: CLRS4/CLRS3 Sections:
  • "Merge Sort" in 2.3 Designing algorithms
 M1: Algorithm Foundations (cont'd)
  • Analyzing Algorithms (cont'd)
  • Solving Recurrences
 Online Resources:
Week 3: - Greedy Algorithms: CLRS4/CLRS3 Sections:
  • 15.2/16.2 Elements of the greedy strategy
    - "Greedy-choice property" and "Optimal substructure"
 M1: Algorithm Foundations (cont'd)
  • Solving Recurrences (cont'd)
M2: Greedy Algorithms vs Dynamic Programming (DP)
  • Review: Properties for Greedy Approach to Work
  • Activity Selection Problems
 CLRS4/CLRS3 Sections:
  • 4.3 The substitution method for solving recurrences
  • 4.4 The recursion-tree method for solving recurrences
  • 4.5 The master method for solving recurrences
  • 15.1/16.1 An activity-selection problem
Online Resources:
Week 4: - Dynamic Programming (DP): CLRS4/CLRS3 Sections:
  • 14.3/15.3 Elements of dynamic programming
 M2: Greedy Algorithms vs DP (cont'd)
  • The Weighted Activity Selection Problem
  • Review: Properties for DP to Work
  • DP for Solving the Activity Selection Problem
  • DP vs Greedy Approach
M3: Randomized Algorithms
  • Probabilistic Analysis
 CLRS4/CLRS3 Sections:
  • 5.2 Indicator random variables
  • 5.3 Randomized algorithms
Online Resources:
HA1 due on Sunday, 2/8
Week 5: - Sorting Algorithm: Binary Search Tree (BST): CLRS4/CLRS3 Sections:
  • 7.1 Description of quicksort
  • 7.2 Performance of quicksort
  • 12.1 What is a binary search tree?
  • 12.2 Querying a binary search tree
 M3: Randomized Algorithms (cont'd)
  • Randomized Linear Search
  • Review: Quicksort
  • Randomized Quicksort
M4: Binary Search Trees (BSTs)
  • Review: BST
  • Insertion in BST
 CLRS4/CLRS3 Sections:
  • 7.3 A randomized version of quicksort
  • 7.4 Analysis of quicksort
  • 12.3 Insertion
Online Resources:
Week 6: - M4: BSTs (cont'd)
  • Balanced BSTs
    • Red-Black Trees
    • AVL Trees
 CLRS4/CLRS3 Sections:
  • 13.1 Properties of red-black trees
  • 13.2 Rotations
Online Resources:
HA2 due on Sunday, 2/122
Week 7: - Graph Basics: BFS and DFS:
  • YouTube video: BFS
  • YouTube video: DFS
CLRS4/CLRS3 Sections:
  • B.4 Graphs
  • 20.1/22.1 Representations of graphs
  • 20.2/22.2 Breadth-first search
  • 20.3/22.3 Depth-first search
 M5: DFS-Based Graph Algorithms
  • Review: Graph Basics, DFS
  • Topological sort
 CLRS4/CLRS3 Sections:
  • 20.4/22.4 Topological sort
Online Resources:
Week 8: - M5: DFS-Based Graph Algorithms (cont'd)
  • Longest path in DAG
  • Strongly connected components
 CLRS4/CLRS3 Sections:
  • 20.5/22.5 Strongly connected components
Online Resources:
Pproject teams and topics finalized on Wednesday, 3/4
Project Proposal due on Sunday, 3/8
Week 9: -
Shortest Path Heaps (for Dijkstra implementation) CLRS4/CLRS3 Sections:
  • 6.1 Heaps
  • 6.2 Maintaining the heap property
  • 6.3 Building a heap
  • 6.5 Priority queues
  • 22.3/24.3 Dijkstra's algorithm
 M6: Shortest Paths
  • The Single-Source Shortest Paths (SSSP) Problem
  • The Bellman-Ford Algorithm for SSSP
  • The All-Pair Shortest Paths (APSP) Problem
  • The Floyd-Warshall Algorithm for APSP
 CLRS4/CLRS3 Sections:
  • 22.1/24.1 The Bellman-Ford algorithm
  • 23.2/25.2 The Floyd-Warshall algorithm
Online Resources:
HA3 due on Sunday, 3/15
Week 10: - Spring break
Week 11: - M7: Flow Networks
  • The Maximum-Flow Problem
  • The Ford-Fulkerson Method
  • Max-Flow Min-Cut Theorem
  • The Edmonds-Karp Algorithm
 CLRS4/CLRS3 Sections:
  • 24.1/26.1 Flow networks
  • 24.2/26.2 The Ford-Fulkerson method
Online Resources:
Submit Essay topic by Sunday, 3/29
Week 12: - M7: Flow Networks (cont'd)
  • The Edmonds-Karp Algorithm
  • Maximum bipartite matching
  • Image Segmentation
 CLRS4/CLRS3 Sections:
  • 24.3/26.3 Maximum bipartite matching
Online Resources:
Week 13: - M8: Parallel Algorithms
  • The Basics of Fork-Join Parallelism
  • Parallel Merge Sort
 CLRS4 Sections:
  • 26.1/27.1 The basics of dynamic multithreading / fork-join parallelism
  • 26.3/27.3 Multithreaded/Parallel merge sort
Online Resources:
HA4 due on Sunday, 4/12
Week 14: - M9: NP-related Concepts
  • Complexity Classes: P, NP, NPC
  • NP-Complete Problems
 CLRS4/CLRS3 Sections:
  • 34.1 Polynomial time
  • 34.3 NP-Completeness and reducibility
  • 34.4 NP-Completeness Proofs
  • 34.5 NP-Complete Problems
Online Resources:
Week 15: - Project Presentations
Week 16: - Project Presentations
Short Essay due on Sunday, 5/3
Week 17: - Last day of classes: Monday, 5/4

Project Presentations
Project final report with source code due on Tuesday, 5/5

© 2026 Yao Xu. All rights reserved. This webpage is created and maintained by Yao Xu. Last updated on .