## Description

Quick Answer [each question worth 1pt]

For the next 3 problems, the phrase “union/find problem of size ” means that the

starting number of disjoint sets is

1. For the union/find problem of size , what is the worst-case complexity for any

single union operation when using weighted union but no path compression?

Note: the cost of initialization does not enter in to the calculation

2. For the union/find problem of size , what is the worst-case complexity for

any single union operation when using both weighted union and path

compression?

Note: the cost of initialization does not enter in to the calculation

3. For the union/find problem of size , what is the worst-case complexity for a

series of union/find operations when using weighted union and path

compression?

4. What is the worst-case complexity for selection sort n items?

5. What is the best-case complexity for selection sort of n items?

6. What is the worst-case complexity for insertion sort n items?

7. What is the best-case complexity for insertion sort of n items?

8. What is the worst-case complexity of quicksort of n items?

9. What is the average-case for quicksort of n items?

10. What is the worst-case for merge sort of n items?

11. You are comparing 2 algorithms A, and B. You have exact running times

, and

.

You are interested in a Big Oh comparison. Is , or is

or are these 2 complexities essentially the same in the Big

Oh sense?

N

N

N

N

N

O(N )

TA(n) = 22 log(n!) + 5n + 2205

TB(n) = 75n log(n) + 70000n + 200 log(n) + 100000

TA(n) = O(TB(n))

TB(n) = O(TA(n))

12. What is the worst-case complexity for quickselect to find the 1st quartile (the

n/4-smallest) item in a set of n items?

13. What is the average-case complexity for quickselect to find the 1st quartile (the

n/4-smallest) item in a set of n items?

14. Suppose you are looking for an item with key k in a set of n unsorted items.

What is the worst-case complexity to find the item (assuming it is in the set)?

15. In a 0-based heap array of size , where , what is the highest index of a

non-leaf element?

16. For Shellsort, let the -gap sequence be {1, 4, 9}.

Let the input sequence be

-27, 9, 0, -4, 12, 17, -100, -8, 42, 6404, 4

Show the sequence after the 9 gap is completed

17. Suppose you are looking for an item with key k in a set of n sorted items. What

is the worst-case complexity to determine the item is not in the set?

18. What is the worst-case complexity to delete the minimum element from a minheap of size n?

19. Given a number and a nonnegative integer , what is the worst-case

complexity to compute ?

20. You are comparing the worst-case complexities of 2 algorithms A and B.

The worst-case time for A is .

The worst-case time for B is

Is , or is , or both?

N N > 2

h

h =

f L

f L

TA(n) = 4000000n + 3504n log(n) + 100000

TB(n) = n2 + 2n + 4

O(TA) ≤ O(TB) O(TB) ≤ O(TA)

Not-so-Quick Answers

1. [ 5 pts ] Is the following code for fn an algorithm? Justify your answer.

def fn(x):

i,j = 0,2

while i< j:

x[i] = 0

i,j = i+1,j+1

2. [5 pts] Using any method you like, find the Big Oh of the function that solves

the recurrence

T(n) = 3T( n

2 ) + n2 + 5000n2 log2

(n) + 2n3 log3

(n)

3. [15 pts] For all parts of the next question, suppose there is a function that

computes the best 1st quintile of a set of numbers. That is, the function

returns the value of the -th smallest item in the set . In a 0-based

array, the function returns the element at index in the sorted array. As

an example, let

Then the sorted array is

So, the value is the value that appears at index (0-based

indexing) in the sorted array. That means that

3.1.[5 pts] Write the Restricted Python code for a modified quicksort algorithm

that takes an array as input, and then subsequently uses as the pivot

element. Your modified quicksort algorithm must use the COMP 582

quicksort partitioning algorithm that always pivots on the 1st element in an

array.

3.2.[5 pts] Suppose the complexity of is . Give the worst-case

complexity of your modified quicksort algorithm in problem 3.1. Show how

you derived the worst-case complexity (Big Oh is sufficient). In your

derivation, you may assume that the subproblems always divide into and

where .

3.3.[5 pts] Suppose the complexity of is . Give the worst-case

complexity of your modified quicksort algorithm in problem 3.1. Show how

you derived the worst-case complexity (Big Oh is sufficient). In your

derivation, you may assume that the subproblems always divide into and

where .

d(S)

S d

|S|

5 sorted(S)

d |S|

5 −1

S0 = {1, 3, − 5, − 2, 0, 1000, 4, 7, 10, 15, 11}

{−5, − 2, 0, 1, 3, 4, 7, 10, 11, 15, 1000}

d(S0) |S0 |

5 −1

d(S0) = − 2

S d(S)

d(S) O(1)

n

5

4n

5

n = |S |

d(S) O(log(n))

n

5

4n

5

n = |S |

4. [10 pts] Find the Big Oh solution to the recurrence

5. [10 pts] Suppose we want to maintain an array of the largest numbers of a

stream of numbers of length . By “maintain”, we mean that at any point in the

stream of numbers, the array contains the largest elements seen at that point

in the stream. Find an efficient algorithm to maintain this array. Also, give the

complexity of your algorithm, and show how you derived the complexity of

your algorithm.

NOTE: The array of the largest elements does not have to be ordered.

T(n) = T (

3n

4 ) + T (

n

4) + θ (n2

)

M

L

M

M

6. [20 pts] Suppose we have a k sets of various sizes. All k of the sets are sorted.

The total number of elements is N. You have available a bmerge routine that

performs a binary merge of 2 sets in exactly operations. The

total cost of the bmerge sequence is the sum of the costs of all of the

bmerge operations. To describe a bmerge sequence, name the result of a

bmerge a new name (/index). Example:

are initial sets. Then a bmerge sequence to merge all of these sets

could be:

6.1.[2 pts] Suppose there are 4 sets of sizes 3,3, 4, and 7.

Give a bmerge sequence that results in the largest number of total

operations to merge all sets

6.2.[2 pts] For the same 4 sets (sizes 3, 3, 4, and 7),

Give the bmerge sequence that results in the smallest number of total

operations to merge all sets.

[HINT: 8.1 and 8.2 have different answers!]

6.3.[16 pts]. For this problem, you want to create an efficient algorithm that

produces the smallest cost bmerge sequence. For example, when your

algorithm gets [7,3,4,3] as input, it returns the sequence you gave for

6.2.

Write your algorithm in Restricted Python code. Remember to give a new

index for intermediate merges. For example, if your first bmerge is of

original sets 0 and 2 (out of 3 original sets), then the index/name of your 1st

bmerge will be 3. Future bmerges can now refer to this intermediate stage

as set 3.The output of your algorithm is a list of bmerges For example,

given 3 original sets 0,1,2, your output could be:

3 = bmerge(0,2)

4 = bmerge(1,3)

In addition to your code, give the complexity of your algorithm.

S1, S2 |S1 | + |S2 |

S0, S1, S2

S3 = bmerge(S1, S2)

S4 = bmerge(S0, S3)

S0, S1, S2, S3

7. [15 pts] You are given a list of numbers as input. You must process in a

specific fashion:

1. Find the maximum of

2. Find the 2nd largest element of

The complexity measure for this problem is an ordered pair:

step1), step2)

Note: This is not the same as summing the 2 complexities. Comparison is done

in lexicographic order. For example, a naive algorithm would have paired

complexity:

Similarly, sorting first, then picking the right elements would have paired

complexity

The paired complexity of the sort-first method is worse than the naive method,

since lexicographic order has .

Your mission is to find a processing algorithm that is better than the naive

algorithm above. Write the Restricted Python code for your algorithm and give

the paired complexity for your algorithm.

L L

L

L

O( O(

O(n), O(n)

O(n log(n)), O(1)

O(n log(n)) > O(n)