xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

算法代写-CMPT307 21-Assignment 4

时间：2021-03-11

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.

学霸联盟

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.

学霸联盟