|
|
Homeworks and Group Project
See the calendar for deadlines.
Homework
Homework will be collected at the beginning of the class on the day it is due. This means that homework is due at 9:30am. After 9:40am it will be considered late. Homework may be submitted up to one day late (until 9:40am on the following day) for a penalty of 10% off the assignment grade. Homework will not be accepted after one day late. See guidelines for how to write-up algorithms. If you are unclear what is expected in a proof write-up, look at Prof. Cusick from UC Fresno's tutorial on the basics of proof writing.
- Homework 1: Exercises 2.2, 2.5, 3.1, 3.5, 4.5, 4.8, 4.18 from the textbook.
- Homework 2: Exercises 5.3, 5.5, 6.1, 6.24 from the textbook.
- Homework 3: Exercises 7.2, 7.5, 7.9, 7.15 from the textbook. All algorithm write-ups (algorithms are requested for 7.9 and 7.15 b) should follow the guidelines.
- Homework 4: Exercises 8.1, 8.9, 8.14 from the textbook. Additional problem.
- Homework 5: Exercises 11.1, 11.4, 11.10 from the textbook. Additional problem. For 11.4: Give an LP and accompanying algorithm to approximately solve this problem. You do not need to prove that the LP is correct, but should give some explanation as to why your algorithm gives a b-approximation of the optimal solution. Note: Hitting Sets are defined in problem 8.5.
Group Project
You must submit your group project electronically using the submit server. You will log in
to the submit server using your University Directory ID. Once you log in,
click on the submit link for the project you wish to submit, and
follow the directions. I will consider the most recent submission by any member of the team to be the final version. Public tests ensure that your solution has output in the expected format. You should pass these tests by the second checkpoint.
Answers to questions your classmates have asked:
- If more students sign up for a class than can fit in the largest room, are multiple section of that class created? No.
- Are there ever sections of a class? No. These classes are "simple classes," like ours, with exactly one teacher and some number of students that all fit into a single room.
- What about the edge cases when there might be more students than could actually ever be scheduled or more classes than could be scheduled? See the code for make_random_input.pl to see what I'm assuming. As long as your solution works for any instance that make_random_input.pl generates, it is complete enough. (For this project we care most about average inputs, and less about pathological ones.)
- What if a class isn't scheduled? How do I include it in the output schedule? Just don't include that class at all.
|