Assignment Schedule
Announcements, clarifications, corrections and revisions to assigment
specifications are posted to the
Announcements page.
Please read this page regularly.
- Assignment handout (PDF)
(PS)
- Due at start of tutorial on Friday, April 7.
- Typo: At the end of the question 4 introduction,
S should be defined as the
sum of ai
(not the sum of si).
The online version has been corrected.
- Clarification: For question 1, the definition of d(C)
mentions the "cost" of edges without being specific: there are two
notions of cost that we could mean (d(e) or d(e)*f(e)).
Fortunately, only one of these notions makes sense in the context of the
rest of the question. We leave it up to you to think about it and figure
out the correct interpretation.
In the definition of an augmenting cycle, the handout talks about the
corresponding undirected network -- this is just saying that C
is a is a cycle if we ignore the directions on the edge (or analogously,
is a cycle in the residual network).
- For question 2, it is acceptable to have exponentially many
constraints in your integer program (as a function of the number of
nodes in the graph). Also, you may find it helpful to consider subsets of
vertices and circuits in the graph, and to think about the ways in which
edges in the circuits interact with the subsets of vertices (of course,
your goal is to use this idea to write down linear constraints that ensure
any solution to your integer program yields a circuit in the graph).
- Initial marking scheme (the TA might have
made some adjustments)
- Sample solutions:
PDF or PS
- Assignment handout (PDF)
(PS)
- Due at start of tutorial on Friday, March 17.
- Be sure to show your work for question 1, and justify the correctness
and running time of your algorithms.
- You may use any results that are proved in the textbook, in lecture,
or in tutorial. For example, you do not have to reprove Ford-Fulkerson's
algorithm or closest pair of points algorithm if you use it to solve a
question on the assignment.
- Clarification: For question 2, you must give a divide-and-conquer
algorithm; any other type of algorithm will receive only part marks.
(The whole point of the question is to make sure that you review and
understand the closest-points algorithm presented in class.)
- The marks allotment was not included on the assignment handout.
It is 20-20-10-10 (for questions 1-4).
- Sample solutions:
PDF or PS
- Assignment handout (PDF)
(PS)
- Due at start of tutorial on Friday, February 17.
- Now due by Monday, February 27 at noon. Assignments may be handed into
the drop box near SB 1155 labelled "CSC373S" or given to the instructor.
If you hand in your assignment to the TA at the start of tutorial
on February 17, you will receive extra credit.
- Hint: for Q2, you might find it useful to store more than one
value at each location in the array.
- Assignment handout (PDF)
(PS)
- Due at start of tutorial on Friday, January 27.
- Clarification: At the end of question 3, you are asked to
"Prove that, for a
given set of boxes with specified weights, the greedy algorithm ...".
This means: "Prove that, for an arbitrary set of boxes with specified
weights, the greedy algorithm ...".
- Clarification:: For question 4, once you have an algorithm,
also give a short proof that your algorithm is correct.
A full proof is not necessary for this question.
You should also justify that your algorithm is efficient (i.e., polynomial).
- Solution hints
- Sample solutions:
PDF or PS
Submission instructions
Every assignment will consist of
a number of "pencil-and-paper" questions
(whose solution involves no programming and
can be handwritten or typed).
All assignments must be submitted directly to the TA
at the beginning of tutorial on the due date.
Late assignments will not be accepted
(including assignments submitted after the first 10 minutes of tutorial),
except in truly unusual circumstances.