CMPT307 21-1 Final Exam 1
15:30-18:30 April 25 (Sunday), open book, extra 20 minutes for submission. There
are 100 points in this exam. Submit your answers (must be typed, no point for hand
writing answers) in pdf file to CourSys http://coursys.sfu.ca/2021-cmpt-307-d1/.
You are required to have your answers received at CourSys by 18:50. Answers received
after 18:50 will get penalty of reducing points: 10 and 20 points deductions for answers
received at (18 : 50, 19 : 10] and (19 : 10, 19 : 30], respectively; no point will be given to
answers received after 19:30.
Students who receive 50% extra time accommodation from CAL (center for accessible
learning) are required to have your answers received at CourSys by 20:30; answers received
after 20:30 will get penalty of reducing points: 10 and 20 points deductions for answers
received at (20 : 30, 21 : 00] and (21 : 00, 21 : 30], respectively; no points will be given to
answers received after 21:30.
Students who receive 25% extra time accommodation from CAL are required to have
your answers received at CourSys by 19:40; answers received after 19:40 will get penalty
of reducing points: 10 and 20 points deductions for answers received at (19 : 40, 20 : 05] and
(20 : 05, 20 : 30], respectively; no points will be given to answers received after 20:30.
The work you submitted must be your own. Include your student number, your first
name and last (family) name, the course number and name, and examination date in the
top of your answers.
1. 15 points
Integers of a large number of bits are very important in many applications, for example,
integers of thousands bits are a base for information security. Given two integers x
and y of n-bits, it is known that each of the sum x + y, the difference x ? y, the
product xy when x = 2n or y = 2n can be computed in O(n) time. But it takes O(n2)
time to compute the product xy for arbitrary x and y of n-bits by multiplying x and y
directly. Much effort has been made to compute the product xy more efficiently. Given
two n-bits integers x = xn?1 · · ·x0 and y = yn?1 · · · y0 (assume n is even), let k = n/2,
xh = xn?1 · · ·xk, xl = xk?1 · · ·x0, yh = yn?1 · · · yk and yl = yk?1 · · · y0. Then the n-bits
integers x and y can be expressed as x = xh2n/2 + xl and y = yh2n/2 + yl. Below are
two recursive formulas (algorithms) to compute the product xy:
(a) xy = (xh2n/2 + xl)(yh2n/2 + yl) = xhyh2n + (xhyl + xlyh)2n/2 + xlyl.
(b) Pre-compute xhyh, xlyl and (xh + xl)(yh + yl), then
xy = xhyh2n + [(xh + xl)(yh + yl)? xhyh ? xlyl]2n/2 + xlyl.
Apply Master Theorem for the recursive analysis to show the running times of the two
algorithms above in term of n (5 points for each running time). In the analysis for the
running times, assume that n = 2j for integer j > 0, and it takes O(1) time for every
arithmetic operation between two integers when n = 1. Which algorithm has a samller
asymptotic running time (5 points)?
2. 15 points
CMPT307 21-1 Final Exam 2
Below is a randomized algorithm for searching an unsorted array problem: Given an
array A of n elements which are not sorted and a value x, find an index i such that
A[i] = x. Algorithm Random-Search works as follows: select a number i from {1, .., n}
independently and uniformly; if A[i] = x then return i and terminate; otherwise repeat
the above process until the i with A[i] = x is found or A[i] 6= x for every i = 1, .., n is
concluded.
Random-Search
Initialize array P of size n containing all zeros;
c = 0;
while c < n do
i = RI(A);
if A[i] = x then return i;
if P [i] = 0 then {P [i] = 1; c = c + 1};
return A does not contain x.
Assume that there are 1 ≤ q < n elements of array A containing x. Analyze the
expected number of checks of A[i] = x Random-Search performs before terminates and
give the expected number in terms of n and q.
3. 15 points
There are n clients waiting for the service of an agent. The agent starts the service
at time 0 and serves the clients one by one. When the agent starts serving a client
i the agent continuously serves client i until the service is completed and the agent
takes time pi > 0 to serve client i. Let ci be the time when the agent completes
the service for client i. The waiting time of client i is ci. The average waiting time
for all clients is (1/n)
∑n
i=1 ci. For example, given two clients 1 and 2 with p1 = 3
and p2 = 5, if the agent serves client 1 first and then client 2 then c1 = p1 = 3,
c2 = p1 + p2 = 3 + 5 = 8 and the average waiting time is (3 + 8)/2 = 5.5; if the agent
serves client 2 first and then client 1 then c2 = p2 = 5, c1 = p2 + p1 = 5 + 3 = 8 and
the average waiting time is (5 + 8)/2 = 6.5. Design a greedy algorithm in pseudo code
which, given p1, .., pn, computes an order to serve the n clients such that the average
waiting time is minimized (5 points); prove the correctness (5 points) and analyze the
running time of your algorithm, assuming p1, .., pn are real numbers (5 points).
4. 15 points
Assume you are running two equipments rental offices by yourself, one in Vancouver
and the other in Toronto. Each month, you can run your business in only one city,
either in Vancouver office or in Toronto office. In month i (1 ≤ i ≤ n), you will incur an
operating cost vi if you run the business in Vancouver and incur an operating cost ti if
you run the business in Toronto. However, if you run the business in one city in month
i, and in the other city in month i+ 1, then you incur a fixed moving cost M to move
from one city to the other city. Given a sequence of n months, a plan is a sequence of
n locations c1, .., cn, each ci is either Vancouver or Toronto indicating where you will
run your business in the ith month. A plan can begin in either cities. The cost of a
CMPT307 21-1 Final Exam 3
plan is the sum of the operating costs for each of the n months, plus a moving cost
M for each time you move from one city to the other. Given M , v1, .., vn and t1, .., tn,
an optimal plan is a plan with the minimum cost. An example: n = 4, M = 10
and the operating costs are given in Table 1. An optimal plan is c1 =Vancouver,
c2 =Vancouver, c3 =Toronto, c4 =Toronto with the cost 1 + 3 + 10 + 2 + 4 = 20.
Month 1 Month 2 Month 3 Month 4
v1 = 1 v2 = 3 v3 = 20 v4 = 30
t1 = 50 t2 = 20 t3 = 2 t4 = 4
Table 1: Operating costs for four months.
Design a dynamic programming algorithm (structure of optimal solution (5 points),
Bellman equation (5 points), pseudo code and analysis of running time (5 points)) to
find the cost of an optimal plan.
5. 20 points
For any pair of nodes u and v in an edge-weighted digraph G of n nodes and m arcs
with no negative cycles, let Puv = {u v} be the set of shortest paths from u to v and
p?uv be the path in Puv with the minimum number of arcs. Let r(p
?
uv) be the number
of arcs in p?uv and r = maxu,v∈V (G)r(p
?
uv). Give a modified Bellman-Ford algorithm
in pseudo code that the modeified algorithm computes the shortest distance from s
to every v and terminates once every path of at most r + 1 arcs from s to every v is
checked, even if r is not known in advance (10 points). Prove the correctness of the
modified algorithm (5 points). Analyze the running time of the modified algorithm (5
points).
6. 20 points
An improved Dijkstra’s algorithm for computing a shortest path from a source node s
to a destination node t works as follows: Let S be the set of nodes to which the shortest
paths from s have been computed and T be the set of nodes from which the shortest
paths to t have been computed. Initially, S = ? and T = ?; in each iteration, the
improved algorithm adds a node u ∈ V (G) \ S to S as in Dijkstra’s algorithm (slides
68,69 of lec6) and adds a node x ∈ V (G) \ T to T as in Dijkstra’s algorithm taking t
as the source, until S ∩ T 6= ?. Let w be the node in S ∩ T . The improved algorithm
takes a shortest path from s to w and a shortest path from w to t as a shortest path
from s to t. Write the improved Dijkstra’s algorithm in pseudo code which, given an
undirected graph G of n nodes and m edges with non-negative edge weights, a source
node s and a destination node t, computes the shortest distance between s and t (10
points). Prove the correctness of the improved Dijktra’s algorithm (your pseudo code)
(5 points) and analyze its running time (5 points).