Other resources/recommended reading (all on a 2 hour reserve in the library; or free):
TOPIC: Greedy algorithms. Dynamic programming. (Homework #1 due Sep. 13, exam #1 on Sep. 20.)
Reading:
homework 1
Problem sessions:
- Sep. 10 (Monday) 6:15pm - 7:15pm in Hylan 202 (Theodore Chapman)
- Sep. 11 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Peter Chen)
- Sep. 12 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Yu Chen)
- Sep. 12 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Petar Dinev)
- Sep. 17 (Monday) 6:15pm - 7:15pm in Hylan 202 (Petar Dinev)
- Sep. 18 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Peter Chen)
- Sep. 19 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Xingyu Wang)
- Sep. 19 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Hanlin Tang)
Aug. 30 Th - Introduction.
Sep. 4 Tu - When does greedy algorithm for the coin change problem work?
Sep. 6 Th - Dynamic programming for the coin change problem. Knapsack (integer weights).
Sep. 11 Tu - Knapsack revisited (integer values). Longest increasing subsequence.
Sep. 13 Th - Edit distance. Chain matrix multiplication.
Sep. 18 Tu - More dynamic programming problems.
Sep. 20 Th - EXAM #1 (topics: Greedy algorithms/Dynamic programming)
TOPIC: Graph algorithms. (Homework #2 due Oct. 11, homework #3 due Oct. 25, exam #2 on Nov. 1.)
Reading:
homework 2
homework 3
Problem sessions:
- Oct. 8 (Monday) 6:15pm - 7:15pm in Hylan 202 (Sofia Carrillo)
- Oct. 9 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Petar Dinev)
- Oct. 10 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Sofia Carrillo)
- Oct. 10 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Samuel Triest)
- Oct. 22 (Monday) 6:15pm - 7:15pm in Hylan 202 (Sofia Carrillo)
- Oct. 23 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yu Chen)
- Oct. 24 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Sofia Carrillo)
- Oct. 24 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Samuel Triest)
- Oct. 29 (Monday) 6:15pm - 7:15pm in Hylan 202 (Theodore Chapman)
- Oct. 30 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Yu Chen)
- Oct. 31 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Xingyu Wang)
- Oct. 31 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Samuel Triest)
Sep. 25 Tu - Finding connected components, DFS, testing whether graph is strongly connected.
Sep. 27 Th - Linearization (topological sorting). Strongly connected components.
Oct. 2 Tu - BFS, Shortest paths (Dijkstra)
Oct. 4 Th - Dealing with negative edge weights (Bellman Ford). Floyd-Warshal.
Oct. 9 Tu - Matchings I.
Oct. 11 Th - Matchings II.
Oct. 16 Tu - No class (Fall break).
Oct. 18 Th - Minimum spanning trees.
Oct. 23 Tu - Flows I.
Oct. 25 Th - Flows II.
Oct. 30 Tu - More graph algorithms.
Nov. 1 Th - EXAM #2 (topics: Graph algorithms)
TOPIC: Linear programming. Reductions (NP-completeness). (Homework #4 due Nov. 15, exam #3 on Nov. 29.)
Reading:
homework 4.
Problem sessions:
- Nov. 12 (Monday) 6:15pm - 7:15pm in Hylan 202 (Hanlin Tang)
- Nov. 13 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Peter Chen)
- Nov. 14 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Xingyu Wang)
- Nov. 14 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Hanlin Tang)
- Nov. 26 (Monday) 6:15pm - 7:15pm in Hylan 202 (Theodore Chapman)
- Nov. 27 (Tuesday) 6:15pm - 7:15pm in Goergen 109 (Peter Chen)
- Nov. 28 (Wednesday) 6:15pm - 7:15pm in Gavett 310 (Xingyu Wang)
- Nov. 28 (Wednesday) 7:40pm - 8:40pm in Hutchinson 473 (Petar Dinev)
Nov. 6 Tu - Modeling with linear programs I (classical problems).
Nov. 8 Th - Solving systems of equations (Gaussian elimination), solving systems on inequalities (Fourier-Motzkin elimination).
Nov. 13 Tu - Duality, Modeling with linear programs II (zero-sum games).
Nov. 15 Th - Linear programming for approximation (relaxation, rounding).
Nov. 20 Tu - NP completness, reductions I.
Nov. 22 Th - THANKSGIVING.
Nov. 27 Tu - NP completness, reductions II.
Nov. 29 Th - EXAM #3 (topics: Linear programming)
TOPIC: Divide and Conquer Algorithms (Homework #5 due Dec. 6.)
Grading
-
The grade for the course is computed from the exam grade (54%), the homework grade (10%), and
the final exam grade (36%).
Homework Rules
- Homework is collected on the due date, before class, in the classroom.
- No late homework will be accepted without instructor's
permission (a permission must be requested at least 24 hours
before the due date).
- You may work with other people on the
homework, but you must each write up your solutions separately
(without any written aid). If you work with other people, indicate
who you worked with on your solution.
Test Rules
- All tests are closed book. No text
or notes. No scratch paper allowed. No electronic devices (calculators, phones, computers, etc).
- There will be 3
full-class exams and a final exam. There will be no make-up exams.
This course follows
The University Policy on Academic Honesty .