SubjectANALYSIS OF ALGORITHMS

(3)

Prove or disprove: SUM{i**2} [where i changes from i=1 to i=n] theta(n**2).

(4)

Write out the algorithm (pseudocode) to find K in the ordered array by the method 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?

(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:

Again, in case you dont have any programming language at hand you can use pseudocode to solve the problem.

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?

(6)

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: You have to start with n=1, then make assumption what you make expect for any given n = N, and check if the formula you found works for n =N+1.

This is what we call prove by induction.

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