Week $3$: Complexity Analysis and Divide$-$and$-$Conquer

Part $3$: Theoretical Questions $(25$ points$)$

Question $8$: Divide$-$and$-$Conquer Approach $(10$ points$)$

$($a$)$ What is the Divide$-$and$-$Conquer approach in algorithm design? $(2$ points$)$

$($b$)$ Provide two examples of algorithms that use the Divide$-$and$-$Conquer approach and explain how they apply it$.(3$ points$)$

$($c$)$ Explain the recurrence relation for Merge Sort and how it leads to the time complexity of $O(nlogn).(5$ points$)$

Question $9$: Recurrence Relations $(10$ points$)$

$($a$)$ What is a recurrence relation, and how is it used in analyzing recursive algorithms? $(3$ points$)$

$($b$)$ Solve the following recurrence relation using the Master Theorem:

$T(n)=3T(n2)+O(n)T(n)=3\frac{T}{\frac{?}{?}}$left$\frac{\frac{\frac{?}{?}}{f}\text{r}\text{a}\text{c}\{n\}2}{\frac{?}{?}}$right

$($c$)$ Explain how binary search fits into the Divide$-$and$-$Conquer approach and provide its recurrence relation. $(3$ points$)$

Question $10$: Amortized Analysis $(5$ points$)$

$($a$)$ What is amortized analysis, and how does it differ from worst$-$case and average$-$case analysis? $(3$ points$)$

$($b$)$ Give an example of an algorithm where amortized analysis is useful, and briefly explain how it works. $(2$ points$)$

Part $4$: Practical Questions $(25$ points$)$

Question $11$: Divide$-$and$-$Conquer Algorithm Implementation $(10$ points$)$

Task: Write a Python implementation of the Merge Sort algorithm. Your function should divide the list into smaller subproblems, sort each subproblem, and merge them back together. Include comments to explain each step. $(5$ points$)$

Task: Analyze the time and space complexity of your Merge Sort implementation. $(5$ points$)$

Question $12$: Recursion and Complexity $(10$ points$)$

Task: Write a Python function to calculate the nth Fibonacci number using a recursive approach. Then, analyze the time complexity of this recursive implementation. $(5$ points$)$

Bonus Task: Implement a memoized version of the Fibonacci function to improve the time complexity. Compare the time complexities of the recursive and memoized versions. $(5$ bonus points$)$