Sort the list C $,$ O$,$ M $,$ P$,$ U $,$ T $,$ E$,$ R in alphabetical order by Selection sort

Solve the following recurrence relations using backward substution.

a$)x(n)=x(n-1)+n-1$ for $n>0,x(0)=0$

b$)x(n)=x(\frac{n}{3})+n$ for $n>1,x(1)=1$

c$)x(n)=2x(\frac{n}{2})+6$ for $n>1,x(1)=0$

Write the Algorithm for Travel Salesman Problem with its efficiency.

ALGORITHM S$($n$)$

$//$Input: A positive integer $n$

$//$Output: The sum of the first $n$ cubes

if $n=1$ return $1$

else return $S(n-1)+n^{**}{?}^{**}{n}^{**}n$

a$.$ Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed.

b$.$ How does this algorithm compare with the straightforward non recursive algorithm for computing this sum?

$9.$ Find $GCD(46,290)$ by applying Euclid's algorithm.

$10.$ For each of the following functions $C(n),$ indicate how much the Running Time $T(n)$ will change its input is increased triple fold.

$($a$)\sqrt[\phantom{2}]{?}{n}^3$

$($b$)lo{g}_{2}n$

$($c$)3^n$

d$)n^4$

Important Instructions:

$?]$ Submit the soft copy of your assignment on Blackboard. Do not submit the hard copy image.

$?]$ Make the Assignment Name like this $($your ID$.$Assignment$\_1)$

$?$ Take proper care during submission of Assignment; submit it in proper group and proper document. After the submission kindly check the document again. If you have submitted the wrong document or in a wrong group, immediately contact me to me $($Course Teacher$).($via WhatsApp$)$

$[?$ Submit the Assignment soft copy BEFORE $23$:$59$hrs of the due date.

$?$ If you submit your assignment late. Each day, $10\%$ penalty will incur of the total marks scored by the students.