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:

$\backslash$table$[[[A]**[B],\backslash$table$[[$Execution$],[$Time$]]],[[100**100]**[100**100],],[[500**500]**[500**500],],[[1000**1000]**[1000**1000],],[[2500**2500]**[2500**2500],],[[5000**5000]**[5000**5000],],[[1000****10000]**[10000**10000],],[[20000**20000]**[20000**20000],]]$

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

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

$\backslash$table$[[A=[1$dotsdotsn$],\backslash$table$[[$Insertion sort$],[$time$]],\backslash$table$[[$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}$

nlogn