Exam 1 - Divide and Conquer

Question 1

Is pseudocode allowed in the D&C written questions?

Answer 1

No

Question 2

In the D&C written questions, each recurrence should be a ____ problem than before

Answer 2

Smaller

Question 3

In the D&C written questions, each solution must be more efficient than ____

Answer 3

The brute force solution

Question 4

In the D&C written questions, what are the three sections expected?

Answer 4

Algorithm Description
Correctness Justification
Runtime Analysis

Question 5

In the D&C written questions, what is expected in the Algorithm Description section?

Answer 5

How to solve the problem

Question 6

In the D&C written questions, what is expected in the Justification of Correctness section?

Answer 6

Why the algorithm solves the problem

Question 7

In the D&C written questions, what is expected in the Runtime Analysis section?

Answer 7

The big-O runtime of the algorithm, including the big-O runtimes for all nontrivial steps of the algorithm

Question 8

In the D&C written questions, can the master theorem be used for the runtime analysis?

Answer 8

Yes

Question 9

What is the input for FastMultiply?

Answer 9

Two n-bit integers x and y, where n is some power of two

Question 10

What is the output of FastMultiply?

Answer 10

x times y

Question 11

FastMultiply starts by splitting x and y into what components?

Answer 11

X_l, Y_l, X_r, Y_r

They are the left and right n/2 bits of x and y

Question 12

After FastMultiply splits X and Y into left and right halves, how does it calculate the three subproblems?

Answer 12

A is FastMultiply(X_l,Y_l)
B is FastMultiply(X_r,Y_r)
C is FastMultiply(X_l+X_r,Y_l+Y_r)

Question 13

After FastMultiply calculates A, B, and C, how does it use those values to calculate the output value?

Answer 13

2^n * A +
2^(n/2) * (C - A - B)
+ B

Question 14

What’s the input formula for the master theorem?

Answer 14

Question 15

What are the input constraints of the master theorem?

Answer 15

a > 0, b > 1, d >= 0

Question 16

What is the result of the master theorem if d > log (b, a)

Answer 16

O(n^d)

Question 17

What is the result of the master theorem if d = log (b, a)

Answer 17

O(n^d log n)

Question 18

What is the result of the master theorem if d < log (b, a)

Answer 18

O(n^(log(b,a)))

Question 19

What is the recurrence for the runtime of fastmultiply?

Answer 19

T(n) = 3T(n/2) + O(n)

Question 20

What does the master theorem tell us the big-O of fastmultiply is, given that its recurrence is T(n) = 3T(n/2) + O(n)

Answer 20

O(n^(log(2,3)))

Question 21

What is the input of mergesort?

Answer 21

An array of numbers a[1…n]

Question 22

What does mergesort return if the input array has size 1?

Answer 22

The input array, unmodified

Question 23

What does mergesort return if the input array has size > 1

Answer 23

Question 24

In mergesort, what does the merge subroutine do if either if the inputs is empty?

Answer 24

It returns the other input

Question 25

In mergesort, the merge subroutine is given two arrays, x[1…k] and y[1…l]. What does it do if x[1] is <= y[1]?

Answer 25

Question 26

In mergesort, the merge subroutine is given two arrays, x[1…k] and y[1…l]. What does it do if x[1] is NOT <= y[1]?

Answer 26

Question 27

What is the recurrence of the runtime for mergesort?

Answer 27

T(n) = 2T(n/2) + O(n)

Question 28

What is the runtime for mergesort, given that the recurrence is T(n) = 2T(n/2) + O(n) ?

Answer 28

O(n log n)

Question 29

What is FastSelect for?

Answer 29

Finding the kth smallest element in an unsorted list of numbers

Question 30

What are the inputs to FastSelect?

Answer 30

A, an unsorted list of numbers of size n
k, an integer 1 <= k <= n

Question 31

What is the first step of FastSelect?

Answer 31

Break A into n/5 groups, G1, G2, … G(n/5)

Question 32

After splitting A into the n/5 G groups, what does FastSelect do next?

Answer 32

For i from 1 to n/5, sort Gi and let m_i be the median of Gi

Question 33

After calculating the Gi medians, what does FastSelect do?

Answer 33

Creates set S which includes all of the medians of the G groups

S = {m_1, m_2, …, m_(n/5)}

Question 34

After creating set S, what does FastSelect do?

Answer 34

It finds the pivot value p by recursing on S

p = FastSelect(S, n/10)

Question 35

After calculating the pivot value p, what does FastSelect do?

Answer 35

It partitions A into A<p, A=p, A>p

Question 36

After partitioning A based on pivot p, what does FastSelect do if k <= |A<p|?

Answer 36

It recurses on the A<p set

return FastSelect(A<p, k)

Question 37

After partitioning A based on pivot p, what does FastSelect do if k > |A<p| + |A=p|?

Answer 37

It recurses on the A>p set

return FastSelect(A>p, k-|A<p|-|A=p|)

Question 38

After partitioning A based on pivot p, what does FastSelect do if k is not <= |A<p| and not > |A<p| + |A=p|?

Answer 38

it returns p

Question 39

What is the runtime of the step of FastSelect where it breaks A into n/5 groups of 5 elements each?

Answer 39

O(n)

Question 40

What is the runtime of the step of FastSelect where it sorts the G groups, calculates their medians, and creates set S?

Answer 40

O(1) per group, which results in O(n)

Question 41

What is the recurrence of the step of FastSelect where it calculates pivot p based on the set of medians S?

Answer 41

T(n/5)

Question 42

What is the recurrence of the step of FastSelect where it recurses on one of the partitioned sections of A?

Answer 42

T((3/4)n)

Question 43

Why do we know that FastSelect finds a good pivot p value?

Answer 43