Divide and Conquer Strategy and Recurrence Relations in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the midpoint for dividing the array.

DSA Typescript

const mid = Math.floor((start + [1]) / 2);

Drag options to blanks, or click blank then click option'

Amiddle

Bstart

Clength

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'start' instead of 'end' causes incorrect midpoint.

Using 'length' is invalid here.

The midpoint is calculated by averaging the start and end indices.

2fill in blank

medium

Complete the code to recursively call the function on the left half.

DSA Typescript

return divideAndConquer(arr, start, [1]);

Drag options to blanks, or click blank then click option'

Amid

Bmid + 1

Cend

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'mid + 1' skips the midpoint element.

Using 'end' includes the whole array.

The left half ends at the midpoint index.

3fill in blank

hard

Fix the error in the base case condition to stop recursion correctly.

DSA Typescript

if (start [1] end) return arr[start];

Drag options to blanks, or click blank then click option'

A!==

B===

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '<' causes infinite recursion.

Using '!==' is incorrect for base case.

The base case is when start equals end, meaning one element left.

4fill in blank

hard

Fill both blanks to complete the recurrence relation function.

DSA Typescript

function T(n) {
  if (n [1] 1) return 1;
  return 2 * T(n [2] 2) + n;
}

Drag options to blanks, or click blank then click option'

A<=

B>

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' in base case causes wrong stopping.

Using '-' instead of '/' changes the recurrence.

The base case is when n is less than or equal to 1. The recurrence calls T with n divided by 2.

5fill in blank

hard

Fill all three blanks to complete the merge step in merge sort.

DSA Typescript

while (i < left.length && j < right.length) {
  if (left[i] [1] right[j]) {
    result.push(left[[2]]);
    i[3];
  } else {
    result.push(right[j]);
    j++;
  }
}

Drag options to blanks, or click blank then click option'

A<=

B<

Ci

D++

E--

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes duplicates to be handled incorrectly.

Using '--' decrements index wrongly.

We compare left[i] & right[j] using '<'. We push left[i] and increment i with '++'.