Divide and Conquer Alogrithms

Question 1

What is the Max Subarray Problem?

Answer 1

It asks for indices i and j in an array A such that A[j] - A[i] is maximized, and i ≤ j.

Question 2

What is the practical application of the Max Subarray Problem mentioned in the lecture?

Answer 2

Retrospective stock trading — determining when to buy and sell for maximum profit.

Question 3

What is the constraint on buying and selling in the Max Subarray Problem?

Answer 3

No short selling; you must buy before you sell (i ≤ j).

Question 4

What is the time complexity of the brute force solution?

Answer 4

Theta(n^2)

Question 5

How does the brute force solution work?

Answer 5

It uses two nested loops to evaluate A[j] - A[i] for all i < j.

Question 6

What are the three main steps in a divide and conquer algorithm?

Answer 6

Divide, Recurse, Combine.

Question 7

In the divide step, how is the array divided?

Answer 7

It is split into two halves: A[l to m] and A[m+1 to u], where m = (l + u) // 2.

Question 8

What are the three cases considered when combining solutions?

Answer 8

1) Max subarray in left half, 2) Max subarray in right half, 3) Max subarray straddling the midpoint.

Question 9

How is the straddling case handled in the algorithm?

Answer 9

By computing min in the left half and max in the right half, then taking their difference.

Question 10

What is the time complexity of the divide and conquer solution?

Answer 10

Theta(n log n)

Question 11

Why is the divide and conquer approach more efficient?

Answer 11

It reduces the time complexity from quadratic (Theta(n^2)) to near-linear (Theta(n log n)).

Question 12

What is the main idea behind divide and conquer algorithms?

Answer 12

Divide the problem into subproblems, solve each recursively, and combine their solutions.

Question 13

What are the three main phases of a divide and conquer algorithm?

Answer 13

Divide, Conquer, Combine

Question 14

What does the ‘Divide’ step do in divide and conquer?

Answer 14

It splits the problem into smaller subproblems.

Question 15

What happens in the ‘Conquer’ step of divide and conquer?

Answer 15

Each subproblem is solved, usually recursively.

Question 16

What is the purpose of the ‘Combine’ step in divide and conquer?

Answer 16

To merge the solutions of subproblems into a solution for the original problem.

Question 17

What is the time complexity of Merge Sort?

Answer 17

Θ(n log n)

Question 18

In Merge Sort, which step is most costly in terms of time?

Answer 18

The Combine step, which takes Θ(n) time.

Question 19

In Quick Sort, where is the majority of the work done?

Answer 19

In the Divide step (partitioning), which takes Θ(n) time.

Question 20

What is the role of the pivot in Quick Sort?

Answer 20

It is used to partition the array into two subarrays.

Question 21

What is a method to choose a good pivot in Quick Sort?

Answer 21

The Median of Medians trick.

Question 22

What is the time complexity of Binary Search?

Answer 22

Θ(log n)

Question 23

Which step is the most computationally expensive in Binary Search?

Answer 23

None, each step is Θ(1); the recursion provides the efficiency.

Question 24

What is the Master Method used for?

Answer 24

To analyze the time complexity of divide and conquer algorithms.

Question 25

How does Merge Sort split the input?

Answer 25

Into two equal parts, assuming n is even.

Question 26

How does Binary Search determine which half to search?

Answer 26

By comparing the target with the middle element.

Question 27

What is the word size in modern CPUs?

Answer 27

64 bits

Question 28

How are large numbers represented for computation?

Answer 28

As arrays of binary bits (bit strings)

Question 29

Why is big number arithmetic important?

Answer 29

It's essential for cryptography and large integer operations.

Question 30

What is the purpose of the carry variable in binary addition?

Answer 30

To handle overflow during bit-wise addition.

Question 31

What is the complexity of binary addition for n-bit numbers?

Answer 31

Θ(n)

Question 32

What is the time complexity of grade-school multiplication?

Answer 32

Θ(n^2)

Question 33

How does grade-school multiplication work?

Answer 33

Multiply each bit of one number with the other and shift accordingly, then add all results.

Question 34

How does divide and conquer multiplication initially work?

Answer 34

Split numbers in halves and recursively multiply, add, and pad results.

Question 35

Why doesn't basic divide and conquer improve time complexity over grade-school method?

Answer 35

Because it still performs four n/2-bit multiplications.

Question 36

What is the recurrence relation for naive divide and conquer multiplication?

Answer 36

T(n) = 4T(n/2) + Θ(n)

Question 37

What trick is used in Karatsuba’s algorithm?

Answer 37

Use (A1+A2)(B1+B2) to replace two multiplications with one.

Question 38

How many multiplications does Karatsuba’s algorithm perform?

Answer 38

Three

Question 39

What is the recurrence relation for Karatsuba’s algorithm?

Answer 39

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

Question 40

What is the time complexity of Karatsuba’s algorithm?

Answer 40

Θ(n^1.585)

Question 41

Why is Karatsuba’s algorithm faster than grade-school multiplication?

Answer 41

Fewer recursive multiplications lead to faster asymptotic growth.

Question 42

What does multiplying a binary number by 2^k mean?

Answer 42

Appending k zeros to the number.

Question 43

What is a recurrence relation?

Answer 43

An equation that defines a sequence recursively: each term is defined in terms of previous terms.

Question 44

What is divide and conquer?

Answer 44

An algorithm design strategy where a problem is broken into smaller subproblems, solved recursively, and combined.

Question 45

In a recurrence T(n) = a·T(n/b) + f(n), what does 'a' represent?

Answer 45

The number of subproblems the problem is divided into.

Question 46

In a recurrence T(n) = a·T(n/b) + f(n), what does 'b' represent?

Answer 46

The factor by which the problem size is reduced.

Question 47

In a recurrence T(n) = a·T(n/b) + f(n), what does 'f(n)' represent?

Answer 47

The cost of the divide and combine steps outside the recursive calls.

Question 48

What is the Master Method used for?

Answer 48

To solve recurrences of the form T(n) = a·T(n/b) + Θ(n^c) in divide-and-conquer algorithms.

Question 49

Master Method Case 1 condition?

Answer 49

If log_b(a) > c, then T(n) = Θ(n^log_b(a)).

Question 50

Master Method Case 2 condition?

Answer 50

If log_b(a) = c, then T(n) = Θ(n^c·log n).

Question 51

Master Method Case 3 condition?

Answer 51

If log_b(a) < c, then T(n) = Θ(n^c).

Question 52

What is the result of T(n) = 2·T(n/2) + Θ(n)?

Answer 52

Θ(n·log n) - Example: Merge Sort or Max Subarray.

Question 53

What is the result of T(n) = 3·T(n/2) + Θ(n)?

Answer 53

Θ(n^1.58) - Example: Karatsuba Multiplication.

Question 54

What is the result of T(n) = 4·T(n/2) + Θ(n)?

Answer 54

Θ(n^2) - Example: Naive Multiplication.

Question 55

What is the result of T(n) = 7·T(n/2) + Θ(n^2)?

Answer 55

Θ(n^2.81) - Example: Strassen's Matrix Multiplication.

Question 56

How do you calculate log_b(a)?

Answer 56

Use the formula log_b(a) = ln(a)/ln(b).

Question 57

What are the steps to apply the Master Method?

Answer 57

1. Identify a, b, c. 2. Compute log_b(a). 3. Compare with c. 4. Apply the correct case.

Question 58

What does the expansion method do?

Answer 58

It repeatedly expands the recurrence to a base case to find a pattern and solve it.

Question 59

What is a signal in the context of Fourier Transforms?

Answer 59

A signal is a sequence of values over time, such as stock prices, voice recordings, or temperature data.

Question 60

What does the Fourier Transform do?

Answer 60

It converts a time-domain signal into its frequency components, revealing the contribution of each frequency.

Question 61

What is the Discrete Fourier Transform (DFT)?

Answer 61

A version of the Fourier Transform for discrete-time signals; it converts n time samples into n frequency components.

Question 62

What is the Inverse Fourier Transform?

Answer 62

It converts frequency components back into the original time-domain signal.

Question 63

Why do Fourier Transforms use complex numbers?

Answer 63

Because the frequency components often involve phase and amplitude, which are represented naturally using complex numbers.

Question 64

What is the form of a complex number?

Answer 64

a + bj, where 'a' is the real part, 'b' is the imaginary part, and j = sqrt(-1).

Question 65

How do you compute the modulus of a complex number a + bj?

Answer 65

modulus = sqrt(a^2 + b^2)

Question 66

What is the polar form of a complex number?

Answer 66

z = re^(jθ), where r is the modulus and θ is the phase angle.

Question 67

What does multiplying two complex numbers do in polar form?

Answer 67

Multiplies their magnitudes and adds their angles.

Question 68

What is a root of unity?

Answer 68

A complex number ω such that ω^n = 1 for some integer n.

Question 69

What is the general form of the nth root of unity?

Answer 69

ω_k = e^(2πjk / n), for k = 0 to n-1.

Question 70

What is the time complexity of the Fast Fourier Transform (FFT)?

Answer 70

O(n log n)

Question 71

What is the complex conjugate of a + bj?

Answer 71

a - bj

Question 72

What is the purpose of the FFT algorithm?

Answer 72

To compute the DFT efficiently using divide-and-conquer strategy.

Question 73

How are discrete signals typically represented?

Answer 73

As a sequence of samples: a_0, a_1, ..., a_{n-1}.

Question 74

What happens if you remove high-frequency components from a signal?

Answer 74

You get a smoothed or denoised version of the original signal.

Question 75

How is 1 represented as a complex number?

Answer 75

1 = e^(j*0), with modulus 1 and angle 0 radians.