CMPT307 21-1 Assignment 4 1
Due 16:00 March 15 (Monday). There are 100 points in this assignment.
Submit your answers (must be typed, no point for hand writing answers) in pdf file
to CourSys https://coursys.sfu.ca/2021sp-cmpt-307-d1/.
The work you submitted must be your own. Any collaboration and consulting outside
resources must be explicitly mentioned on your submission.
1. 15 points
A digraph G with nodes v1, .., vn is an an ordered graph if it has the following properties:
(i) Every directed edge has the form (vi, vj) with i < j and (ii) for every node vi,
i = 1, 2, .., n − 1, there is at least one edge of the form (vi, vj). The length of a path
in G is the number of edges in it. Given an ordered digraph G, the goal is to find
the length of the longest path that begins at v1 and ends at vn. Give a dynamic
programming algorithm (structure of optimal solution, Bellman equation and pseudo
code) which, given an ordered graph, finds the length of the longest path that begins
at v1 and ends at vn in O(n
2) time. Your algorithm need only compute the maximum
length of the path.
2. 20 points
There are two machines A and B and a job J . In each time interval ti of t1, .., tn, J can
be executed on A by ai > 0 steps or on B by bi > 0 steps or moved between machines
(from A to B or from B to A, J is executed 0 step). Design an O(n) time dynamic
programming algorithm (structure of optimal solution, Bellman equation, pseudo code)
which, given a1, .., an and b1, .., bn, computes a plan that decides run J on A or on B
or move between machines for every interval such that J is executed by a maximum
number of steps. At t1, J can be executed on either A or B. Your algorithm should
compute both the maximum number of steps and the plan to achieve the maximum
number of steps.
3. 10 points (Ex 15.5-2 of text book)
Give the cost and structure of an optimal binary search tree for an input instance
shown below:
i 0 1 2 3 4 5 6 7
pi 0 0.04 0.06 0.08 0.02 0.10 0.12 0.14
qi 0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05
4. 15 points (Ex 16.1-4 of text book)
Given a set S = {a1, .., an} of proposed activities (e.g., classes) that wish to use a
resource (e.g., classroom) which can serve one activity at a time. Each ai has a start
time si and a finish time fi with 0 ≤ si < fi < ∞, and takes place in time interval
[si, fi). Activities ai and aj are compatible if [si, fi) ∩ [sj, fj) = ∅. The scheduling all
CMPT307 21-1 Assignment 4 2
intervals problem is to find a minimum number of resources to serve all activities, each
resource serves a subset of mutually compatible activities from S. Give an efficient
greedy algorithm in pseudo code to solve the scheduling all intervals problem. Prove
the algorithm finds an optimal solution and analyze the running time of the algorithm.
5. 15 points (Ex 16.2-6 of text book)
Give an algorithm in pseudo code which solves the fractional knapsack problem in O(n)
time. Prove the correctness and analyze the running time of your algorithm.
6. 15 points (Ex 17-1.3, 17-2.2, 17-3.2 of text book)
Suppose we perform a sequence of n operations on a data structure in which the ith
operation costs i if i is an exact power of 2, and 1 otherwise. (a) Use aggregate
analysis to determine the amortized cost per operation. (b) Use an accounting method
of analysis to determine the amortized cost per operation. (c) Use a potential method
of analysis to determine the amortized cost per operation.
7. 10 points (Ex 17.3-7 of text book)
Design a data structure to support the following two operations for a dynamic multiset
S of integers, which allows duplicate values:
INSERT(S, x) inserts x into S.
DELETE-LARGER-HALF(S) deletes the largest d|S|/2e elements from S.
Explain in plain language how to implement this data structure so that any sequence
of m INSERT and DELETE-LARGER-HALF operations runs in O(m) time. Your
implementation should also include a way to output the elements of S in O(|S|) time.




























































学霸联盟