$1.$ Answer the following:

$($a$)$ Design and analyze a recursive version of the LOGICALAND$($A$,$B$,$C$,$p$,$r$)$ algorithm

that uses a divide$-$and$-$conquer approach in which the algorithm divides the array

elements p$..$r in half and calls itself recursively on each half. Specifically, give

pseudocode for your recursive LOGICALAND$($A$,$B$,$C$,$p$,$r$)$ algorithm. The initial call to

your algorithm would pass $1$ in for p and n for r$.$ Don$$t use global variables.

$($b$)$ Design and analyze an iterative version of the LOGICALAND$($A$,$B$,$C$,$p$,$r$)$ algorithm.

$($c$)$ Perform a line$-$by$-$line analysis of your algorithms in $($a$)$ and $($b$)$ and derive a

recurrence T$($n$)$ for the running time, where n $=$ r $-$ p $+1.$ You may assume that each line

of pseudocode takes unit time $($i$.$e$.,$ c i $=1),$ except, of course, those lines containing non$-$

primitive operations.

$($d$)$ Compare the order of growth of the two versions and determine which one is better in

terms of order of growth and practical use.

$2.$ Solve the following recurrences:

a$)$ T$($n$)=3$T$($n$-1)+4$T$($n$-2)+2,$ n$>0,$ where T$(0)=$T$(1)=1$

b$)$ T$($n$)=2$T$($n$/4)+$n$,$ n$>1,$ where T$(1)=1$

c$)$ T$($n$)=5$T$($n$/16)+$n $1/2+$n$,$ n$>0,$ where T$(0)=2$