Due: Friday October 19

Warning:  Some of the math symbols on this page do not appear correctly using Netscape/Mozilla.

From the text:  3.2:   3, 4, 5, 8, 9, 10, 24     3.3:   7, 8, 9, 10

1. Prove that f(x) = x³ – 1000x² + x – 1 is W (x³) and O(x³).
2. Prove that 1^k + 2^k + 3^k + … + n^k is W(n^k+1) and O(n^k+1), for any fixed k>0.
3. Order the following functions in order of their growth rate. If f(x) is O(g(x)), but g(x) is not O(f(x)), then put f(x) above g(x). If they are each big-O of each other, then place them on the same level.  Beware:  some of these are easy to compare and some are not.

 

 
 
 

x² + x³      3^x      x!     x/log₂x      x²+ 2^x      xlog₂x      2^xlogx     logx²

log₂x!      log₂x      lnx     2^x     x(1+2+…+ x)     loglogx      2^{x^2}     log²x

4. Compute the sum of the infinite series below.
1. 1 + 1/4 + 1/16 + 1/64 + …
2. 1 + 2/4 + 3/16 + 4/64 + …
5. Telescoping Series.
1. Using the identity 1/((k)(k+1)) = 1/k – 1/(k+1), find the value of the infinite sum 1/(1*2) + 1/(2*3) + 1/(3*4) + ….
2. The nth triangle number is defined to be the sum of the first n positive integers. What is the value of the infinite sum of the reciprocals of the triangle numbers.
6. What’s wrong with the following proofs by induction?
1. Every binary string contains identical symbols. The proof is by induction on the size of the string. For n=0 all binary strings are empty and therefore identical. Let X = b_nb_n-1…b₁b₀ be an arbitrary binary string of length n+1. Let Y = b_nb_n-1…b₁ and Z = b_n-1…b₁b₀. Since both Y and Z are strings of length less than n+1, by induction each contains identical symbols. Since the two strings overlap, X must also contain identical symbols.
2. Any amount of change greater than or equal to twenty can be gotten with a combination of five cent and seven cent coins. The proof is by induction on the amount of change. For twenty cents use four five-cent coins. Let n > 20 be the amount of change. Assume that n = 7x + 5y for some non-negative integers x and y. For any n > 20, either x > 1, or y > 3.If x > 1, then since 3(5) – 2(7) = 1, n+1 = 5(y+3)+7(x–2). If y > 3, then since 3(7) – 4(5) = 1, n+1 = 7(x+3)+5(y–4). In either case, we showed that n+1 = 7u + 5v where u and v are non-negative integers.
7. Prove by induction that:
a.   The nth Fibonacci number equals (1/Ö 5)[(1/2 + Ö 5/2)ⁿ – (1/2 – Ö 5/2)ⁿ ], where F₀ = 0 and F₁ = 1.

b.   The sum of the geometric series 1 + a + a² + … + aⁿ equals (1–aⁿ⁺¹)/(1–a), where a does not equal one.

c.    21 divides 4ⁿ⁺¹ + 5 ^2n-1

8. Counting each arithmetic calculation or comparison, extraction or exchange of a card as one operation, what is the worst-case order of growth of an algorithm that sorts numbered cards in the following way?
1. Find the largest valued card in the deck by shuffling through one card at a time extracting a card if it is the largest one seen so far, and swapping the previously largest card back into the deck. When the largest has been found, place this card face down in a new pile and repeat the previous process until no cards in the original pile are left. Explain your answer.
2. This time we assume that the largest number on any of the n cards is n². We sort the cards by placing a set of n² plates numbered from 1 to n² on a table. Then one by one, place each card on top of the numbered plate equal to it on the desk. The sorted list can be extracted by looking through the piles on all n² plates in order.
3. This method can be improved to work in linear time. Explain how. Hint: This is not easy. Use division, to try turn each number into a pair of numbers, each with a value between 1 and n.
back
 

---

shai@stonehill.edu

http://www.stonehill.edu/compsci/shai.htm