Homework $1$

$(100$ points$)$

$(30$ points$)1.$ Compute and explain the time complexity of the following recursive functions.

$(6$ points$)1\mathrm{.}1,T(n)=2T(\frac{n}{3})+\sqrt[\phantom{2}]{n}$

$(7$ points$)1\mathrm{.}2T(n)=T(\frac{n^3}{2})+\sqrt[\phantom{2}]{n}logn$

$(7$ points$)1\mathrm{.}3T(n)=3T(\frac{n}{3})+\frac{\sqrt[\phantom{2}]{n}}{lo{g}^{2}n}$

$(10$ points$)1\mathrm{.}4T(n)=3T(\frac{n}{2})+n^2($It is required to use the iterative method.$)$

$(5$ points$)2.$ Apply Amdahl's Law to compute the theoretical speedup of program execution if

$98\%$ of a sequential program in terms of execution time is parallelized by $196$ threads $($processor

cores$).$

$(65$ points$)$ Compare the behavior of a binary min$-$heap, an AVL tree, and a splay tree, based

on the following operations.

Perform each operation $($Building$,$ Search, and Insertion$)$ five times, and report the individual

times as well as the mean and standard deviation.

$(30$ points$)3\mathrm{.}1$ Building

$(10$ points$)3\mathrm{.}1\mathrm{.}1$ Build each data structure with $50K$ unique elements to do this list the numbers

from $1$ to $50,000.$ Then use a permutation function to permute the set. Then insert the numbers

one by one to build the data structure.

$(10$ points$)3\mathrm{.}1\mathrm{.}2$ Report the time taken to build each data set.

$(10$ points$)3\mathrm{.}1\mathrm{.}3$ Report the number of swaps in the heap. The number of rotations in the AVL

tree and the Splay tree.

$(20$ points$)3\mathrm{.}2$ Search

$(10$ points$)3\mathrm{.}2\mathrm{.}1$ Report times to find the $50$ lowest numbers in the data structures.

$(10$ points$)3\mathrm{.}2\mathrm{.}2$ Report times to find $50$ random numbers in the data structures.

$(10$ points$)3\mathrm{.}3$ Insertion: Insert a set of $5000$ random numbers that are not in the original data

structure, and report the time for each insertion.

$(5$ points$)3\mathrm{.}4$ Discuss the behavior of the data structures along with which type of problems are

most suitable for which data structures. Use the runtimes to support your analysis.

Note: It is required to submit a PDF file for Problems $1-3$ and a ZIP file including all the source

code in $\frac{C}{C}++$ in Linux with Makefile for Problem $3.$