CSC 201-Discrete Math for Computer Scientists

Shai Simonson

Due: Thursday, October 19

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

Prove that 1^k + 2^k + 3^k + … + n^k is Ω(n^k+¹) and O(n^k+¹), for any fixed k>0. Hint: 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 x^k, from 0 to n.

(9/48 points) 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.

x² + x³ 3^x x! x/lgx x²+ 2^x xlgx 2^xlgx logx² 2^x+¹

lgx! lgx lnx 2^x x(1+2+…+ x) loglogx 2^2x x^x log²x

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) + ….
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.

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 = b_nb_n-₁…b₁b₀ be an arbitrary binary string of length n+1. Let Y = b_nb_n-₁…b₁ and Z = b_n-₁…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.
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.

a. The nth Fibonacci number equals (1/

√

5)[(1/2 +

√

5/2)ⁿ – (1/2 –

√

5/2)ⁿ ], where F₀ = 0 and F₁= 1 and F_n = F_n_-1 + F_n_-2

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

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?

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.
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. 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 n²plates in order.
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. You may assume that the numbers range in value from 0 to n-1 inclusive.