Fall 2008
Term Test # 2 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 3 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: /10 # 2: /16 # 3: / 7
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 # 2 CSC 373 H1 Question 1. [10 marks]
Consider the following task: given a list that contains stock prices over the last several days, determine if there are any three consecutive days during which the stock price increased. Write a divide-and-conquer algorithm that carries out this task; more specifically, give an algorithm A(L,b,e) that returns an index i such that b+1 i e−1 and L[i−1] < L[i] < L[i+1], if such an index exists—your algorithm should return the value −1 if there is no such index. Include descriptive comments, or a concise English description of the main ideas, and analyze the running time of your algorithm. (For your reference, the Master Theorem states that a recurrence of the form T(n) = aT(n/b)+Θ(nd) has solution Θ(nd) if a < bd, Θ(nd log n) if a = bd, and Θ(nlogb a) if a > bd.)
Note: For full marks, your answer must make use of the divide-and-conquer method (even though there is a simple iterative solution), and your algorithm must run in no more than linear time.
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 # 2 CSC 373 H1 Question 2. [16 marks]
A vertex cover in an undirected graph G = (V, E) is any subset of vertices C ⊆ V such that every edge in GhasatleastoneendpointinC(i.e.,∀(u,v)∈E,u∈Corv∈C,orboth). Intheminimumvertex cover problem, the input is a graph with a positive integer weight w(v) for each vertex v ∈ V , and we want to find a vertex cover C with the smallest possible total weight w(C) = v∈C w(v). In this question, we are interested in constructing minimum weight vertex covers for trees, using dynamic programming.
Part (a) [3 marks]
Given a tree T = (V, E), state precisely the information contained in your dynamic programming table(s)—
in particular, specify the exact sub-problem whose solution is stored in each entry of your table(s).
Part (b) [6 marks]
Give a recurrence that could be used to compute the entries in your table. Justify that your recurrence is
correct.
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 # 2 CSC 373 H1
Question 2. (continued) Part (c) [7 marks]
Give an algorithm that will determine the vertices in a minimum vertex cover, given the entries in your table. Briefly justify that your algorithm is correct, and analyze its runtime.
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 # 2 CSC 373 H1 Question 3. [7 marks]
Use the Ford-Fulkerson algorithm to compute a maximum flow in the network below (where each edge has the indicated capacity). State precisely each augmenting path that you use—you must use the path given below the picture as your first augmenting path. Justify that your flow is maximum—for full marks, your justification should not be based on the non-existence of a larger flow or of an augmenting path.
a
3
s 8 b 10 c 8 t
3
33
d
0/8 0/10 0/8 Augmenting path P = s −→ b −→ c −→ t
Residual capacity ∆f (P ) = (fill this in)
Page 9 of 10 Student #:
over. . .
10
10
5
5
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 #2