COM304: Algorithm Design and Analysis
Spring 2024
Course Schedule
Note: KT refers to the KleinbergTardos text, DPV refers to DasguptaPapadimitriouVazirani. All books are on reserve in Shain.
Date 
In Class 
Homework 



1. 
This course, syllabus, policies, etc Chapter 1  Introduction 1.1 Stable Matching 
HW 0 (item 0 due tonight, items 03 due before class on Wed, Jan 24; items 47 due by Friday, Jan 26) 0. Complete the HW group survey form linked from the moodle page. I will plan to post your HW groups on Wed. 1. Read the entire syllabus (note or post to moodle any questions you have) 2. Read chapter 0.1 of DPV (and 0.2 is recommended too) 3. Read the preface of KT (at least through “Pedagogical Features and Supplements” section) 4. More reading in KT: Chapter 1.1. 5. Complete: Chapter 1, exercises 1 and 2 in KT. You don’t need to use LaTeX yet for typesetting this one, but this miniHW is a good chance to start practicing with it without any real pressure… Submit to moodle as a pdf or image file. If you don’t mind, please create your Overleaf accounts using my referral link. 6. Schedule at least two weekly meeting times of two hours each with your groups. Group meetings can begin this week if you wish, but really must begin with HW1 this weekend. Add your group’s scheduled meeting times and locations to the shared COM304 HW calendar. (Add it as a repeating event. You might have to add the event to this shared calendar via your own google calendar by first adding the class calendar to the view of your own Google calendar.) 7. Let me know (via moodle forum or email) if you have any questions/comments/concerns! All moodle forum posts/comments/questions count toward class participation. 
2. 
1.1 Stable Matching, cont’d 
HW 1 (due Fri, Feb 2)
· Review chapter 1.1 (from last week’s HW) and then read Solved Exercises 1 and 2 (starting on page 19). · Read chapters 2.12.2. · Also scan chapter 2.3 for the runtime analysis of GS. · Post any questions/comments about the reading to the moodle forum
· Chapter 1, exercises 4 and 6 in KT. See bullet three for more info. · Chapter 2, exercise 2. Note that you must fully justify your answers for this exercise for full credit. · Typeset your writeup using LaTeX and submit it as a pdf to moodle. Remember that for questions like 1.4 and 1.6, you always need to provide three things : (1) your algorithm for solving the problem, (2) a runtime analysis of your alg, and (3) a proof of correctness, i.e., a written argument that shows the algorithm always works correctly on any input. See HW policy in the syllabus for more details.

Chapter 4 – Greedy Algorithms 
HW 2 (due Fri, Feb 9) 1) Reading: a) Solutions to HW1 (solution summaries from KT and sample student solutions will be posted to moodle). Please post any questions you have about HW1 to the forum. b) Carefully read and understand all of 0.3 of DPV (on reserve in Shain). Post your questions/comments to the moodle forum. c) Read the rest of Chapter 2 of KT. Post any questions to the forum. d) Chapter 4.1 of KT. Post any questions to the forum. e) Solved Exercise 1 of Chapter 4 of KT (starting on page 183). Post any questions to the forum. 2) Complete: a) Chapter 2, exercises 3 (as always, you must fully justify your answers) b) Chapter 4, exercise 3, 5. Remember to give your algorithm, its runtime analysis, and the proof of its correctness for each problem. c) Optional for Black History Month: watch the awesome and inspiring movie, Hidden Figures (link to movie via moodle). Then post a few sentences to the moodle forum about what you found surprising or interesting about the movie. You can also do a little extra research and mention any historical inaccuracies of the movie if you wish. I’ve also posted the acclaimed Marvel superhero movie Black Panther there for you to enjoy as well… 

3. 
4.1 Interval Scheduling 

4. 
4.1 Interval Partitioning (proof of ESF optimality using structural properties of the problem) 



5. 
4.2 Scheduling to Minimize Lateness (proof of EDF optimality by exchange argument) 
HW 3 (due Fri, Feb 16) 1) Reading: a. Solutions to HW2. Post any questions you have to the forum. b. Chapter 3, up through 3.3. Emphasis on the part on “Representing Graphs” in 3.3. c. Chapter 4.2, 4.4 and 4.5 of KT. (Reading 4.3 is good too, but optional.) Post any questions to the forum. d. Solved Exercises 2 of Chapter 4 of KT (starting on page 185). 2) Complete: a. Chapter 4, exercises 2b and 6.
[Hint: for #6 follow the idea/structure of the proof that greedy EDF
is optimal for minimizing max lateness] b. Trace through Dijkstra’s on the example input instance on slide 3 of these slides. Provide a table showing in each iteration: · the set S (the explored set) · the value of d(v) for each node v in each iteration · note that KT calls this value d’(v) until the node gets added to S · the node chosen to be added to S This trace can be hand drawn (as in this example I did by hand) rather than typeset to save time if you wish. As seen in the photos, please show the “frontier” of S as it changes in each iteration, and highlight the edges used for each shortest path. Note that the var name π(v) is used for d’(v) in the photos, but in class we just called it d(v) the whole time. c. Also
complete (start these after Monday’s class):

6. 
4.4 Shortest Paths in a Graph 




HW 4 (due Fri, Feb 23) 1) Reading: a. Solutions to HW3. Let us know if you have any questions! b. Review chapter 4.5, then read chapters 5.15.3 c. Solved Exercise 3 of chapter 4 (pg 187) and solved exercises 1 and 2 of Chapter 5 of KT (starting on page 242). 2) Complete: a. Complete the two remaining slides of the MST packet from class. · The cycle property was first stated earlier on slide 7, and its proof follows the idea of the proof of the cut property. (A proof can also be found in your reading or on the old zoom videos of the class I have posted to moodle.) · On the last remaining slide, for the proof of Kruskal’s correctness, refer back to slide 5 for the def of Kruskal’s alg. For the first blank of Case 2, the name of the edge being referenced is (u,v), as illustrated. b. Chapter 4, exercise 9 c. Recall
the CountAndSort algorithm we learned in class for
mergesorting a list of values while also counting
the number of inversions in it. Note that this alg
is also given in section 5.3 of KT, where it is called SortandCount(). · Trace (by hand) the CountAndSort algorithm
on the following list of integers: [64, 15, 91, 29, 99, 80, 27, 89,
11]. Show how the action unfolds by drawing a recursive call tree that
shows the (sub)list being passed into each node of the tree, and also show
what happens to the two returned (sorted) lists in each node of the
tree. You can be creative in how you choose to depict the action, as
long as you are fully illustrating all the recursive calls and the values
being returned (inversion counts) from each call. · On the illustration of your trace, number each recursive call in chronological order of the algorithm’s execution
so that it is clear which recursive call is made first, second, third,
etc. d. Chapter 5, exercise 1.
Note that rather than actual “runtime” you
are analyzing here the number of “database queries” (The questions don’t say
how much runtime each query actually takes.) But the number of queries
should still be expressed in bigO notation, as it would be with runtime.) 

7. 
4.5 The Minimum Spanning Tree Problem 

8. 
Chapter 5 – Divide and Conquer 5.1 Mergesort 5.3 Counting inversions 

HW 5 (due Fri, Mar 1) 1. Reading: a. Solutions to HW 4. Post your questions about them to moodle. b. Review KT sections: 5.15.3. c. Read 5.4, 6.1 and 6.2 d. Review solved exercises 1 and 2 of Chapter 5. e. Read solved exercise 1 of Chapter 6. 2. Complete: · Chapter 5, exercise 3. Note that rather than actual “runtime” you are analyzing here the number of “invocations to the equivalence tester.” (The problem doesn’t give the actual runtime of each invocation.) The number of queries/invocations should still be expressed in bigO notation, as it would be with runtime. · Chapter 6, exercises 1 and 2 

9. 
5.4 Finding the closest pair of points 

10. 
Chapter 6 – Dynamic Programming 6.1 Weighted Interval Scheduling 6.2 Memoization or Iteration 

11. 
6.4 The Subset Sum Problem 
HW 6 (not actually due until Fri, Mar 8, but you
can pretend it is due Wed, Mar 6 if you prefer) 1. Reading: a. Solutions to HW 5. Post your questions about them to moodle. b. Review KT chapters 6.16.2 c. Read KT chapters 6.36.8 (although 6.3, 6.5 and 6.7 are optional) 2. Complete: Chapter
6, exercises 3 and 4 Note: The HW above is shorter/smaller than
usual since the takehome midterm will hopefully be distributed in class on Wed Mar
6. It will not be due until Fri, March
29, and you are not expected to begin the exam until after the break. But I know that some students would like to
have it in hand before the break in case they have time to work on it over
the break and reduce their workload upon their return. And our last meeting before the break is
Wed, so I plan to distribute it that day if possible. Since having two assignments on hand at
once will feel stressful to some, I wanted to make this HW smaller, so people
could choose to finish it by Wed instead of Fri if they prefer. 
12. 
6.4 The Knapsack Problem and 

13. 
6.6 Edit Distance (i.e. Sequence Alignment) cont’d, and 
Additional reading/review (may be completed after HW 6 exercises are submitted). · Note that I have posted some dynamic programming review videos to moodle. These can be helpful if you were absent or just need a recap of what we learned in class. · Read the HW 6 solutions that will be posted to moodle. ·
Read through all the other chapter 6 exercises to see the broad domain of problems that can be solved
efficiently (in poly time) using
dynamic programming!
1) If you are particularly interested in any, let me know and I’ll share a sample solution for it with you! Midterm Exam due Friday, March 29 in hard copy in my office. If I am not in, please slide it under my office door. 
14. 
6.8 Shortest Paths (with negative edge weights) 

Mar 924: SPRING BREAK =) 

15. 
Chapter 7 –
Network Flow 7.1 The
MaxFlow Problem and FordFulkerson 
HW 7 (HW due Fri, April 5) 1. Reading: a. Review Chapter 3, up through 3.3. Emphasis on the part on “Representing Graphs” in 3.3. b. Chapters 7.1  7.3. 2. Complete: a. Illustrate/trace through each iteration of the FordFulkerson Max Flow Algorithm on this flow network. To make sure the illustration is clear, you should separately draw for each iteration: (1) original graph with the current flow values on each edge, leaving edge capacities as “denominators,” and (2) the residual graph with the next augmenting path highlighted in it and the bottleneck edge value shown somehow. To see what I mean, refer to the FordFulkerson demo on page 16 (slide 17) of this presentation. Download and view it on full screen so you can watch how the alg unfolds as an animation with each click. Each slide/click represents the next iteration of the algorithm. The top figure of each slide shows the current/updated flow, and the bottom shows the residual graph for that flow. For your trace though, please greedily choose the augmenting path with the largest bottleneck edge value in each iteration. Please remember to clearly highlight the next augmenting path in each residual graph (shown as the dark bolded paths in the demo). b. Chapter 7, exercises 15. Remember to explain all answers rather than simply state them. Please draw diagrams and if you are attaching them separately or to the end of your pdf, please reference them from the same place you give your answers. You can just write/draw everything by hand, but please do so neatly! Color coding your drawings with highlighters or colored pens/pencils is strongly encouraged. 
16. 
7.2 The Max Flow Min Cut Theorem (7.3 Good Augmenting Paths) 




17. 
7.5 Bipartite Matching Problem 
HW 8 (due Fri, April 12) 1) Reading: a) Solutions to HW7. b) Chapters 7.57.7 (7.4 is optional) c) Solved Exercises 1 and 2 d) Post any questions/thoughts to moodle. 2) Complete: Chapter 7, exercises 6, 7, 8. Remember, solve these problems by reducing/transforming them to problems we have already solved, like Max Flow or Max Bipartite Matching. 
18. 
7.7 The Circulation Problem (with Demands, and then with Lowerbounds) 

19. Mon Apr 8 
7.8 Survey Design 7.9 Airline Scheduling 7.12 Baseball Elimination skipped =( 
HW 9 (due Fri, April 19) 1) Reading: a. Solutions to HW 8 b. The rest of chapter 7, and then chapter 8.1 c. Also read (but do not do/submit): all the other exercises of chapter 7 to see the broad domain of problems that can be solved using Network Flow! If you are particularly interested in any let me know and I’ll share the solution for it with you! 2) Complete: Chapter 7, exercises 9,
14a, 16, but/and… ·
No need to solve 9
completely please, instead just write a brief few lines
on how this problem is similar/related/connected to exercise 7 from last HW
in the same chapter. ·
Solve exercise 14a
completely, as usual: alg def, runtime analysis, proof of correctness ·
Same for exercise
16. Also note that this textbook was
written before the rise/dominance of Google, hence the reference in exercise
16 to Yahoo! You can just replace the word
“Yahoo!” with Google in the problem statement if you like and it is still as
relevant as ever. · Extra required problem: i) Show how a blackbox solver for the Independent Set Problem could be used to solve the Interval Scheduling Problem that we saw when we studied Greedy algorithms early in the semester (defined in chapter 1 and revisited in chapter 3 and on the midterm). I.e., reduce the Interval Scheduling Problem to the Ind. Set Problem in polytime. (You can use the decision version of interval scheduling if you’d like, defined in exercise 8.1.) ii) The fact that you’ve reduced Interval Scheduling to Independent Set in part (i) indicates to us that one problem is “at least as hard as” the other. State which is which, and explain why/how the reduction indicates this to you. 
20. Wed Apr 10 
Chapter 8  Computational Intractability P vs NP overview 8.1 Polytime Reductions and relative hardness of problems, Independent Set, Vertex Cover 

21. 
8.2 NPcompleteness 8.4 Vertex Cover, Set Cover 
HW 10 (due Fri, April 26) 1) Reading: a. Solutions to HW 9 b. Chapters 8.18.4. c. Solved
Exercises 1 on page 500 2) Complete: a)
Chapter 8, exercises 1, 2, and 3. (Note: for exercise 1 please justify your answers
to the questions only using the facts we have already established about relative
hardness of VC, IS, and interval scheduling. Please do not do any
reductions for these.) b) Watch this video about P vs NP with people who are not in our class, like family, friends, or relatives. Note their questions/comments afterward, and see if you can answer or elaborate on them, and post at least one or two sentences about the screening experience/discussion to our class moodle forum. 3) Extra Credit
(not difficult, due any time before the end of classes): ·
In class, Jun
suggested a very reasonable greedy algorithm for the Independent Set problem
where we greedily pick vertices in lowestdegreefirst order. (The degree of a vertex is the number of
edges incident on the vertex, i.e., how many other vertices it is connected
to by a direct edge). The idea being:
perhaps if we start with friends who have the least conflict with our other
friends, then we might maximize how many we can invite to our conflictfree
party. ·
Greedy Alg: o
Find the vertex v
with lowest degree (fewest incident edges) o
Add v to S, and
remove it, along with any vertices connected to it (and all their edges) from
the graph o
Repeat the above two
steps until the graph is empty · Show that this algorithm is not optimal, in that it does not always return the maxcardinality independent set of the graph. I.e., give a counterexample, a bad input instance of Ind Set, for this greedy algorithm. 
22. 
8.2 cont’d, the Satisfiability Problem (3SAT) and its reduction to Ind Set. 

23. 
8.5 Directed Ham Cycle to Ham Cycle, 3SAT to Ham Cycle 
HW 11 (due Fri, May 3) 1. Reading: Chapters 8.58.7, and Solved Exercises 1 and 2 starting on page 500. 2. Complete: Chapter 8, exercises 4, 5, and 8. · For all parts of exercise 4, the proofs of correctness are not required; only the alg defs please. You may also assume we already know all of these are in NP, and just focus on the “hard” part (no pun intended). 3. Read (but no need to complete) exercises 11 and 12 as well. (Notice how Hitting Set from exercise 5 can be reduced to Plot Fulfillment of exercise 11…) 
24. 
TSP, 3D Matching 

25. Mon 
Partitioning Problems 8.6 3D Matching 
HW 12 (smallerHW due Wed, May 8) 1) Reading: a) Chapters 8.88.10 b) Read through all the chapter 8 exercises you were not assigned and mentally file away all these problems as being NPhard. c) Chapter 11.1 2) Optional, yet just as fascinating reading: a) chapter 9: intro and 9.1 [problems beyond NP] b) chapter 10: just the intro [solving special cases of NPhard problems] 3) Complete: Chapter 8, exercises 17 and 19, but no analyses required, only algorithm definitions. You may also assume all problems are in NP without showing/proving it. So you only need to worry about the NPhard part of NPcompleteness. 
26. 
8.8 Numerical Problems and NPcompleteness wrapup 

27. 
Chapter 11 – Approximation Algs 11.1 The Load Balancing Problem (a 2approximation, and a
3/2approx) 
Some extra credit exercises (due any time before
the end of exams): [Note that HW grades can go over 100% and that these bonus values are estimated percentages, not raw points… the number of raw points depends on the total raw points of each HW…] · [Up to +4% on a HW] Chapter 8, exercise 26 (we actually already saw one solution idea for 26 in class so this is just turning it into a formal writeup… we did this in class by reduction from Subset Sum… bonus points for giving a reduction using different values for the last two pieces of “treasure” than the ones we used in class.) · [Up to +3% on a HW] The numbers for the reduction of 3D matching to subset sum in our example from class were base 10 numbers. Will base 10 numbers always work for all 3D matching inputs? Why/why not? What base do the numbers need to be in general? · [Up to +4% on a HW] Show the load balancing problem we learned about in class (chp 11.1) is NPhard by reduction from the Partition problem (two pirates splitting their treasure equally). · [Up to +3% on a HW] From a student: in class we saw a simple greedy algorithm that achieves a 2approximation for the load balancing problem. I.e., we proved L <= 2L*, where L was the makespan of our greedy alg, and L* was the makespan of the optimal assignment. A student after class claimed that in fact it could be proven that L < 2L*. I.e., that the inequality could be a strict one. Can you modify the proof from class/reading to get this slightly stronger result? · [+4% on a HW]
Prove that the greedy LPT (longest processing time first) load balancing
algorithm we discussed in class gives a 3/2approximation to the
optimal makespan (this is actually in
your reading, and we went over it in class quickly, but now is your chance to
write it up nicely in your own words). ·
[+4% on a HW] Find an input
instance where the greedy LPT alg does
not find the optimal makespan for the load
balancing problem. The worse the ratio of your instance to the
optimal makespan the more bonus you
get. =) · Prove a simple polytime 2approximation for the minimum Vertex Cover (VC) problem. We will also show that this approximation is tight. As you might recall, the VC problem says: given a graph, find a minimumcardinality set of vertices that "covers" all the edges. Consider the following algorithm: · Pick any edge e = (u,v) from the graph and add both its endpoints (u and v) to the vertex cover · Delete/remove that edge e from the graph. · Also delete/remove its endpoints (u and v) from the graph, along with any edges that were covered by u and v. · Keep repeating the above three steps until no more edges remain in the graph i. [Up to +3% on a HW] Give an input instance that shows this algorithm might sometimes give a vertex cover that twice the size of an optimal vertex cover. ii. [Up to +4% on a HW] Prove the following claim: the above algorithm always (on any input graph) gives a vertex cover that is no more than twice the size of an optimal vertex cover. Interestingly, it is widely believed that unless P = NP, there is no better approximation than this for Vertex Cover! Also interesting: even though, as we saw in class, vertex cover and independent set are essentially "equivalent problems," there is actually no 2approximation for I.S... it's in fact been proven that I.S. cannot be approximated to within any constant factor unless P = NP. Huh! · [+3% on a HW] Find a bad input instance for the following Vertex Cover Strawman Alg #1: Pick an arbitrary vertex with at least one uncovered edge incident to it, put it into the cover, and repeat. See if you can find an instance that makes the algorithm fail: one where its outputted vertex cover is much bigger than the optimal vertex cover. The worse your instance makes the alg mess up the better. =) · [+3% on a HW] Find a bad input instance for the following Vertex Cover Strawman Alg #2: Similar to above, but this time greedily pick the vertex that covers the most uncovered edges in each iteration. See if you can find an instance that makes the algorithm fail: one where its outputted vertex cover is bigger than the optimal vertex cover. The worse your instance makes the alg mess up the better. =) ·
[+4%
on a HW] Chapter 11, exercise 1 ·
[+3% on a HW] Devise a noinstance for
3sat. (See graph coloring worksheet, where this bonus was mentioned.) 
28. 
Chapter 13 – Randomized Algorithms 13.4 A randomized approximation for max 3sat 13.5 Randomized Divide and Conquer: Quicksort 

May 
Review Days and Final Exams 
Final Exam period ends on May 13 for graduating seniors and May 15 for everyone else. 