Subject : Algorithms

Question 1. Solve the following recurrences using (a) repeated substitution method; and (b) master theorem if applicable, and state the reason if it cannot be applied 1.T(0) = 0, T(n) = 2T(m - 1)+1 2.T(1) = 5, T(n) = T(n 1) + 2n 3.T(1) = 1, T(n) = 3T($])+n 4.T(1) = 1, T(n) = 4T(%) +n3 5.T(1) = 1, T(n) =T(%) + log n Question 2. Design a divide-and-conquer algorithm for computing the number of levels in a binary tree. (In particular, the algorithm must return 0 and 1 for the empty and single node trees, respectively). What is the efficiency class of your algorithm? Question 3. Design a divide-and-conquer algorithm that finds a sub-array A[i, ..., j] such that A[i] + A[i + 1] + ... + A[j] is maximum and write recurrences relation, then, design an iterative algorithm and compare them