CMPT 307 Assignment 1 to 4 solutions

Description

CMPT 307 Assignment 1

1. Express ∑ (3𝑖
3 − 6𝑖 + 2)
𝑛
𝑖=0
as a polynomial p(n). Then prove that the sum = p(n) by
induction.
2. Aerosort is a sorting algorithm.
Aerosort(A, i, j) // A is array to sort; i and j are start and end
indices.
n = j – i + 1
If (n < 10) {
sort A[i…j] by insertion-sort
return
}
m1 = i + 3 * n / 4
m2 = i + n / 4
Aerosort(A, i, m1)
Aerosort(A, m2, j)
Aerosort(A, i, m1)
a. What is the asymptotic worst-case running time of Aerosort? Show your work.
b. Prove that Aerosort(A, 1, n) correctly sorts an array A of n elements.
3. Devise a comparison-based algorithm (no bucket or radix sort, for instance) to
simultaneously find the minimum and the maximum element in a list of n numbers
using at most 3n/2 comparisons. Give pseudocode.
4. Give an efficient algorithm to convert a given -bit (binary) integer to a decimal
representation. Argue that if multiplication or division of integers whose length is at
most  takes time M(), then binary-to-decimal conversion can be performed in time
Θ(M() log ). (Hint: use a divide-and-conquer approach, obtaining the top and bottom
halves of the result with separate recursions.)

CMPT307 Assignment 2

1. Improve the Longest Common Subsequence (LCS) algorithm (10 points):
(a) Show how to compute the length of an LCS using only 2 min(m, n)
entries in the c table plus O(1) additional space. Express in pseudocode. Then analyze the memory space usage of your algorithm.
(b) Then show how to do the same thing, but using min(m, n) entries plus
O(1) additional space. Again, express in pseudocode, and analyze the
memory space usage of your algorithm.
2. Refer to the power of 2 problem (Lecture 12, slides p21) (10 points).
(a) Redo the problem using the accounting method.
(b) Redo the problem using the potential method.
3. Coin changing (20 points):
Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin’s value is an integer.
(a) Describe a greedy algorithm to make change consisting of quarters,
dimes, nickels, and pennies. Prove that your algorithm yields an
optimal solution.
(b) Suppose that the available coins are in the denominations that are
powers of c, i.e., the denominations are c
0
, c1
, . . . , ck
for some integers
c > 1 and k ≥ 1. Show that the greedy algorithm always yields an
optimal solution.
(c) Give a set of coin denominations for which the greedy algorithm does
not yield an optimal solution. Your set should include a penny so
that there is a solution for every value of n.
(d) Give an O(nk)-time algorithm that makes change for any set of k
different coin denominations, assuming that one of the coins is a
penny.
1

CMPT307 Assignment 3

1. Describe an algorithm to compute the reversal (also called transpose)
rev(G) of a directed graph in O(V + E) time. (10 points)
2. Given a directed graph G. Let v denote a vetex of G, and S(v) be the
strong component of G that contains v. For two arbitrary vertices u, v ∈
G, prove that u can reach v if and only if S(u) can reach S(v) in scc(G).
(10 points)
3. Given an undirected graph G with weighted edges and a minimum spanning tree T of G, describe an algorithm (use pseudocode) to update the
minimum spanning tree T when the weight of a single edge e is increased.
The input to your algorithm is the edge e and its new weight value. You
shold modify the spanning tree T so that it is still a minimum spanning
tree. (10 points)
Hint: Consider the cases e ∈ T and e 6∈ T separately.
4. Given a directed graph G with weighted edges, describe an algorithm to
find the shortest path from one vertex s to another vertex t. There is
exactly one edge in G that is with negative weight. (10 points)
Hint: Consider modifying Dijkstra’s algorithm. Of course other ideas
could also be great.
1

CMPT307 Assignment 4

1. Let G = (V, E) be a directed graph with weighted edges, edge weights
can be positive, negative, or zero. Suppose vertices of G are partitioned
into k disjoint subsets V1, V2, . . . , Vk; that is, every vertex of G belongs to
exactly one subset Vi
. For each i and j, let δ(i, j) denote the minimum
shortest-path distance between vertices in Vi and vertices in Vj , that is
δ(i, j) = min{dist(u, v) | u ∈ Vi and v ∈ Vj}
Describe an algorithm to compute δ(i, j) for all i and j. For full credit,
your algorithm should run in O(V E + kV log V ) time. (10 points)
2. Let G = V, E be a flow network in which every edge has capacity 1 and
the shortest-path distance from s to t is at least d. (10 points)
(a) Prove that the value of the maximum (s, t)-flows is at most E/d.
(b) Now suppose that G is simple, meaning that for all vertices u and v,
there is at most one edge from u to v. Prove that the value of the
maximum (s, t)-flow is at most O(V
2/d2
).
3. A cycle cover of a given directed graph G = (V, E) is a set of vertexdisjoint cycles that cover every vertex in G. Describe and analyze an
efficient algorithm to find a cycle cover for a given graph, or correctly
report that no cycle cover exists. (10 points)
Hint: use bipartite matching. But G is not bipartite, so you’ll have to use
a graph derived from G.
4. Solve the equation by using an LUP decomposition. (For full credit, show
your detail steps. ) (10 points)


1 −2 1
0 2 −8
−4 5 9




x1
x2
x3

 =


0
8
−9


1