What is the main advantage of using the divide and conquer approach in algorithms?
Think about how breaking a problem into parts can help solve it faster.
Divide and conquer splits a big problem into smaller parts, solves each part separately, and then combines the answers. This often makes the solution faster and easier to manage.
What is the printed output after running this TypeScript code that uses divide and conquer to sort an array?
function merge(left: number[], right: number[]): number[] {
let result: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
const unsorted = [5, 3, 8, 4, 2];
const sorted = mergeSort(unsorted);
console.log(sorted);Merge sort sorts the array in ascending order by dividing and merging.
The mergeSort function splits the array repeatedly, sorts each half, and merges them back in order. The final output is the sorted array.
Consider this recursive function that tries to use divide and conquer. What causes the stack overflow error?
function faultyDivide(arr: number[]): number[] {
if (arr.length === 0) return [];
const mid = Math.floor(arr.length / 2);
const left = faultyDivide(arr.slice(0, mid));
const right = faultyDivide(arr.slice(mid));
return left.concat(right);
}
faultyDivide([1, 2, 3, 4]);Think about when recursion should stop to avoid infinite calls.
The base case only stops when the array is empty, but it should also stop when the array has one element. Without this, recursion never ends, causing stack overflow.
What is the output of this TypeScript code that uses divide and conquer to find the k-th smallest element?
function quickSelect(arr: number[], k: number): number {
if (arr.length === 1) return arr[0];
const pivot = arr[Math.floor(arr.length / 2)];
const lows = arr.filter(x => x < pivot);
const highs = arr.filter(x => x > pivot);
const pivots = arr.filter(x => x === pivot);
if (k <= lows.length) {
return quickSelect(lows, k);
} else if (k > lows.length + pivots.length) {
return quickSelect(highs, k - lows.length - pivots.length);
} else {
return pivot;
}
}
const array = [7, 10, 4, 3, 20, 15];
const k = 3;
console.log(quickSelect(array, k));QuickSelect finds the k-th smallest element by partitioning around a pivot.
The sorted array is [3,4,7,10,15,20]. The 3rd smallest element is 7, which the algorithm finds by dividing and conquering.
Besides improving speed, what is another key benefit of using divide and conquer in algorithm design?
Think about how breaking problems down affects code clarity and maintenance.
Divide and conquer helps by making complex problems simpler to handle. Each smaller part is easier to understand, test, and fix, improving code quality.