CSC165H1: Problem Set 3

CSC165H1 Problem Set 3
CSC165H1: Problem Set 3
 
General instructions
Please read the following instructions carefully before starting the problem set. They contain important
information about general problem set expectations, problem set submission instructions, and reminders
of course policies.
? Your problem sets are graded on both correctness and clarity of communication. Solutions which
are technically correct but poorly written will not receive full marks. Please read over your solutions
carefully before submitting them. Proofs should have headers and bodies in the form described in
the course note.
? Each problem set may be completed in groups of up to three. If you are working in a group for this
problem set, please consult https://github.com/MarkUsProject/Markus/wiki/Student_Groups
for a brief explanation of how to create a group on MarkUs.
Exception: Problem Sets 0 and 1 must be completed individually.
? Solutions must be typeset electronically, and submitted as a PDF with the correct ?lename. Handwritten submissions will receive a grade of ZERO.
The required ?lename for this problem set is problem set3.pdf.
? Problem sets must be submitted online through MarkUs. If you haven't used MarkUs before, give
yourself plenty of time to ?gure it out, and ask for help if you need it! If you are working with a
partner, you must form a group on MarkUs, and make one submission per group. \I didn't know
how to use MarkUs" is not a valid excuse for submitting late work.
? Your submitted ?le should not be larger than 9MB. This may happen if you are using a word
processing software like Microsoft Word; if it does, you should look into PDF compression tools to
make your PDF smaller, although please make sure that your PDF is still legible before submitting!
? The work you submit for credit must be your own; you may not refer to or copy from the work of
other groups, or external sources like websites or textbooks. You may, however, refer to any text
from the Course Notes (or posted lecture notes), except when explicitly asked not to.
Additional instructions
? For each proof, clearly de?ne the predicate (P(n)) that is relevant for your proof.
? You may not use forms of induction we have not covered in lecture.
? Please follow the same guidelines as Problem Set 2 for all proofs.
1. [12 marks] extend some results...
Page 1/3
CSC165H1, Fall 2017 Problem Set 3
Definition 1 (sequence an, S). Let a : N 7! Z. Denote a(n) = an, and a is identi?ed with the sequence
a0; a1; a2; :::. Let S = ff j f : N 7! Zg be the set of integer sequences.
(a) [3 marks] Use induction on n to prove that if m is some non-zero integer, and a; b 2 S are arbitrary
integer sequences, and n is an arbitrary natural number greater than 0, then

8k ? n; ak ? bk (mod m)
?
)
k
Y=n
k=0
ak ?
k
Y=n
k=0
bk (mod m)
Hint: You may assume 2.18(c) from the course notes as a starting point.
(b) [3 marks] Use induction on n to prove that if d 2 N, d 1, and b is an integer sequence with bm 0
for all natural numbers m, and n is an arbitrary natural number, then

8i 2 N; i ? n ) gcd(d; bi) = 1?
) d -
i
Y=n
i=0
bi
Hint: You may assume 2(g) from problem set 2 as a starting point.
(c) [3 marks] Consider the sums
1
2 + 1
+
1
2 2
=
14
24

13
24
1
3 + 1
+
1
3 + 2
+
1
2 3
=
37
60

13
24
Use induction to prove that for all natural numbers n, if n 1 then:
j
X
=2n
j=n+1
1
j

13
24
(d) [3 marks] De?ne integer sequence c 2 S by
cn =
8
<
:
0; if n = 0
cn1 + 3n
2 3n + 1; if n 0
Use induction on n to prove that for all n 2 N; cn = n
3
.
2. [8 marks] Counting subsets
(a) [3 marks]
Definition 2 (

n
k
!
). Let n; k 2 N, k ? n, and S be a set with jSj = n. Then
n
k
!
denotes the number
of subsets S of size k.
Use induction on n to prove
8n; k 2 N; k ? n )

n
k
!
=
n!
k!(n k)!
Hint:

Notice that no induction is required when k = 0 or k = n, and look for a connection between
n + 1
k
!
and both
n
k
!
and
n
k 1
!
. This approach requires you to introduce k after n. AntiHint: You may not use results from combinatorics such as the Binomial Theorem, since they are,
essentially, what you are proving.
Pa
CSC165H1, Fall 2017 Problem Set 3
Definition 3 (Sn). Let n 2 N. De?ne Sn = f1; 2; : : : ; ng
Definition 4 (DT Pn). Let n 2 N. De?ne the set of disjoint two-set partitions of Sn as follows:
DT Pn =
?
fA; Bg j A; B ? Sn and A [ B = Sn and A \ B = ;

Notice that DT P0 =
?
f;; ;g
and DT P1 =
?
ff1g; ;g
.
(b) [2 marks] Write out all the elements of DT P2 and DT P3 explicitly.
(c) [3 marks] Find a closed-form expression for jDT Pnj in terms of n. Use induction on n to prove your
formula correct.
3. [11 marks] asymptotics
(a) [3 marks] Use the de?nition of big-Theta from the course notes to prove Theorem 5.8.
(b) [3 marks] Use the de?nition of big-Oh from the course notes to prove that for all a; b 2 R
+

b a ^ a 1
?
) b
n
62 O(a
n
)
You may not use limits or other techniques of calculus.
(c) [5 marks] Read over function xgcd, which calculates the extended gcd(n, m), below:
1 def xgcd(n, m):
2 s1, s0, t1, t0, r1, r0 = 0, 1, 1, 0, m, n
3 while r1 != 0:
4 quotient = r0 // r1
5 r0, r1 = r1, r0 - quotient * r1
6 s0, s1 = s1, s0 - quotient * s1
7 t0, t1 = t1, t0 - quotient * t1
8 return (r0, s0, t0)
Let the input size be n. Assume that the loop body, lines 4{7, is 1 \step". Prove that the runtime
of xgcd, RTxgcd 2 O(lg n). Hint: Can you show that every two iterations of the loop reduces r0 by
at least half?
Page 3/