(Q1) [10 pts.] Problem 1.14 from the Baases 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.

(Q2) [10 pts.] Problem 1.27 from the Baases textbook, page 64: Suppose Algorithm-1 does f(n) = n2 + 4n steps in the worst case, and Algorithm-2 does g(n) = 29n + 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)?

(Q3) [10 pts.] Problem 1.40 from the Baases textbook, page 65: Prove or disprove: SUM{i2} [where i changes from i=1 to i=n] (n2).

(Q4) [10 pts.] Problem 1.41 from the Baases textbook, page 65: Write out the algorithm to find K in the ordered array by the method suggested in the text (Section 1.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?

(Q5) [20 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:

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?

(Q6) [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.4 on pages 112-113 of the Baases text.

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

(Q7) [20 pts.] Let A1 = event odd number on first die; A2 = event odd number on second die; A3 = event odd total on both die. Show that the following three events are independent: {A1,A2} {A2,A3} {A1,A3} Show that the fourth event {A1,A2,A3} is NOT independent.