Ch. 5

Question 1

Divide and Conquer

Answer 1

1. Divide instance of problem into two or more smaller instances.
2. Solve smaller instances recursively.
3. Obtain solution to original (larger) instance by combining these solutions.

Question 2

Divide and Conquer Recurrence

Answer 2

The form T(n) = aT(n/b) + f(n)
where f(n) ∈ Θ(n^d), d >= 0

Question 3

Common Sorting Algorithms

Answer 3

Selection Sort
Bubble Sort
Insertion Sort
Mergesort
Quicksort

Question 4

Mergesort

Answer 4

A divide-and-conquer approach to sorting.
1. Split the array A[1..n] in two and make copies of each half in arrays B[1..⌊n/2⌋] and C[1..⌈n/2⌉].
2. Sort arrays B and C.
3. Merge sorted arrays B and C into array A.

Question 5

Quicksort

Answer 5

A divide-and-conquer approach to sorting.
1. Select pivot point p
2. Rearrange the list so that all elements in the first s positions are ≤ p and the elements in the remaining n-s positions are ≥ p.
3. Exchange the pivot with the last element in the first subarray, and it is now in its final position.
4. Sort the two subarrays recursively

Question 6

f(n) ∈ Θ(nᵈ)

Answer 6

f(n) runtime scales on the order of n^d.

Question 7

Divide and Conquer Master Theorem

Answer 7

If a < bᵈ, T(n) ∈ Θ(nᵈ)
If a = bᵈ, T(n) ∈ Θ(nᵈlogn)
If a > bᵈ, T(n) ∈ Θ(n^logb(a))

Question 8

Merge sorted arrays B and C

Answer 8

Repeat until no elements remain in one of the arrays:
- Compare the first elements in the remaining unprocessed portions of the arrays.
- Copy the smaller of the two into A, while incrementing the index indicating the unprocessed portion of that array.
Once all elements on one of the arrays are processed, copy the remaining unprocessed elements from the other array into A.

Question 9

Hoare’s Algorithm

Answer 9

Two-directional scan partitioning algorithm.
1. Repeat until i and j pointers cross:
- Scan i from left to right so long as a[i] < p
- Scan j from right to left so long as a[j] > p
2. Exchange a[i] with a[j].
3. When pointers cross, exchange p with a[j[.

Question 10

Mergesort time complexity

Answer 10

O(nlogn)
The O(logn) comes from partitioning the array into two equal halves.
The O(n) comes from the comparisons done when merging.

Question 11

Quicksort time complexity

Answer 11

Best and avg case: O(nlogn)
- Pivot always partitions the array equally, like mergesort.
Worst case: O(n^2)
- Pivot always ends up in first or last element and the array is partitioned as unequally as possible.

Question 12

Master Theorem for 16T(n/4)+n

Answer 12

a = 16
b = 4
d = 1

16 > 4

Θ(n^(log₄16) = Θ(n²)

Question 13

Master Theorem for 7T(n/3) + n²

Answer 13

a = 7
b = 3
d = 2

7 < 9

Θ(n²)