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

CS 3100: Algorithms
Fall 2019

Homework Assignments

Assignment Topic Due by 11:59pm Submission instructions
HW0 Homework 0: Necessary Background Wednesday, September 4 Written assignment
Due in class
Complete individually
HW1 Homework 1: Recursion Friday, September 13 Written assignment
Due in class
May work in groups
HW2 Homework 2: Recursion and Backtracking Thursday and Friday, September 19-20 Oral grading
May work in groups
HW3 Homework 3: Dynamic Programming Monday, Sept. 30 Written assignment
Due in class
May work in groups
HW4 Homework 4: Greedy Algorithms Monday and Tuesday, October 7-8 Oral grading
May work in groups
HW5 Homework 5: Graphs Wednesday, Oct. 23 Written assignment
Due in class
May work in groups
HW6 Homework 6: MST and flows Monday and Tuesday, Nov. 4-5 Oral grading
May work in groups
HW7 Homework 7: Flows and shortest paths Friday, Nov. 15 Written assignment
Due in class
May work in groups
HW8 Homework 8: Shortest paths and Hardness Monday, Nov. 25 Written assignment
Due in class
May work in groups
HW9 Homework 9: NPHardness Wednesday, Dec. 4 Written assignment
Due in class
May work in groups

Homework Instructions and FAQ

Logistics

Format


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.