Spring 2003 CSE331 Midterm 2 (75 minutes)
Sections 1,2,3 Chung
Name ________________________________________ID______________________
PART I. (15 points.) Multiple choice. No explanation necessary.

Suppose we consider a variation of Mergesort in which we divide the list to be sorted into four sublists of equal size, recursively sort each sublist, and then merge the four lists to obtain the final sorted list. What recurrence would be the number of comparisons used by this algorithm in the worst case?
A. T(n) = 2 T(n/2) + n  1. B. T(n) = 4 T(n/2) + n  1.
C. T(n) = 2 T(n/4) + n  1. D. T(n) = 4T(n/4) + n  1.
E. T(n) = 4T(n/4) + n^{2}.

In class we mentioned that Mergesort and Quicksort could be viewed as applications of a technique called DivideandConquer. In this technique we solve a problem by

dividing it into subproblems,

recursively solving the subproblems, and then

combining the solutions of the subproblems to get a solution to the original problem.
(i) Outside of the time spent in recursive calls, where did Quicksort do its comparisons of keys?

In stage (a).

In stage (c).

About half in stage (a), and the other half in stage (c).

Neither stage (a) nor stage (c) required any comparisons of keys.
(ii) Outside of the time spent in recursive calls, where did Mergesort do its comparisons of keys?

In stage (a).

In stage (c).

About half in stage (a), and the other half in stage (c).

Neither stage (a) nor stage (c) required any comparisons of keys.
3. Consider the following program. What is the time complexity of the following program?
Long power(int x, int n)
{
if ( n == 1 ) return x;
else {
if ( n % 2 == 0 ) return power(x,n/2)*power(x,n/2) ;
else return power(x,n/2)*power(x,n/2) *x
}
}
A. O(n) B. O(nlogn) C. O(logn) D. O(n^{2}) D. O(2^{n})
PART II. (25 points) True or false? If true, explain it briefly. If not, provide a counter example.

Given a connected undirected graph G, if the weights of all edges are distinct, there is at most one minimum spanning tree.

Given a connected undirected graph G, if the weights of all edges are distinct, there is exactly one shortest path from one node to another node.

Dijkstra’s algorithm works even when there is a negative edge.

Prim’s algorithm works even when there is a negative edge.

In hashing of table size 10,000, if there is no deletion of keys and the number of elements are close to 5000, chaining is much better than open addressing (closed hashing).

In hashing, as the load factor approaches to 1, the performance of the chaining is better than the closed hashing.

For a hash table of size 111, let h1 and h2 be as follows:
h1(x) = 4x+1 mod 105
h2(x) = 7x+1 mod 105
In this case, h1 is better hashing function than h2.
PART III. (30 points)
1. Find the minimum spanning tree using Prim’s algorithms.

State the most important one advantage and one disadvantage of quadratic rehashing.
3. Below is a set of characters and their relative frequencies of occurrence. Build an optimum Huffman code for this set of characters.
Character: a b c d e f
Frequency: 5 2 6 2 8 4
4. Let z1, z2 be two complex numbers. That is, z_{1}= x_{1} + iy_{1}, and z_{2} = x_{2} + iy_{2}, where x_{1},x_{2},y_{1},y_{2 }are integers, and i = 1 .
Show that z1*z2 can be computed three integer multiplications.
0
1
2
3
4
5
6
7
8
9
5
. Let the hash table size be 10 and
h(x) = 3x + 1 mod 10
C
onsider the following sequence of operations
I
nsert 13
Insert 20
Insert 10
Insert 23
Delete 20
Search 10
Show the contents of hash table for open addressing. Assume that you use linear probing for open addressing. For each operation, how many comparisons with the table entry does it require?
PART IV. (30 points)
Select any three problems and solve them.
Mark clearly which problems should be graded.
1. Find the shortest path spanning tree of the next graph.
(a) Demonstrate clearly how the cost (v) and from(v) are updated after each step.
Fill out the “?” places of step 2, and all places of
Step 26.
Step

Selected node
 A 
B

C

D

E

F

G

Cost

From

Cost

From

Cost

From

Cost

From

Cost

From

Cost

From

Cost

From

0

A



3

A





8

A

9

A









1

B

0


3

A

B

?

?

B

9

A









2
















3
















4
















5
















6
















(b) What is the shortest path from A to E.
(c) What is the shortest path from A to G.

Write a pseudo code of FindMed (A, n) which finds the median of an array A [1..n].
Note that A is not a sorted array. Your algorithm must be O(n) time in average.
You may use Partition(A, i, j), where Partition(A, i, j) returns m, and partitions the list A[i..j] into two parts A[i .. m] and A[m+1 .. j] such that every element of A[i..m] is smaller than or equal to the elements of A[m+1..j].
For example, if A[1..7] = {1,4,6,5,3,7,2}, one result of Partition (A,2,7) is,
it returns 3, with updated A={1,2, 3,5,6,7,4}
Note that the result of Partition(A, i, j) depends on how we implement it and the pivot element picked, but it is not the concern of us for the following problem. Assume that partition will take O(n) time for a list of n elements.
The number of lines should be smaller than 12 lines.
What is the average case complexity of the above program?
Let T(n) be the worst case time complexity of the above algorithm.
What is the recurrence equation describing the T(n)?
What is the worst case complexity of the Find?
3. Consider the following problem.
Job Scheduling with maximum profit
Instance: Jobs {J_{1},…,J_{n}}, with their profits {p_{1},…,p_{n}}, and deadline {d_{1},…,d_{n}}.
Objective: Schedule jobs to maximize the total profit. Each job has a unit execution time. Job scheduled within deadline gets its profit, but cannot get profit if it does not end within deadline.
Demonstrate how greedy algorithm works with the following example.
What is the complexity of your greedy? Justify your answer.
Example: Jobs with deadline and profits
Job J1 J2 J3 J4 J5 J6 J7
Profit 6 2 1 4 3 5 7
Deadline 4 2 5 2 3 1 4
4.The coinchanging problem In a Whacky country, there are k types of coins with their values x_{1}, x_{2}, ..., x_{k} cents.
Given y cents for the change, you would like to get the minimum number of changes.
Answer the following questions.
For the demonstration of your algorithm, work with the following example:
Coins: 1cent, 5 cents, 12 cents
Change: 19 cents
What is the greedy algorithm?
Does it give the optimal solution?
Demonstrate your algorithm.
Give a counter example of changes and coins where the greedy algorithm does.
Share with your friends: 