Course Home | Course Policies | Homework | Schedule & Lecture Notes

CS 3100: Algorithms
Fall 2017

Homework Assignments

Assignment Topic Due by 11:59pm Submission instructions
HW0 Homework 0: Necessary Background Wednesday, September 6 In class
HW1 Homework 1: Recursion Friday, September 15 In class
HW2 Dynamic Programming Friday, September 22 Oral grading
HW3 Greedy Algorithms Monday, October 2 In class
HW4 Graph Algorithms Friday, October 13 Oral grading
HW5 Max flows Monday, October 30 In class
HW6 Flows, NP-Hardness Wednesday, Nov. 8 In class
HW7 NP-Hardness and reductions Friday, Nov. 17 Oral grading
HW8 Approximation Wednesday, Nov. 29 On paper by 5pm
HW9 LP Friday, Dec. 8 On paper by 11am or oral

Homework Instructions and FAQ



How to schedule oral presentation homework

For oral homeworks, each group will schedule a presentation time with the professor. Watch the course webpage for announcements regarding this process. Each member in a group will present at least one problem from a given homework set. The assignment of who presents what will be done randomly at the beginning of the presentation session.

Form: How to write

Please be nice to the grader! Make it easy for me to see what you're doing. If your answers are hard to read, I'll be MUCH less sympathetic to your mistakes. All this goes for exam problems, too.

Content: What to write

Convince the grader that you understand exactly what you're doing.

Form: How To Present

The audience here will be considered "experts", since I'll obviously be familiar with the background material and the problem at hand. So you don't need to explain big O notation or any other background from the class, and you don't need to provide motivation. (After all, your motivation is probably that I assigned it!)

Interaction with the instructor

I will randomly assign to each person in your group a problem to present. Those not presenting should for the most part remain quiet, unless either the instructor or the person presenting requests help or clarification from another group member.

During your presentation, I may interrupt, ask questions, provide or ask for clarifying comments, point out flaws or counterexamples, or any other similar behavior. (Don't worry, I won't usually throw anything to get your attention.) Usually this can be taken as an indication that either you haven't made things clear or there is an error. It might also be that you've assumed too much of your tired, stressed, and overworked instructor. In any case, don't panic, because I'm not out to get you; just answer the questions to the best of your ability.

Part of the value is that you can get immediate, real-time feedback on your solutions. However, at some point it is very likely that you will find out that something is incorrect or unclear in a problem you are presenting. Don't panic! You can still get partial credit for these problems, and may even be able to fix the solution. Part of the value of this experience is learning to think on your feet while communicating your solutions.

Within reason, the instructor may allow you to react and modify your solutions. However, full points for content will only be awarded when initial solutions are correct. Yes, we realize that this gives oral presentation an advantage over written homework, since you are more likely to fix errors and get partial credit. Enjoy it!

One last comment. If you are totally stuck and can't remember how to solve the problem, but your homework partner remembers, you are allowed to ask for help. However, you will lose points for this, so try to avoid it! Make sure you all know how to solve every problem, so that you can try for full credit. However, if your answer is wrong and you can't fix it, you are better off asking for help and getting partial credit if your partner can get it correct - you'll only lose a few points off the total, so that is better than a 0.