Fall 2012 schedule (Previous schedules: 2009, 2010, 2011).
Date  Topic  Mini Project  Notes 
Mon, Aug 27  Introduction (Slides [19.5MB])  (HW 0 out)  
Wed, Aug 29  Main steps in algorithm design (Slides, Notes)  
Fri, Aug 31  Stable Marriage Problem (Slides, Notes)  [KT, Sec 1.1] (HW 0 in)  
Mon, Sep 3  No Class  Labor Day  
Wed, Sep 5  Stable Marriage ProblemII (Notes)  Jennifer Cockrell Remo Fiscione Spencer Whitt 
Guest Lecture by Jesse Hartloff 
Fri, Sep 7  Computing a Stable Matching (Slides, Notes)  Ho Jun Kang Christopher Mckieman Derek Williamson 
[KT, Sec 1.1] (HW 1 out) 
Mon, Sep 10  GaleShapley algorithm (Slides, Notes)  Cody Boppert Sergey Cherny Victoria Minorczyk 
[KT, Sec 1.1] 
Wed, Sep 12  Analyzing the GaleShapley algorithm (Slides, Notes)  Gino Buzzelli Dachi Chkadua Spencer McCreary 

Fri, Sep 14  What is an Efficient Algorithm? (Slides)  Aman Bhatia Tegan Leach Jinglun Li 
[KT, Sec 1.1, Sec 2.1, 2.2] (HW 1 in, HW 2 out) Reading assignment: [KT Sec 1.1, 1.2, 2.1, 2.2, 2.4] 
Mon, Sep 17  No Class  Rosh Hashanah  
Wed, Sep 19  Asymptotic Notation (Slides, Notes, Supplementary Notes)  Stephanie Clabeaux Stephen Slipoy Paul Theberge 
[KT, Sec 2.2] 
Fri, Sep 21  Analysis of GaleShapley Algorithm (Slides, Notes)  Jennifer Cordaro Aleksandra Patrzalek Crystal Wong 
[KT, Sec 2.3] (HW 2 in, HW 3 out) 
Mon, Sep 24  Graph Basics (Slides, Notes)  Jonathan Pahl Shintaro Matsumoto Andrew Wong 
[KT, Sec 3.1] Reading assignment: [KT, Sec 2.5] 
Wed, Sep 26  No Class  Yom Kippur  
Fri, Sep 28  Trees (Slides, Notes)  Sean Briceland Evan Dombrowski Khanh Nguyen 
[KT, Sec 3.1, 3.2] (HW 3 in, HW 4 out) 
Mon, Oct 1  Breadth First Search (Slides, Notes)  Peter Cageao Matthew McCauley Shek Yin Tam 
[KT, Sec 3.2] 
Wed, Oct 3  Depth First Search (Slides)  Sileem Farghaly Daniel Mohr Andrew Shufelt 
[KT, Sec 3.2] 
Fri, Oct 5  Runtime Analysis of BFS (Slides, Notes)  Damian Forbes Jim Kortleven Arjun Pravin 
[KT, Sec 3.3] (HW 4 in, HW 5 out) 
Mon, Oct 8  Runtime Analysis of DFS (Slides, Notes)  Daniel Bellinger Michael Chen Matthew Hogan 
[KT, Sec 3.3] Reading Assignment: [KT, Sec 3.3, 3.4, 3.5] 
Wed, Oct 10  Topological Ordering (Slides, Notes)  Jake Breindel David Fischer Justin Lawrence 
[KT, Sec 3.6] 
Fri, Oct 12  Greedy Algorithms (Slides, Notes)  (HW 5 in)  
Mon, Oct 15  Interval Scheduling (Notes)  Stacey Askey Sarah Michalski Jen Treacy 
Guest lecture by Jesse Hartloff [KT, Sec 4.1] 
Wed, Oct 17  Chadray Kishbaugh Adrianne Mende George Pineda 

Fri, Oct 19  Mid term exam  In class  
Mon, Oct 22  Scheduling to Minimize Lateness (Slides, Notes)  Kunal Ratan Arora Nikhil Jain Deeksha Kumar 
[KT, Sec 4.2] Reading Assignment: [KT, Sec 4.1] 
Wed, Oct 24  Greedy Algorithm for Scheduling to Minimize Lateness (Slides, Notes)  Philip Bozak Benjamin Demmer Devin Toth 
[KT, Sec 4.2] 
Fri, Oct 26  Analyzing the Greedy Algorithm (Slides, Notes)  Qing Liu Masa Yaegashi Chunyang Zhu 
[KT, Sec 4.2] (HW 6 out) 
Mon, Oct 29  Dijkstra's Shortest Path Algorithm (Slides, Notes)  Robert Hansen Michael Hasssan Kevin Jones 
[KT, Sec 4.4] 
Wed, Oct 31  Analyzing Dijkstra's Algorithm (Slides, Notes)  Joe Crawford Shannin Ciprich Jean D. Labatte 
[KT, Sec 4.4] 
Fri, Nov 2  Minimum Spanning Tree (Slides, Notes)  Andrew Webster  [KT, Sec 4.5] (HW 6 in, HW 7 out) 
Mon, Nov 5  Correctness of Kruskal and Prim's Algorithms (Slides, Notes)  [KT, Sec 4.5]  
Wed, Nov 7  Cut Property Lemma (Slides, Notes)  Jeff Gerfin Eric To 
[KT, Sec 4.5] Reading Assignment: [KT, Sec 4.5, 4.6] 
Fri, Nov 9  Merge Sort (Slides, Notes)  [KT, Sec 5.1] (HW 7 in, HW 8 out)  
Mon, Nov 12  Solving Recurrences (Slides, Notes)  [KT, Sec 5.1, Sec 5.5] Reading Assignment: [KT, Sec 5.2] 

Wed, Nov 14  Integer Multiplication (Slides, Notes)  Carl Smith Burton Wu 
[KT, Sec 5.5] 
Fri, Nov 16  Counting Inversions (Slides, Notes)  [KT, Sec 5.3] (HW 8 in, HW 9 out)  
Mon, Nov 19  Closest Pair of Points (Slides, Notes)  [KT, Sec 5.4]  
Wed, Nov 21  No Class  Fall Recess  
Fri, Nov 23  No Class  Fall Recess  
Mon, Nov 26  Kickass Property Lemma (Slides, Notes)  Bartek Karmilowicz Tam Mai Amol Patil 
[KT, Sec 5.4] 
Wed, Nov 28  Weighted Interval Scheduling (Slides, Notes)  {KT, Sec 6.1]  
Fri, Nov 30  Iterative Dynamic Programming (Slides, Notes)  Mike Philips  [KT, Sec 6.1, 6.2] (HW 9 in, HW 10 out) 
Mon, Dec 3  Shortest Path with Negative Edge Weights (Slides, Notes)  [KT, Sec 6.8]  
Wed, Dec 5  BellmanFord Algorithm (Slides, Notes)  Alexander Schieppati  [KT, Sec 6.8] 
Fri, Dec 7  Wrapup (Slides)  [KT, Chap 8] Last Lecture (HW 10 in) 