Problem $1\mathrm{.}14$ from the Baase$$s textbook, page $62$:

Give a formula for SUM$\{$i$\}[$i changes from i$=$a to i$=$n$],$ where a is an integer between $1$ and n$.$

Problem $1\mathrm{.}27$ from the Baase$$s textbook, page $64$:

Suppose Algorithm$-1$ does f$($n$)=$ n$2+4$n steps in the worst case, and Algorithm$-2$ does g$($n$)$

$=29$n $+3$ steps in the worst case, for inputs of size n$.$ For what input sizes is Algorithm$-1$

faster than Algorithm$-2($in the worst case$)?$

Problem $1\mathrm{.}40$ from the Baase$$s textbook, page $65$:

Prove or disprove: SUM$\{$i$2\}[$where i changes from i$=1$ to i$=$n$]\backslash$epsi $\backslash$Theta $($n$2).$

$($Q$4)[10$ pts$.]$ Problem $1\mathrm{.}41$ from the Baase$$s textbook, page $65$:

Write out the algorithm to find K in the ordered array by the method suggested in the text $($Section $1\mathrm{.}6)$ that compares K to every fourth entry until K itself or an entry larger than K is

found, and then, in the latter case, searches for K among the preceding three. How many

comparisons does your algorithm do in the worst case?

$($Q$5)$ Design and implement $($meaning write code and execute the code turning in test

cases and source code$)$ for the following two algorithms to raise an integer to an integer

power assume in both cases that n$,$ the exponent, is a power of $2$:

Algorithm $1$

X$**$N $=$ X$*$ X$**($N$-1)$

X$**0=1$

Algorithm $2$

n $=2**$m

X$**$n $=(($X$**2)**2)**2...,$ etc. $[$NOTE: the symbol of power $(**)$ is used m times here,

i$.$e$.,$ X$**8=(($X$**2)**2)**2,$ because $8=2**3].$

Which algorithm is more efficient with respect to the number of multiplications?

$($Q$6)[20$ pts$.]$ Answer questions $($a$)$ and $($b$)$ below:

$($a$)$ How many times exactly is the code block below executed?

For $($i $=1,$ n$)$

$\{$

For $($j $=1,$ i$)$

$\{$

For $($k $=1,$ j$)$

$\{$

code block

$\}$

$\}$

$\}$

HINT: Take a long look at Example $3\mathrm{.}4$ on pages $112-113$ of the Baase$$s text.

$($b$)$ What is the theta value of this code segment?

$($Q$7)[20$ pts$.]$ Let A$1=$ event $$odd number on first die$$; A$2=$ event $$odd number on second die$$;

A$3=$ event $$odd total on both die$.$

Show that the following three events are independent:

$\{$A$1,$ A$2\}$

$\{$A$2,$ A$3\}$

$\{$A$1,$ A$3\}$

Show that the fourth event $\{$A$1,$ A$2,$ A$3\}$ is NOT independent.