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 Problem-II (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 Gale-Shapley algorithm (Slides, Notes) Cody Boppert
Sergey Cherny
Victoria Minorczyk
[KT, Sec 1.1]
Wed, Sep 12 Analyzing the Gale-Shapley 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 Gale-Shapley 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 Bellman-Ford Algorithm (Slides, Notes) Alexander Schieppati [KT, Sec 6.8]
Fri, Dec 7 Wrapup (Slides) [KT, Chap 8] Last Lecture (HW 10 in)