Fall 2008
Term Test # 1 50 minutes
NONE (in particular, no calculator)
CSC 373 H1
Student Number: Last (Family) Name(s): First (Given) Name(s):
Duration: Aids Allowed:
Do not turn this page until you have received the signal to start. In the meantime, please read the instructions below carefully.
This term test consists of 2 questions on 10 pages (including this one), printed on both sides of the paper. When you receive the signal to start, please make sure that your copy of the test is complete, fill in the identi- fication section above, write your student number where indicated at the bottom of every odd-numbered page (except page 1), and write your name on the back of the last page.
Answer each question directly on the test paper, in the space provided, and use the reverse side of the pages for rough work. If you need more space for one of your solutions, use the reverse side of a page and indicate clearly the part of your work that should be marked.
In your answers, you may use without proof any result or theorem cov- ered in lectures, tutorials, homework, tests, or the textbook, as long as you give a clear statement of the result(s)/theorem(s) you are using. You must justify all other facts required for your solutions.
Write up your solutions carefully! In particular, use notation and ter- minology correctly and explain what you are trying to do — part marks will be given for showing that you know the general structure of an answer, even if your solution is incomplete.
If you are unable to answer a question (or part), you will get 20% of the marks for that question (or part) if you write “I don’t know” and nothing else — you will not get those marks if your answer is completely blank, or if it contains contradictory statements (such as “I don’t know” followed or preceded by parts of a solution that have not been crossed off).
Marking Guide
# 1: /14 # 2: /19
TOTAL: /33
Page 1 of 10 Good Luck!
over. . .
Use this page for rough work — clearly indicate any section(s) to be marked.
Page 2 of 10 cont’d. . .
Fall 2008 Term Test # 1 CSC 373 H1 Question 1. [14 marks]
You are consulting for a trucking company that does a large amount of business shipping packages from Toronto to Montr ́eal. The volume is high enough that they have to send a number of trucks each day between the two locations. Trucks have a fixed integer limit W > 0 on the maximum amount of weight they are allowed to carry. Boxes arrive at the Toronto loading platform one by one, and each package i has a positive integer weight wi W . The loading platform is quite small, so at most one truck can be at the platform at any time. Company policy (and the limited space available at the platform) requires that boxes are shipped in the order they arrive—there would be complaints if boxes made it to Montr ́eal out of order!
At the moment, the company is using a simple greedy algorithm for packing: they pack boxes in the order they arrive (as required), putting as many boxes as possible in each truck without exceeding the weight limit W, i.e., whenever the current box would make the load exceed the weight limit W, they send the truck on its way and keep the box for the next truck. But they wonder if they might be using too many trucks, and they want your opinion on whether the situation can be improved: maybe one could decrease the number of trucks needed by sometimes sending off a truck that was less full, and in this way allow the next few trucks to be better packed? More formally, the current algorithm used by the company can be written down as follows.
TruckPacking(W, w1, w2, . . . , wn):
k=1
Tk = [w1] t=w1
S=[Tk]
for i = 2,…,n:
# current truck number
# list of packages in current truck # total weight of current truck
# current partial solution
if t+wi W: #packageifitsincurrenttruck;putitin Tk.append(wi)
t += wi
else: # package i does not fit in current truck; start next one
k += 1
Tk = [wi]
t = wi S.append(Tk )
return S # = [T1,T2,…,Tk]
Following the structure given in class, give a detailed proof that the current algorithm is guaranteed to always use the minimum number of trucks. In particular, give a clear, precise definition of what it means for a partial solution to be “promising” for this problem. (Your solution will be marked on its structure as well as its content.)
[There’s more space on the next page. . .] Page 3 of 10 Student #: over. . .
Use this page for rough work — clearly indicate any section(s) to be marked.
Page 4 of 10 cont’d. . .
Fall 2008 Term Test # 1 CSC 373 H1 Question 1. (continued)
[Use this page for the rest of your solution.]
Page 5 of 10 Student #: over. . .
Use this page for rough work — clearly indicate any section(s) to be marked.
Page 6 of 10 cont’d. . .
Fall 2008 Term Test # 1 CSC 373 H1
Question 2. [19 marks]
An “ordered graph” G = (V, E) is a directed graph whose nodes can be ordered v1, v2, . . . , vn such that:
(i) every edge goes from a lower indexed node to a higher indexed node, i.e., i < j for all (vi,vj) ∈ E; (ii) all nodes except vn have at least one outgoing edge.
Given an ordered graph G = (V,E), we want to find a longest path from v1 to vn, i.e., a path with the maximum number of edges. For example, in the graph below, (v1,v2), (v2,v4), (v4,v5) is a longest path of length 3.
x
v1 E v2 v3 E v4 E v5
T 0)
[5 marks]
Give a simple greedy algorithm that attempts to solve this problem, on input G = V = {v1, v2, . . . , vn}, E where the vertices have already been ordered to satisfy the conditions above. Then, show that your algorithm does not always return an optimal solution (give an explicit counter-example and desribe the solution returned by your algorithm, as well as why it is not optimal).
Part (a)
Page 7 of 10 Student #: over. . .
Use this page for rough work — clearly indicate any section(s) to be marked.
Page 8 of 10 cont’d. . .
Fall 2008 Term Test # 1 CSC 373 H1
Question 2. (continued) Part (b) [14 marks]
Following the structure given in class, give a dynamic programming algorithm for this problem; state the running time of your algorithm. (Your solution will be marked on its structure as well as its content.)
Page 9 of 10 Student #: over. . .
On this page, please write nothing except your name.
Last (Family) Name(s): First (Given) Name(s):
Page 10 of 10 Total Marks = 33 End of Term Test #1