$70$ In$.$

C $10$:$14$

AAUP E$-$Learn...

moodle.aaup.edu

Algorithms Analysis and Design

$$Assignment

$1$

Notes:

When you send the solution of the Assignment mention the HW characterizes of the used device

Insert the applied code before the Tables result.

Use the function that calculate time in the programming language used

Q$1$: Use Compiler $($ex: $C++$ to create $2(n**n)$ matrices $[$A$]*$

$[B]=[C].$ Generate A and B randomly as follows:

$[A]**[B]$

Execution Time

$[100**100]**[100**100]$

$[500**500]**[500**500]$

$[{1000}^{**}1000]**[{1000}^{**}1000]$

$[{2500}^{**}2500]**[2500**2500]$

$[{5000}^{**}5000]**[{5000}^{**}5000]$

$[{10000}^{**}10000]**[{10000}^{**}10000]$

$[{20000}^{**}20000]**[{20000}^{**}20000]$

Q$2$: A$)$ Use Compiler $($in: $C++)$ to create array $A=[dots..n],$ Generate A randomly as follows, then apply insertion and selection sort for the same generated array:

$A=[1$dots..$n]$ Insertion sort time Selection sort time

$100$

$500$

$1000$

$2500$

$5000$

$10000$

$25000$

$50000$

$100000$

B$)$ Apply insertion sort to sort the string "algorithm" in alphabetical order

Show each iteration of insertion sort on the string. Find the number of comparisons

Q$3$: Prove or disprove

$5n^2+40n+100=O(n^2).$

$\frac{n^3}{1000}=O(n^2).$

$f(n)={\displaystyle \underset{i=1}{\overset{n}{}}}i2.$ is $f(n)=\frac{O}{n^3}?$

$n^k=\frac{O}{2^n}$

${\displaystyle \underset{i=1}{\overset{n}{}}}logi=\frac{O}{nlogn}$

$7^n=(9^n)$