Work the following problems, some of which are borrowed from the book Data Structures and Algorithms in Java, 5th edition by Goodrich and Tamassia.
To receive full credit you will need to show your work. Final answers should be clearly marked. Write only on the front of a page. Staple multiple pages. All work should be legible.
power(x,n) // input: $x$ is a number and $n$ is a non-negative integer // output: $x^n$ if $n=0$ then return $1$ if $n$ is odd then y $\leftarrow$ power($x,(n-1)/2$) return $x \cdot y \cdot y$ else y $\leftarrow$ power($x,n/2$) return $y \cdot y$ |
You may attach a printout of your working program to the rest of your hand-written work.
fun1($A,n$) // input: $A$ is an array with $n \geq 1$ integers // output: the sum of elements at even-numbered indices in $A$ $s \leftarrow A[0]$ for $i \leftarrow 2$ to $n-1$ by increments of 2 do $s \leftarrow s + A[i]$ return $s$ |
fun2($A,n$) // input: $A$ is an array with $n \geq 1$ integers // output: the sum of the prefix sums in $A$ $s \leftarrow A[0]$ for $i \leftarrow 0$ to $n-1$ do $s \leftarrow s + A[0]$ for $j \leftarrow 1$ to $i$ do $s \leftarrow s + A[j]$ return $s$ |