Reference no: EM132001056

Assignment 1

For a given n, a sum tree for n is a full binary tree whose root is labeled whose leaves are labeled 1, and in which the children of a node labeled j have labels that sum to j. Every node should have a label > 0.

Given a cost table c[i], the cost of a node labeled i is c[i], and the cost of the tree is the sum of the cost of its nodes.
a. What is the cost of a sum tree for 1? (in terms of c[1])
b. What is the cost of a sum tree for 2? (in terms of c[1] and c[2]421)
c. An optimal sum tree for i is a sum tree for i of minimum cost. What is an optimal sum tree for 8 if c[1] to c[7] are 1,3,11,20,20,21,26,27?
d. Write down a formula that expresses the cost of an optimal sum tree in terms of the cost of smaller optimal sum trees. (Hint: In an optimal sum tree, the trees rooted at the left and right children of the root form optimal sum trees.)
e. Use the dynamic programming technique to design an algorithm that finds the cost of the optimal sum tree for n, given it and c[i), for 1 ≤ i ≤ n.
f. Analyse the time that your algorithm takes (asymptotic notation).

Problem 1

We want to find an optimal binary search tree for keys that have the following probabilities: (.3, .2, .1, .05, .35). We have started our dynamic programming solution and have partially filled the following e, w and root arrays as shown below. Compute the final solution and draw the optimal binary search tree. Explain your calculations.

	0	1	2	3	4	5
1		0.3	0.5	1	1.15
2			0.2	0.4	0.55	1.35
3				0.1	0.2	0.95
4					0.05	0.45
5						0.35
6

 

0	1	2	3	4	5
1	0.3	0.5	0.6	0.65	1
2		0.2	0.3	0.35	0.7
3			0.1	0.15	0.5
4				0.05	0.4
5					0.35
6

 

	1	2	3	4	5
1	1	1	1	2
2		2	2	2	2
3			3	3	3
4				4	5
5					5

Assignment 2

1. For each of the following non-standard (inefficient) minimum finding algorithms, give the asymptotic best and worst case time analysis. Assume the array has no duplicates. In the algorithms, i and j are the first and last index of the array to be considered. The problem is to find the smallest value among A[i]...A[j]. (The algorithms are intended to be correct. If there is an unintentional error, attempt to fix it before answering.)

(a) Algorithm 1 integer minimum1(A: array of integer; i, j: integer):

begin
if j - i ≤ 5 sort and return A[i];
m1 = minimum1(A, i, i + |(j - i)/5∫;
m2 = minimum1(A, i + |(j - i)/5∫ + 1, j); return the minimum of m1 and m2;
end;

(b) Algorithm 2
integer minimum2(A: array of integer; i, j: integer): begin
if j - i ≤ 5 sort and return A[i];
separate elements of A from i to j in |(j - i)/5| groups of 5 (with one group that may have less than 5);
sort each group of 5 using insertion sort;
form an array with the minimum of each group;
make a recursive call on the new array and return the result; end

(c) Algorithm 3
integer minimum3(A: array of integer; i, j: integer): begin
if j - i ≤ 5 sort and return A[i]; m1 = minimum3(A, i and j - 1); m2 = minimum3(A, i + 1, j);
return the minimum of m1 and m2; end;

2. For an edge (u, v), in a depth first search, indicate if d[u] < d[v] and if f [u] < f [v]. In each box, write True, False or Depends. Writing "Depends" means that it is true in some cases and false in other cases.

	d[u] < d[v]	f [u] < f [v]
tree edge
forward edge
back edge
cross edge

3. We define the depth cost of a heap as Σ_i(d_i ∗ k_i), where ki is the key and di is the depth of the node in the heap. Given a set of key values in arbitrary order, we are interested in constructing a min heap with minimum depth cost.

(a) Give two heaps of size 6, one with minimum depth cost and one which is not optimal. Compute the depth cost of each.

(b) Give a proof (or a convincing argument) that if for every level of a heap, the minimum key value is ≥ the value of every key value in the level above it, then the heap has minimum depth cost.

(c) One way to produce a minimum depth cost heap is to sort the keys. Develop an algorithm that is more efficient than sorting. Hint: Find out how many elements are at the bottom level of the heap, use the linear time selection algorithm to find the set of keys at the bottom level, and recursively apply the algorithm on the rest of the keys.

(d) Analyse the time of your algorithm.

4. You have to develop an algorithm to compute how to give change with the minimum number of coins. The input is a sorted array of coin values c = {c₀, c₁, c₂, ..., c_n} with c₀ = 1 and a target value v. There is an unlimited number of each coin available. The output is an array
{v₀, v₁, v₂, ..., v_n} such that ∑_i c_i ∗ v_i = v, and such that ∑_i v_i is minimum. For example, with US coins c = {1, 5, 10, 25} and v = 61, the solution is {1, 0, 1, 2}.

(a) Although the greedy approach to this problem does not work in general, develop a greedy algorithm to solve this problem. Analyse the time complexity of your algorithm.

(b) Show an example where your greedy approach does not give the optimal solution. (With the most obvious greedy algorithm, the set c = {1, 4, 5} does not give optimal solutions.)

(c) This bonus part has an elaborate solution and only worth 4 point, solve only if you have finished the rest of the exam.)
Develop a dynamic programming algorithm to solve this problem.

5. Closed notes, closed book question

Select the best answer to each question.
(a) expected running time
A. when we consider the average time to perform a sequence of operations (like a sequence of inserts and deletes)
B. when we consider the probability distribution of possible inputs
C. when we consider the probability distribution of random values generated by a randomized algorithm
D. when we consider the time on the most likely input

(b) binary search tree
A. supports search, insert, delete, minimum in O(lg n) average case
B. supports search, insert, delete, minimum in O(lg n) worst case
C. when the root key is less or equal to the root key of each subtree
D. when node keys are expressed in binary

(c) dynamic programming
A. a technique that allows the algorithm to modify itself
B. combines solutions of subproblems, and keeps solutions of subproblems in a table
C. separates a problem recursively into subproblems of equal size
D. when the algorithm requires dynamic allocation of memory

(d) prefix code
A. a code where all codewords must have the same length
B. a code where all codewords start by the same prefix string of at least one char- acter
C. a code where no codeword is also a prefix of some other codeword
D. a code where some of the codewords have different lengths

(e) greedy algorithm
A. an algorithm that always makes the choice that looks best at the moment
B. an algorithm that computes the best profit at the possible expense of running time
C. an algorithm that uses more space for the purpose of a better running time
D. an algorithm that makes use of all the available processors

(f) strongly connected component
A. any maximal set of vertices such that for each pair u and v, there is an edge from u to v and from v to u
B. any maximal set of vertices such that for each pair u and v, there is a path from
u to v and from v to u
C. any maximal set of vertices such that for each pair u and v, there is an edge from u to v or from v to u
D. any maximal set of vertices such that for each pair u and v, there is a path from
u to v or from v to u

(g) minimum spanning tree
A. a subset of the edges that connects all vertices with minimum cost
B. a subset of the edges that connects a given pair of vertices with minimum cost
C. a subset of the edges of minimum size that connects all vertices
D. a subset of the edges of minimum size that connects a given pair of vertices

(h) Dijkstra's algorithm
A. an algorithm to compute the shortest path for every pair of vertices that works on graphs with positive edge weights
B. an algorithm to compute the shortest path from a vertex to every other vertices on graphs with positive edge weights
C. an algorithm to compute the shortest path for every pair of vertices that works on graphs where negative edge weights are allowed
D. an algorithm to compute the shortest path from a vertex to every other vertices on graphs where negative edge weights are allowed

(i) span of a multithreaded algorithm
A. a multithreaded algorithm that finds a subset of edges that connects the network of processors
B. the longest time to execute the algorithm when we have an unlimited number of processors
C. the maximum number of processors used by a multithreaded algorithm
D. the time to execute the algorithm on a single processor

(j) What is the span of multithreaded merge (merging two sorted lists of length n) and the span of multithreaded merge sort, as covered in the textbook and in class?
A. Θ(log n) for multithreaded merge and Θ(log² n) for merge sort.
B. Θ(log² n) for multithreaded merge and Θ(log³ n) for merge sort.
C. Θ(log n) for multithreaded merge and Θ(n) for merge sort.
D. Θ(n) for multithreaded merge and Θ(n log n) for merge sort.