Important note: When writing your solutions, you must follow the guidelines below.
• The answers should be concise, clear and neat.
• When presenting proofs, every step should be justified.
• Assignments should be stapled or placed in an unsealed envelope.
• All questions carry equal marks.
Substantial departures from the above guidelines will not be graded.
Question 1: On the first page of your assignment, write your name, student number, and
course number COMP 2804.
Question 2: A small computer network consists of 6 computers. Each computer is directly
connected to 0 or more computers. Show that there are at least two computers in the network
that are directly connected to the same number of other computers. Is the statement true if
we have 10 computers instead of 6?
Question 3: Show that an = n
2 + n + 1 satisfies
(
a0 = 1
ak = ak?1 + 2k for k > 0.
(1)
Question 4: Consider the following recursive function defined for positive values of n
M(n) = (
n ? 10 if n > 100
M(M(n + 11)) if n ? 100 (2)
Evaluate M(120), M(111), M(97), M(94). Do you observe something interesting for the
value of M(n) for n ? 100?
1
Question 5: Let dn denote the number of ways that n-letters can be put into n-envelopes
so that no letter goes into the correct envelope. Show that d1 = 0, d2 = 1, d3 = 2, and in
general for n ? 3,
dn = (n ? 1)(dn?1 + dn?2).
Question 6: Using induction for n ? 1, show that dn in the previous question can be
expressed as
dn = n!
1
0! ?
1
1! +
1
2! ?
1
3! +
1
4! + · · · + (?1)n
1
n!

.
Question 7: Exercise 4.36 from the Course Text Book by Michiel Smid.
Question 8: Give a recursive definition of the set of integers that are multiples of 3. Show
that your definition indeed generates all the elements of the set {. . . , ?9, ?6, ?3, 0, 3, 6, 9, . . .}.
Question 9: Show that
an =
1 ? r
n+1
1 ? r
, r 6= 1
satisfies the recurrence relation
(
a0 = 1
ak = ak?1 + r
k
for k > 0.
(3)
Question 10: A binary tree is
– either one single node
– or a node whose left subtree is a binary tee and whose right subtree is a binary tree.
Show that any binary tree with n leaves has exactly 2n ? 1 nodes.
Question 11: (Bonus Problem:) Assume you have a set A = {a1, a2, . . . , an+1} of n + 1
positive numbers such that Pn+1
i=1 ai = 2n. Prove or disprove that for any integer k, where
1 ? k ? 2n, we can always find a subset B ? A such that the sum of elements of B equals
k.
2

ScholarMatic: Explanation & Answer

Your ready answer from a verified tutor is just a click away for as little as $14.99

---

  

Click Order Now to get 100% Original Answer Customized to your instructions!