CSC 201-Discrete Math for Computer Scientists

Shai Simonson

Assignment 2

Due: midnight, Monday, October 23

From the text:  Section 3.2:   3, 4, 5, 8, 9, 10, 30.     Section 3.3:   13, 14, 15, 18.

  1. Prove that f(x) = x3 – 1000x2 + x – 1 is Ω(x3) and O(x3).
  1. Prove that 1k + 2k + 3k + … + nk is Ω(nk+1) and O(nk+1), for any fixed k>0Hint:  The Big-O part of this is straightforward using c = 1, and the Big-Omega part can be done by using c = 1/(k+ 1), and comparing the sum to the area under the curve xk, from 0 to n.
  1. 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.  This is a big problem and worth a number of points - make sure to justify every step.
  2. x2 + x3      3x      x!     x/lgx      x2+ 2x      xlog2x      2xlgx     logx2     2x+1 

    lgx!      lgx      lnx     2    x(1+2+…+ x)     loglogx      22x    xx  log2x

  3. Compute the sum of the infinite series below.
    1. 1 + 1/4 + 1/16 + 1/64 + …
    2. 1 + 2/4 + 3/16 + 4/64 + …
  4. 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.
  1. What’s wrong with the following proofs by induction?
    1. Every binary string contains identical symbols (either all 0's or all 1's). The proof is by induction on the size of the string. For n=0 all binary strings are empty and therefore identical. Let X = bnbn-1…b1b0 be an arbitrary binary string of length n+1. Let Y = bnbn-1…b1 and Z = bn-1…b1b0. 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).  That is, I add 3 five cent coins and subtract 2 seven cent coins.  And, I can do this because x is at least 2.  If y > 3, then since 3(7) – 4(5) = 1, n+1 = 7(x+3)+5(y–4). That is, I add 3 seven cent coins and subtract 4 five cent coins, which is doable because y is at least 4.  In either case, we showed that n+1 = 7u + 5v where u and v are non-negative integers.

  2. Prove by induction on n that:
    1. a.   The nth Fibonacci number equals (1/5)[(1/2 + 5/2)n – (1/2 – 5/2)n ], where F0 = 0 and F1 = 1 and Fn = Fn-1 + Fn-2

      b.   The sum of the geometric series 1 + a + a2 + … + an equals (1–an+1)/(1–a), where a does not equal one.

      c.    21 divides 4n+1 + 5 2n-1

  3. 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 n2. We sort the cards by placing a set of n2 plates numbered from 1 to n2 on a table. Then one by one, place each card on top of the numbered plate equal to it on the desk. You can assume that it takes a single step to find a card's pile - as though the card is the index to an array, and the slot in the array is the pile.  The sorted list can be extracted by looking through the piles of the n2 plates in order.
    3. The method in part (b)can be improved to work in linear time. Explain how. Hint: This is not easy. Use only n plates, numbered 0 through n - 1 and turn each number into a pair of numbers, each with a value between 0 and n-1.