Homework 1 ECE 345 Algorithms and Data Structures

ECE 345– Homework 1
Homework 1
ECE 345 Algorithms and Data Structures

This homework is designed so you can practice your background in introductory discrete mathematics and combinatorics. You need to have this background material practiced well because future
homeworks will use it extensively!
• All page numbers are from 2009 edition of Cormen, Leiserson, Rivest and Stein.
• For each algorithm you asked to design you should give a detailed description of the idea,
proof of algorithm correctness, termination, analysis of time and space complexity. If not,
your answer will be incomplete and you will miss credit. You are allowed to refer to pages in
the textbook.
• Do not write C code! When asked to describe an algorithm give analytical pseudocode.
• Read the handout with the instructions on how to submit your Homework online.
Failure to adhere to those instructions may disqualify you and you may receive a
mark of zero on your HW.
• Write clearly, if we cannot understand what you write you may not get credit for the question.
Be as formal as possible in your answers. Don’t forget to include your name(s) and student
number(s) on the front page!
• No Junk Clause: For any question, if you don’t know the answer, you may write “I DON’T
KNOW” in order to receive 20% of the marks.
1. [Permutations and Combinations, 10+10 points]
(a) Give a combinatorial argument to prove that
Xn
i=0

n
i

4
i = 5n
.
(b) For integers n and k where n > k ≥ 1, give a combinatorial argument to prove that:
Xn
i=k

i
k

=

n + 1
k + 1
Hint: consider counting subsets of {1, . . . , n + 1}. How many such subsets have (i + 1) as
their largest element?
UofToronto–ECE 345–Fall, 2020 2 Homework 1
2. [Recurrences, 15 points]
Solve the following recurrences by giving tight Θ-notation bounds. (Hint: apply the Master
Theorem on the first three.)
(a) T(n) = 3T(n/4) + n!
(b) T(n) = 6T(n/3) + n
2
log n
(c) T(n) = T(n/3) + T(2n/3) + Θ(n)
3. [Asymptotics, 25 points]
Sort the following 24 functions from asymptotically smallest to asymptotically largest, indicating ties if there are any. You do not need to turn in proofs, but you should do them anyway
just for practice.
n
4.5 − (n − 2)4.5 n n1+(1/ log n)
log∗
(n/2) Pn
i=1 log i
Pn
i=2 
1
i−1 −
1
i+1
+ 2 log∗
(log∗ n) 2n
(log n)
log∗ n n
5
log∗
2
n 2
log∗ n
e
n
blog log(n!)c

1 − log 1
1−1/nn
n
(log log n)/(log n)
(log n)
(n/2) (log n)
log n

1 + 1
200n

200n
n
1/ log log n n
log log n
log(200) n log2 n n(log n)
2
To simplify notation, write f(n)  g(n) to mean f(n) = o(g(n)) and f(n) ≡ g(n) to mean
f(n) = Θ(g(n)). For example, the functions n
2
, n,

n
2


, n
3
could be sorted either as n  n
2 ≡

n
2


 n
3 or as n 

n
2


≡ n
2  n
3
.
4. [Induction, 5+5 points]
Use induction to prove the following statements. Make sure to show clearly all three steps of
induction (inductive basis, inductive hypothesis and inductive step) or you will miss credit.
(a)
Fn =
φ
n − ψ
n
φ − ψ
where Fn is the n
th Fibonacci number. The Fibonacci numbers are defined recursively by
Fn =



1 , n = 1
1 , n = 2
Fn−2 + Fn−1 , otherwise
and
φ =
1 + √
5
2
, ψ =
1 −
√
5
2
for all positive integers n.
(b) If A1, A2, . . . , An and B1, B2, . . . , Bn are sets such that Ai ⊆ Bi for i = 1, 2, . . . , n, then,
A1 ∪ A2 ∪ . . . ∪ An ⊆ B1 ∪ B2 ∪ . . . ∪ Bn
for all positive integer