Lesson test: Divide and conquer

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Divide and conquer

1.[2p]
Why does the recursion tree for $T (n) = 2 T (n / 2) + n$ give $Θ (n \log n)$ ?

Every level costs $n$ in total, and there are about $\log_{2} n$ levels

Correct

The leaves dominate, and there are $n \log n$ of them

The answer is: Every level costs $n$ in total, and there are about $\log_2 n$ levels

The root costs $n \log n$

The answer is: Every level costs $n$ in total, and there are about $\log_2 n$ levels

Each level costs half the one above it

The answer is: Every level costs $n$ in total, and there are about $\log_2 n$ levels

2.[2p]
Put the three steps of divide and conquer in order.

Conquer each instance by solving it recursively down to a base case
Combine the sub-answers into an answer for the whole
Divide the problem into smaller instances of the same problem

Show the answer

b, c, a

3.[2p]
How many comparisons does mergesort make in the worst case on 16 elements? Use $n \log_{2} n - n + 1$ .

CorrectNot quite: 49

4.[2p]
For $T (n) = a T (n / b) + f (n)$ , the master theorem compares $f (n)$ against

$n^{\log_{b} a}$

Correct

$n^{a / b}$

The answer is: $n^{\log_b a}$

$a^{\log_{b} n}$ divided by $f (n)$

The answer is: $n^{\log_b a}$

$\log_{b} (a n)$

The answer is: $n^{\log_b a}$

5.[2p]
Naive block matrix multiplication obeys $T (n) = 8 T (n / 2) + Θ (n^{2})$ . What exponent does the master theorem give for $T (n)$ ?

CorrectNot quite: 3

6.[3p]
In Karatsuba's method for $1234 \times 5678$ with $a = 12$ , $b = 34$ , $c = 56$ , $d = 78$ , the middle term is $(a + b) (c + d) - a c - b d$ . What is it?

CorrectNot quite: 2840

7.[3p]
Karatsuba multiplication costs $Θ (n^{\log_{2} 3})$ rather than $Θ (n^{2})$ because

the middle term $a d + b c$ is obtained from one extra product rather than two

Correct

the numbers are split into three parts instead of two

The answer is: the middle term $ad + bc$ is obtained from one extra product rather than two

addition is cheaper than multiplication

The answer is: the middle term $ad + bc$ is obtained from one extra product rather than two

the recursion depth is $\log_{3} n$ rather than $\log_{2} n$

The answer is: the middle term $ad + bc$ is obtained from one extra product rather than two

8.[3p]
Which are true of mergesort?

Select all that apply

Its $Θ (n \log n)$ bound holds in the worst case, not just on average

Correct

It is stable when the merge prefers the left run on ties

Correct

It normally needs $Θ (n)$ extra memory

Correct

It runs in linear time on already-sorted input

The answer is: Its $\Theta(n \log n)$ bound holds in the worst case, not just on average, It is stable when the merge prefers the left run on ties, It normally needs $\Theta(n)$ extra memory

9.[2p]
Merging two sorted runs of four elements each takes at most how many comparisons?

CorrectNot quite: 7

10.[2p]
The master theorem settles every recurrence of the form $T (n) = a T (n / b) + f (n)$ .

True

The answer is: False

False

Correct

1.[2p] Why does the recursion tree for T(n)=2T(n/2)+n give Θ(nlogn)?

2.[2p] Put the three steps of divide and conquer in order.

3.[2p] How many comparisons does mergesort make in the worst case on 16 elements? Use nlog2n-n+1.

4.[2p] For T(n)=aT(n/b)+f(n), the master theorem compares f(n) against

5.[2p] Naive block matrix multiplication obeys T(n)=8T(n/2)+Θ(n2). What exponent does the master theorem give for T(n)?

6.[3p] In Karatsuba's method for 1234×5678 with a=12, b=34, c=56, d=78, the middle term is (a+b)(c+d)-ac-bd. What is it?

7.[3p] Karatsuba multiplication costs Θ(nlog23) rather than Θ(n2) because

8.[3p] Which are true of mergesort?

9.[2p] Merging two sorted runs of four elements each takes at most how many comparisons?

10.[2p] The master theorem settles every recurrence of the form T(n)=aT(n/b)+f(n).

1.[2p]
Why does the recursion tree for $T (n) = 2 T (n / 2) + n$ give $Θ (n \log n)$ ?

2.[2p]
Put the three steps of divide and conquer in order.

3.[2p]
How many comparisons does mergesort make in the worst case on 16 elements? Use $n \log_{2} n - n + 1$ .

4.[2p]
For $T (n) = a T (n / b) + f (n)$ , the master theorem compares $f (n)$ against

5.[2p]
Naive block matrix multiplication obeys $T (n) = 8 T (n / 2) + Θ (n^{2})$ . What exponent does the master theorem give for $T (n)$ ?

6.[3p]
In Karatsuba's method for $1234 \times 5678$ with $a = 12$ , $b = 34$ , $c = 56$ , $d = 78$ , the middle term is $(a + b) (c + d) - a c - b d$ . What is it?

7.[3p]
Karatsuba multiplication costs $Θ (n^{\log_{2} 3})$ rather than $Θ (n^{2})$ because

8.[3p]
Which are true of mergesort?

9.[2p]
Merging two sorted runs of four elements each takes at most how many comparisons?

10.[2p]
The master theorem settles every recurrence of the form $T (n) = a T (n / b) + f (n)$ .