Problem Set 3
Explore recursive problem-solving techniques with practical coding exercises. This lesson covers implementation and complexity analysis of a 3-way merge sort, optimized string permutations, and n-dimensional integer lists. Understand how to evaluate recursion depth, time, and space complexity for these algorithms.
We'll cover the following...
We'll cover the following...
Question 1
In the lesson on Recurrence, we implemented merge sort where we divided the array into two parts at each recursion step. Imagine you are asked to implement merge sort by dividing the problem into three parts instead of two. You can assume for simplicity that the input size will always be a multiple of 3. Use a priority queue to merge sub-arrays in the combine step.
...