Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS566 Homework-1

(1) [10 pts.] Prove using mathematical induction, that S= n(n+1)/2

is not correct formula for the sum below.

1^3+2^3+3^3+4^3+…+n^3 = S

Give the correct formula for this sum.

(2)   [10 pts.]

Suppose Algorithm-1 does f(n) = n**2 + 4n steps in the worst case, and Algorithm-2 does g(n) = 14n + 39 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)?

(3)  [15 pts.]

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

(4)  [15 pts.]

Write out the algorithm (pseudocode) to find K in the ordered array by the method that compares K to every fifth entry until K itself or an entry larger than K is found, and then, in the latter case, searches for K among the preceding four. How many comparisons does your algorithm do in the worst case?

(5)  [25 pts.] 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 don’t 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)  [25 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: 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?