August 2024
Monday T Wednesday R Friday S
Module 0: Orientation & Overview
12 
Before Class:
Syllabus
Algorithm Design, 1st edition cover Preface (10 pages) (Skim / read) (PDF available in CougarVIEW Announcements)

Class:
Introductions
Syllabus
Gale-Shapley Demo
13 
14 
Before Class:
Algorithm Design, 1st edition cover Chapter 1: Introduction: Some Representative Problems (18 pages) (PDF available in CougarVIEW Announcements)

Class:
Stable Matching (Gale–Shapley)
15 
Deadline for full refund
16 
Before Class:
Algorithm Design, 1st edition cover 2.1 Computational Tractability

Class:
Stable Matching (Gale–Shapley)
17 
Module 1: Algorithm Analysis
19 
Before Class:
Algorithm Design, 1st edition cover 2.1 Computational Tractability
Algorithm Design, 1st edition cover 2.2 Asymptotic Order of Growth

Class:
Computational Tractability & Asymptotic Order of Growth
20 
Turner College Welcome Back Pizza Luncheon Noon - 2:00 PM (SCCT 2nd Floor Lobby)
21 
Before Class:
Algorithm Design, 1st edition cover 2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays
Algorithm Design, 1st edition cover 2.4 A Survey of Common Running Times

Class:
AI Survey
Implementing Gale–Shapley & Survey of Common Running Times
Binary Search Demo
22 
23 
Before Class:
Algorithm Design, 1st edition cover 2.5 A More Complex Data Structure: Priority Queues
Priority Queues (2:42)
Heaps (10:52)
Heaps: BuildHeap (6:42)
Heaps: Efficiency (6:57)

Class:
Binary Search Algorithm Analysis
Survey of Common Running Times
Priority Queues (exercises)
24 
Module 2: Graphs
26 
Before Class:
Algorithm Design, 1st edition cover 3.1 Basic Definitions and Applications
Algorithm Design, 1st edition cover 3.2 Graph Connectivity and Graph Traversal

Class:
Basic Definitions and Applications
Graph Connectivity and Graph Traversal
27 
28 
Before Class:
Algorithm Design, 1st edition cover 3.3 Implementing Graph Traversal Using Queues and Stacks

Class:
Graph Traversals (exercises, pseudo code)
29 
30 
Before Class:
Algorithm Design, 1st edition cover 3.4 Testing Bipartiteness: An Application of Breadth-First Search
Algorithm Design, 1st edition cover 3.5 Connectivity in Directed Graphs

Class:
Testing Bipartiteness
Connectivity in Directed Graphs
31 

September 2024
Monday T Wednesday R Friday S
2 
Labor Day (no class)
3 
4 
Before Class:
Algorithm Design, 1st edition cover 3.6 Directed Acyclic Graphs and Topological Ordering

Class:
DAGs and Topological Ordering (exercises)
5 
Module 3: Greedy Algorithms
6 
Before Class:
Algorithm Design, 1st edition cover 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead

Class:
Topological Sorting Algorithm: Running Time
Interval Scheduling (Earliest Finish Time First Demo, Demo Earliest Start Time First Demo)
7 
9 
Before Class:
Algorithm Design, 1st edition cover 4.2 Scheduling to Minimize Lateness: An Exchange Argument

Class:
Earliest Finish Time First Demo
Interval Partitioning (Demo Earliest Start Time First Demo)
10 
11 
Before Class:
Algorithm Design, 1st edition cover 4.3 Optimal Caching: A More Complex Exchange Argument
Algorithm Design, 1st edition cover 4.4 Shortest Paths in a Graph

Class:
Interval Partitioning (Intuition)
Scheduling to Minimize Lateness
12 
13 
Before Class:
Algorithm Design, 1st edition cover 4.5 The Minimum Spanning Tree Problem

Class:
Scheduling to Minimize Lateness
Dijkstra's Algorithm (Demo)
14 
16 
Before Class:
Algorithm Design, 1st edition cover 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure (optional)

Class:
Dijkstra's Algorithm (Demo)
Minimum Spanning Trees
17 
Turner College Career Fair (SCCT Lobbies 12 - 2 PM)
18 
Before Class:
Algorithm Design, 1st edition cover 4.7 Clustering
Algorithm Design, 1st edition cover 4.8 Huffman Codes and Data Compression (optional)

Class:
Minimum Spanning Trees (Prim's and Kruskal's Demo)
Clustering
19 
Module 4: Divide and Conquer
20 
Before Class:
Mergesort (16:17) (if needed for review)
Algorithm Design, 1st edition cover 5.1 A First Recurrence: The Mergesort Algorithm
A First Recurrence: The Mergesort Algorithm Pre Quiz

Class:
Recurrence of Mergesort (Merge Demo)
21 
Due:
Greedy Algorithm Homework (a quiz with unlimited attempts)
23 
Before Class:
Algorithm Design, 1st edition cover 5.2 Further Recurrence Relations
Quicksort (16:52) (if needed for review)

Class:
Master Theorem
Randomized Quickselect
24 
25 
Before Class:
Algorithm Design, 1st edition cover 5.3 Counting Inversions
Counting Inversions Quiz

Class:
Counting Inversions
26 
27 
University closed due to weather
28 
30 
Before Class:
Algorithm Design, 1st edition cover 5.4 Finding the Closest Pair of Points
Algorithm Design, 1st edition cover 5.5 Integer Multiplication
Closest Pair of Points and Integer Multiplication Pre Quiz

Class:
Finding the Closest Pair of Points (exercise)

October 2024
Monday T Wednesday R Friday S
1 
2 
Before Class:
Algorithm Design, 1st edition cover 5.6 Convolutions and the Fast Fourier Transform (optional)

Class:
Integer Multiplication

Due:
Exam 1 Preparation Game Questions
3 
4 
Class:
Exam 1 Preparation Game (on Teams) (topics)

Due:
Divide and Conquer Homework (a quiz with unlimited attempts)
5 
Deadline to Withdraw with a WP
7 
Class:
Exam 1 (topics)
8 
9 
Before Class:
Advanced Algorithm Research Project (read)

Class:
Recap Exam 1
Advanced Algorithm Research Project Introduction
Research project Proposals
10 
Module 5: Dynamic Programming
11 
Before Class:
Algorithm Design, 1st edition cover 6.1 Weighted Interval Scheduling: A Recursive Procedure
Algorithm Design, 1st edition cover 6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems
Dynamic Programming 1 Pre Quiz

Class:
Fibonacci Sequence Demo
Dynamic Programming Intro
12 
Due:
Advanced Algorithm Research Project Proposal
14 
Before Class:
Algorithm Design, 1st edition cover 6.3 Segmented Least Squares: Multi-way Choices
Algorithm Design, 1st edition cover 6.4 Subset Sums and Knapsacks: Adding a Variable
Segmented Least Squares Pre Quiz

Class:
Segmented Least Squares
Subset Sums and Knapsacks

Due:
Sign-up for Mock Interviews
15 
Distinguished Speaker: Colonel Corey Woods: Strategic Use of Technology in the Military - 6:00 PM in SCCT 305 or Auditorium
16 
Before Class:
Algorithm Design, 1st edition cover 6.5 RNA Secondary Structure: Dynamic Programming over Intervals

Class:
Subset Sums and Knapsacks
RNA Secondary Structure
17 
18 
Before Class:
Algorithm Design, 1st edition cover 6.6 Sequence Alignment
Sequence Alignment Pre Quiz
Algorithm Design, 1st edition cover 6.7 Sequence Alignment in Linear Space via Divide and Conquer

Class:
RNA Secondary Structure
Sequence Alignment
19 
Seniors can Register
21 
Before Class:
Algorithm Design, 1st edition cover 6.8 Shortest Paths in a Graph
Shortest Paths in a Graph Pre Quiz
Algorithm Design, 1st edition cover 6.9 Shortest Paths and Distance Vector Protocols

Class:
Sequence Alignment
Shortest Paths (exercises)
Juniors can Register
22 
Sophomores can Register
23 
Before Class:
Algorithm Design, 1st edition cover 6.10 Negative Cycles in a Graph

Class:
Shortest Paths (exercises)
Negative Cycles in a Graph (exercises)
24 
Module 6: Network Flow
25 
Before Class:
Algorithm Design, 1st edition cover 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

Class:
Shortest Paths (exercises)
Negative Cycles in a Graph (exercises)
26 
28 
Before Class:
Algorithm Design, 1st edition cover 7.2 Maximum Flows and Minimum Cuts in a Network
Algorithm Design, 1st edition cover 7.3 Choosing Good Augmenting Paths

Class:
Maximum-Flow Problem
Ford–Fulkerson (Exercises)
Maximum Flows and Minimum Cuts (Exercises)

Due:
Sequence Alignment Homework (a quiz with unlimited attempts)
29 
30 
Before Class:
Algorithm Design, 1st edition cover 7.4 The Preflow-Push Maximum-Flow Algorithm

Class:
Maximum Flows and Minimum Cuts (Exercises)
Capacity Scaling Algorithm (Exercises)
31 
Graduate School Fair 12:30 - 2:00 PM Outside of Cougar Cafe

November 2024
Monday T Wednesday R Friday S
1 
Before Class:
Algorithm Design, 1st edition cover 7.5 A First Application: The Bipartite Matching Problem

Class:
Maximum Flows and Minimum Cuts (Exercises)
Capacity Scaling Algorithm (Exercises)
Bipartite Matching
2 
4 
Before Class:
Max Flow Application to Bipartite Matching Pre Quiz
Algorithm Design, 1st edition cover 7.6 Disjoint Paths in Directed and Undirected Graphs
Algorithm Design, 1st edition cover 7.7 Extensions to the Maximum-Flow Problem
Algorithm Design, 1st edition cover 7.8 Survey Design
Algorithm Design, 1st edition cover 7.9 Airline Scheduling

Class:
Student Evaluations Bonus Credit Explanation
Disjoint Paths
Extensions to Max Flow
Survey Design
Airline Scheduling
5 
6 
Class:
Disjoint Paths
Extensions to Max Flow
Survey Design
Airline Scheduling
7 
8 
Before Class:
Algorithm Design, 1st edition cover 7.10 Image Segmentation
Algorithm Design, 1st edition cover 7.11 Project Selection
Algorithm Design, 1st edition cover 7.12 Baseball Elimination

Class:
Image Segmentation
Project Selection
Baseball Elimination
9 
Module 7: Intractability
11 
Before Class:
Algorithm Design, 1st edition cover 8.1 Polynomial-Time Reductions

Class:
Poly-Time Reductions
Packing and Covering Problems
12 
13 
Before Class:
Algorithm Design, 1st edition cover 8.2 Reductions via Gadgets: The Satisfiability Problem
Algorithm Design, 1st edition cover 8.3 Efficient Certification and the Definition of NP

Class:
Reductions via Gadgets: The Satisfiability Problem
Efficient Certification and the Definition of NP
14 
15 
Before Class:
Algorithm Design, 1st edition cover 8.4 NP-Complete Problems

Class:
NP-Complete Problems
16 
18 
Before Class:
Algorithm Design, 1st edition cover 8.5 Sequencing Problems

Class:
NP-Complete Problems
Sequencing Problems
19 
20 
Before Class:
Algorithm Design, 1st edition cover 8.6 Partitioning Problems
Algorithm Design, 1st edition cover 8.7 Graph Coloring

Class:
Partitioning Problems
Graph Coloring
21 
Due:
Exam 2 Preparation Game Questions
22 
Class:
Exam 2 Preparation Game (on Teams) (topics)
23 
25 
Thanksgiving Break
26 
Thanksgiving Break
27 
Thanksgiving Break
28 
Thanksgiving Break
29 
Thanksgiving Break
30 

Legend

Read
Algorithm Design Textbook Read sections in Algorithm Design
Watch video
Assignment (submit through CougarVIEW)
Project (submit through CougarVIEW)
CougarVIEW Quiz
Exam / Test