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)
