Algorithms Answers

Prove the following using mathematical induction:
1. (ab)n = an bn for every natural number n
2. 13 +23+33+…+n3 = (1+2+3+…+n)2
3. 1+3+5+7+…+(2n-1) = n2

Prove that n + log2n = O(n) by showing that there exists a constant c > 0 such that n + log2n ≤ cn.
(note that log2n means (log n)2.)

1. Prove that n + log n = O(n) by showing that there exists a constant c > 0 such that n + log n ≤ cn.

Read 10 integers from the keyboard in the range 0 -100, and count how many of them are larger than 50, and display this result.

Divide 1161 by 31 both are octal numbers

Write a pseudocode version of the factorial function . . .

(a) iteratively.

(b) recursively.

Using pseudo code, write a program that works out the price of a garden hose for a user defined length in m (£1.56 per metre)

Write a pseudocode algorithm to compute the product of the first n positive integers. How many multiplications does your algorithm perform?

Solve the following recurrence relation (without using Master Theorem)
C(n) = C(n/2) + logn, for n > 1. C(1) = 0

Consider an array of prime integers in the range [1...20] with the entries randomly distributed. Find the average number of comparisons for a sequential search in the array.