What is a closed form for the sum 1 + 2 + 3 + ... + n? That is, express this sum as a function of n using standard arithmetic operators. Answer
What is a closed form for ∑nk=1(k + 3)? Answer
What is the value of sum 1 + 2/3 + 4/9 + 8/27 + ... ? (The sum is infinite, and each term is 2/3 of the previous term.) Answer
What is the value of sum 3/4 + 9/16 + 27/64 + ... ? (The sum is infinite, and each term is 3/4 of the previous term.) Be careful. The sum does not start with 1. Answer
Suppose that f(n) = 2n2 + n. Which of the following are true, and which are false?
A median of a list of n numbers is defined to be a value x in the list such that at least n/2 values in the list are ≤ x, and at least n/2 values in the list are ≥ x. (Note that at least one value in the list is ≤ x, since x is in the list.) Describe an algorithm that finds a median of a list in time O(nlg(n)). Answer
To within a constant factor, what is a solution to recurrence T(n) = 2T(n/4) + 1? Answer
To within a constant factor, what is a solution to recurrence T(n) = 4T(n/2) + 1? Answer
To within a constant factor, what is a solution to recurrence T(n) = 2T(n/4) + n? Answer
To within a constant factor, what is a solution to recurrence T(n) = 4T(n/2) + n2? Answer