CIS 3200 (Spring 2024)
Week 1 |
||||
| L01 | Mon, Jan 22 | Course description, algorithms, worst-case complexity | ||
| HW 1 released on Mon, Jan 22 | ||||
| L02 | Wed, Jan 24 | Insertion-sort and Merge-Sort (quick-sort) | ||
| HW1 due @ 11:59 pm on Fri, Jan 26 | ||||
| Independent HW 1 released on Fri, Jan 26 | ||||
Week 2 |
||||
| L03 | Mon, Jan 29 | Sorting lower bounds and linear-time sorting | ||
| Independent HW 1 due @ 11:59 pm on Mon, Jan 29 | ||||
| HW2 released on Mon, Jan 29 | ||||
| L04 | Wed, Jan 31 | Median and Selection, Recurrences and substitution method. | ||
Week 3 |
||||
| L05 | Mon, Feb 05 | Master theorem, Convex Hull | ||
| L06 | Wed, Feb 07 | FFT or Matrix Multiplication | ||
| HW2 due @ 11:59 pm on Wed, Feb 07 | ||||
| Independent HW 2 released on Wed, Feb 07 | ||||
| Independent HW 2 due @ 11:59 pm on Sat, Feb 10 | ||||
| HW 3 released on Sat, Feb 10 | ||||
Week 4 |
||||
| L07 | Mon, Feb 12 | dynamic programming | ||
| L08 | Wed, Feb 14 | dynamic programming | ||
| HW3 due @ 11:59 pm on Sun, Feb 18 | ||||
| IHW 3 released on Sun, Feb 18 | ||||
Week 5 |
||||
| L09 | Mon, Feb 19 | dynamic programming | ||
| Ex1 | Wed, Feb 21 | Midterm 1 Wed 03:30 pm - 05:00 pm @ Towne 100 [exam info] | ||
| IHW3 due @ 11:59 pm on Fri, Feb 23 | ||||
| HW4 released on Fri, Feb 23 | ||||
Week 6 |
||||
| L10 | Mon, Feb 26 | greedy algorithms | ||
| L11 | Wed, Feb 28 | greedy algorithms | ||
Week 8 |
||||
| L12 | Mon, Mar 11 | Graphs, BFS, DFS | ||
| IHW4 released on Mon, Mar 11 | ||||
| L13 | Wed, Mar 13 | Minimum spanning tree, Union-Find | ||
| HW4 due @ 11:59 pm on Wed, Mar 13 | ||||
| IHW4 due @ 11:59 pm on Fri, Mar 15 | ||||
| HW5 released on Fri, Mar 15 | ||||
Week 9 |
||||
| L14 | Mon, Mar 18 | Shortest path: Dijkstra's alg | ||
| L15 | Wed, Mar 20 | Bellman-Ford | ||
| IHW5 released on Sun, Mar 24 | ||||
Week 10 |
||||
| L16 | Mon, Mar 25 | All-pairs shortest paths | ||
| HW5 due @ 11:59 pm on Tue, Mar 26 | ||||
| L17 | Wed, Mar 27 |
The flow problem on graphs or review
Note: "General Flow Notes" is a comprehensive overview of flow topics and Ford-Fulkerson, while the other notes hone in on specific lectures.
|
||
| IHW6 released on Thu, Mar 28 | ||||
| IHW5 due @ 11:59 pm on Thu, Mar 28 | ||||
Week 11 |
||||
| L18 | Mon, Apr 01 | Ford-Fulkerson | ||
| Ex2 | Wed, Apr 03 | Midterm 2 Wed 03:30 pm - 05:00 pm @ Towne 100 [exam info] | ||
| HW6 released on Wed, Apr 03 | ||||
| IHW6 due @ 11:59 pm on Wed, Apr 03 | ||||
Week 12 |
||||
| L19 | Mon, Apr 08 | Max-Flow, Min-Cut Theorem | ||
| L20 | Wed, Apr 10 | Capacity-scaling algorithms | ||
Week 13 |
||||
| L21 | Mon, Apr 15 | Bipartite matching | ||
| IHW7 released on Mon, Apr 15 | ||||
| HW6 due @ 11:59 pm on Mon, Apr 15 | ||||
| L22 | Wed, Apr 17 | min-cost bipartite matching | ||
| IHW7 due @ 11:59 pm on Fri, Apr 19 | ||||
Week 14 |
||||
| L23 | Mon, Apr 22 | Computational hard problems | ||
| HW7 released on Mon, Apr 22 | ||||
| L24 | Wed, Apr 24 | poly-time reductions, Cook-Levin theorem | ||
Week 15 |
||||
| L25 | Mon, Apr 29 | Reductions | ||
| L26 | Wed, May 01 | Review | ||
| HW7 due @ 11:59 pm on Wed, May 01 | ||||