$(1)(4$ marks$)$ Study the $$smart$$ Sieve algorithm $($we discussed it in our class$)$ for finding

all the prime numbers that are smaller or equal to a positive integer bigger than $1.$ When

index variable i changes, we need to check $2*$ i$,3*$ i$,$ etc., to eliminate them, since we

are sure that $2*$ i$,3*$ i$,$ etc. are not prime numbers. However, we can change the

algorithm such that the first number we need to check is i $*$ i$.$ This obviously skips some

numbers.

$($a$)$ Argue briefly that this is safe, i$.$e$.,$ the algorithm is still correct.

$($b$)$ In the notes, we purposely left the upper bound of the algorithm blank. What should it

be$?$ Argue that your answer is correct.

$(2)(4$ marks$)$ Use the definition of O$-$notation to argue that the following statements are

correct.

$($a$)100$n$3+2000$n $+12000$ O$($n$3)$

$($b$)230$n $$ O$($n$)$

$(3)(4$ marks$)$ Use the definition of $\backslash$Omega $-$notation to argue that the following statements are

correct.

$($a$)100$n$3+2000$n $+12000\backslash$Omega $($n$3)$

$($b$)2$nlogn $\backslash$Omega $($n$)$

$(4)(3$ marks$)$ Use the definition of $\backslash$Theta $-$notation to argue that the following statement is

correct.

$3$n$($n$2-1)\backslash$Theta $($n$3)$

$(5)(3$ marks$)$ Use the definition of $\backslash$Theta $-$notation to prove that, if f$($n$)\backslash$Theta $($g$($n$))$ and g$($n$)$

$\backslash$Theta $($h$($n$)),$ then f$($n$)\backslash$Theta $($h$($n$)).$

$(6)(4$ marks$)$ Solve the following recurrence relations.

$($a$)$ T$($n$)=3$T$($n$-1)$ for n $>1,$ where T$(1)=4$

$($b$)$ T$($n$)=$ T$($n$/3)+1$ for n $>1,$ where T$(1)=1$

$(7)(5$ marks$)$ Write a recursive algorithm to find the maximum element in an array of n

elements. Analyze its time efficiency.

$(8)(8$ marks$)$ Consider the following algorithm and answer the related questions.

Input: a nonnegative integer n

xyz$($n$)\{$

x $=0$;

for i $=1$ to n do $\{$

x $=$ x $+$ i $*$ i

$\}$

$\}$

$($a$)$ What does this algorithm compute?

$($b$)$ What are the basic operations in this algorithm?

$($c$)$ What is its time efficiency in terms of the number of basic operations that are

executed?

$($d$)$ Can you improve its time efficiency? Provide your solution.