Answer all three provided exercises below starting with Exercise $1$

Divide and conquer

Write a function to calculate $a^b($a raised to the power of b$)$ using a divide$-$and$-$

conquer approach. The function should handle both positive and negative integer

values of $b,$ as well as edge cases where $a$ is $0.$ The goa Exercise $2$

Binary Search Tree

In Lecture $7,$ we discussed binary search trees and an algorithm to find the successor

of a given node x $.$ Using that concept, write the pseudocode for the TREE$-$

PREDECESSOR procedure, which returns the predecessor of a specific node $x.$ Exercise $3$

Dynamic Programming

Write a program that calculates the nth Fibonacci number using dynamic

programming. The Fibonacci sequence is defined as follows:

$F(0)=0$

$F(1)=1$

$F$ For $n2,F(n)=F(n-1)+F(n-2)$

Your program should use a dynamic programming approach to store intermediate

results and avoid redundant computations. Specifically:

Implement the solution using a bottom$-$up approach $($iterative$).$

The input to the program should be an integer $n($where $n0).$

Your solution should achieve a time complexity of $O(n).$

Write the pseudocode for the algorithm and explain its time and space complexity.l is to achieve a time

complexity of $O(b)$ or better $($ideally $O(lgb)).$

Requirements:

a can be any integer $($positive$,$ negative, or zero$).$

b can be any integer $($positive$,$ negative, or zero$).$

If $a=0$ and $b0,$ return an error message.

Write the pseudocode for your algorithm and specify its time complexity $($Big$-$O

notation$).$