Design and Analysis of Algorithms

Questions: Search:

1. Suppose you are given a set P of integers and another integer x. We wish to use a Θ(n²) algorithm to decide whether there are 3 integers in P and the sum of these three integers equals to x. Show your algorithm and indicate why its complexity is Θ(n²). (You can use pseudo code or by illustration only)

Recurrence:

2. Using a recursion tree, show the process how to solve the following recurrence in terms of the big O representation. Use the substitution method to verify your result.

T(n) = 4T(n/4)+cn

Sorting:

3. Can RADIX SORT shown in our textbook work correctly if we use QUICKSORT instead of COUNTING SORT to sort each individual digit? Justify your answer.

Data structures:

4. If we perform an inorder traversal on a Min Heap (as defined in the textbook), will we get the values in sorted order? Why or why not? Use a simple example to justify your answer.

Greedy algorithms and dynamic programming:

5. You have n programs p1, ..., pn with size m1, ..., mn MB (mega bytes). You have a disk that can store up to W MB. W is less than the total size of the programs. You are asked to use a dynamic programming solution to store the programs onto the disk so as to maximize the disk space utilization. In other words, you want to find a subset of programs such that its total size is maximized but has to be less than C.

Define U[i,w] as the maximum disk utilization of a disk with capacity w MB and programs p1,...,pi to be selected for storing it on the disk. Write a recurrence for U[i,w] and identify the boundary condition.

6. Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.

1) Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.

2) Give a set of coin value combination (the value of coins may not be limited to quarter, dime, nickel, or penny) for which the greedy algorithm does not yield an optimal solution. Your set should include a penny value so that there is a solution for every possible value of n. Use an example to justify your answer.

Tree and graph:

7. Given the following weighted undirected graph, show the order the edges would be added for building a spanning tree using Kruskal's and Prim's algorithm. Take the following figure as an example, order edges added using two algorithms. In addition, how many edges will be picked up to build the tree? Why? Show your process.

8. For each of the following, either draw a graph satisfying the given criteria or explain why it cannot be done. Your graphs should be simple, i.e. not having any multiple edges (more than one edge between the same pair of vertices) or self- loops (edges with both ends at the same vertex).

b. A graph with 3 connected components, 11 vertices, and 8 edges.
c. A graph with 3 connected components, 10 vertices, and 30 edges.
d. A graph with 3 connected components and 10 vertices. 9 vertices have degree 3 and 1 vertex has degree 4.
e. A graph with 6 vertices, of which 4 have degree 3, 1 has degree of 4 and 1 has degree 5.