Homework 1 Permutations and Combinations

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/n?n
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
UofToronto–ECE 345–Fall, 2020 3 Homework 1
5. [Probability, 10 points]
During a committee election, a person places their vote on 3 of 20 candidiates. Assume that
all candidate have equal chance to be selected into the committee. At the end of the election,
5 of the candidate will form the committee. What is the probability that at least one of the
candidates elected by this person will be on the committee?
6. [Proof by contradiction, 10 points] Assume you are in the final round of a quiz contest, and
the final True or False question is so extremely difficult that you have no clue which one of the
two choices is correct. There are two people who know the answer that you can potentially get
help from. However, one of them always lies and the other always tells the truth. You cannot
distinguish which one is the liar. You are allowed to ask one question to one of the potential
helpers, without knowing which one you are talking to. Come up with the single question you
will ask the helper, and decide which answer you will choose based on their response. Use a
proof by contradiction to show your strategy is indeed correct. Make sure to show clearly all
the steps of the proof to receive full credit.
7. [Trees, 10 points]
George has a 26-node binary tree, with each node labeled by a unique letter of the alphabet.
The preorder and postorder sequences of nodes are as follows:
preorder: o v e f g t l s d n x a y u m k p j i c w b z h q r
postorder: t s l g f e n u m y a k x d v j z b h w c r q i p o
Draw George’s binary tree.