[Solving recurrence relations] Exercise 4.3-1 (a, b, and c) on p. 75 of
the text.
[Writing a divide-and-conquer algorithm] Consider the problem of
determining how many times a particular element occurs in an array.
Write a divide-and-conquer algorithm to solve this problem. How many
comparisons must your algorithm perform on an array of length n?
[Writing a memoized algorithm] Consider the problem of computing the
"choose" function (also called the binomial coefficient
function). Its definition is:
C(n, 0) = 1
for n ≥ 0
C(0, k) = 0
for k > 0
C(n, k) = C(n-1, k-1) +
C(n-1, k)
for n > 0 and
k
> 0
Write a memoized algorithm to compute C(n, k).
[Writing a greedy algorithm] Consider the problem of making change for n
cents using the fewest number of coins, where the coins available are
quarters, dimes, nickels, and pennies.
a. How would a brute-force algorithm work? How many different coin
combinations are there for 21¢ and which one yields the fewest number of
coins?
b. Write down (in pseudocode) a greedy algorithm for making change with the
fewest coins.
Run your algorithm on the amounts 21¢, 54¢, and $5.33, listing the minimal
number of coins needed for each.
c. Argue informally that your algorithm always yields the fewest number of
coins.
d. (Extra credit) Determine a list of coin denominations (which must include
a penny) for which your algorithm will not give the fewest
number of coins.
[Executing greedy graph-optimization algorithms] The following table represents an adjacency matrix for a graph on nine
vertices, where the vertices are labeled with the letters 'a' through 'i'.
A non-zero value w at a position in the matrix indicates that the
vertices labeling the row and column of that position have an edge between
them with weight w. A zero value indicates that there is no
edge. For example, the value 7 at position (a,f)
indicates that there is an edge of weight 7 between vertices a and f.
The value 0 at position (a,e) indicates that there is no edge
between vertices a and e. This is an undirected graph so
the value at position (x,y) is the same as at (y,x).
a. Run Prim's minimal-cost spanning tree algorithm on the graph represented
by the matrix. Your answer should specify the minimal cost and the tree that
Prim's algorithm produces.
b. Run Dijkstra's single-source shortest-path algorithm on the graph
represented by the matrix using vertex a as the source. Your
answer should specify the lengths of the shortest paths from a to
every other vertex and the tree the algorithm produces.
Vertex
Vertex
a
b
c
d
e
f
g
h
i
a
0
2
0
0
0
7
3
0
0
b
2
0
4
0
0
0
6
0
0
c
0
4
0
2
0
0
0
2
0
d
0
0
2
0
1
0
0
8
0
e
0
0
0
1
0
6
0
0
2
f
7
0
0
0
6
0
0
0
5
g
3
6
0
0
0
0
0
3
1
h
0
0
2
8
0
0
3
0
4
i
0
0
0
0
2
5
1
4
0
[Matrix chain order] Consider the matrix chain multiplication order
problem again. Assume that you have a chain of eight matrices whose
dimensions are: 10´2, 2´10,
10´2, 2´10, 10´4,
4´10, 10´4, and 4´10.
a. Using the program you wrote for assignment 4, compute the optimal
number of scalar multiplications needed to form the product of these
matrices. Also, give the optimal parenthesization.
b. Consider a divide-and-conquer approach that divides the chain in half
and:
recursively computes the number of scalar multiplications needed to form a single
matrix L from the matrices in the left half of the chain;
recursively computes the number needed to form a single matrix R from the matrices in
the right half of the chain;
computes the number of multiplications needed to form the product LR;
adds these values together to determine the total number of multiplications needed.
How many multiplications does this algorithm compute will be needed with the above
chain?
c. Consider a greedy approach that scans the chain looking for the pair of
matrices requiring the fewest multiplications to form a product. Then,
assuming that product has been formed, it looks at the resulting chain for
the next pair requiring the fewest multiplications. It continues to do
this until there is only one matrix.
How many multiplications does this algorithm compute will be needed with the above
chain?
[NP-completeness] Using any source except for the textbook, find two
NP-complete problems that have arisen in practice. The web might be a
good place to look. For each problem, write a short description and
provide a reference to where you found the information.
