CSI 403 – Data Structures and Algorithms – Spring 2019 Homework – I
Date given: Jan. 23, 2019
1. Given below are several pairs of functions f(n) and g(n). For each pair, find lim f(n). Show
Due date: Feb. 1, 2019 n→∞ g(n)
work. For some of these, you may need to use L’Hospital’s rule. (20 points)
(a) f(n) = 15n2 and g(n) = 5.
(b)f(n)=2n andg(n)=n2.
(c) f (n) = n ln n and g(n) = 17n2 + 4. (Note that “ln” denotes the natural logarithm.) (d)f(n)=3n andg(n)=2n.
2. (a) Use induction on n to prove that for all integers n ≥ 0, the value 4n + 1 is not divisible by 3. (20 points)
(b) Consider the infinite sequence of integers f0, f1, f2, …, defined by f0 = 1, f1 = 2 and 3n
fn =fn−1+fn−2 foralln≥2. Useinductiononntoprovethatfn> 2 forall n ≥ 1. (20 points)
3. Let A = {x,y,z,w} and let B = {1,2,3}. Determine the number of functions from A to B that are neither one-to-one nor map y to 3. Show work. (20 points)
Hint: Use the principle of inclusion-exclusion.
4. Let A = {x1, x2, . . . , x10} be a set of 10 positive integers, not necessarily distinct, such that xi ≤ 10, 1 ≤ i ≤ 10. Prove that there are at least two different 5-element subsets S1 and S2 of A such that the sum of the elements in S1 is equal to the sum of the elements in S2.
(20 points)
Hint: Use the pigeonhole principle.