数学代写 CSC165H1: Problem Set 3

CSC165H1, Fall 2018 Problem Set 3

General instructions

CSC165H1: Problem Set 3

Due Friday November 2 2018 before 10pm

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 that are technically correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them.
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. Note: Problem Set 0 must be completed individually.
Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Hand- written submissions will receive a grade of ZERO.
The required filename 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 figure 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.
Yoursubmittedfileshouldnotbelargerthan9MB.Thismayhappenifyouareusingwordprocessing software like Microsoft Word; if it is, you should look into PDF compression tools to make your PDF smaller, although please make sure that your PDF is still legible before submitting! Note: Problem Set 0 must be completed using LATEX.
Submissions must be made before the due date on MarkUs. You may use grace tokens to extend the
deadline; please see the Problem Set page on the course website for details on using grace tokens.
The work you submit must be that of your group; 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 specific to this Problem Set

For each proof by induction, clearly define the predicate (P(n)) that is relevant for your induction proof, so that you’re proving a statement with structure ∀n ∈ N, P (n) or ∀n ∈ N, n ≥ ⇒ P (n).
Always label the steps that use the induction hypothesis.
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.

Page 1/5

CSC165H1, Fall 2018 Problem Set 3

1. [6 marks] Pascal’s Triangle You may have learned that the number of ways you can choose k different n 􏰀n􏰁

items from a set of n items is often labelled nCk or, equivalently, Ck or k . In this question, you will prove some facts about Pascal’s triangle.

(See https://en.wikipedia.org/wiki/Pascal%27s_triangle for interesting background information.) The only facts you may use in your proofs in this question are:

+ 􏰀n−1􏰁 􏰀n−1􏰁 􏰀n􏰁
• ∀k∈N,∀n∈Z ,n≥k⇒ k−1 + k = k (calledPascal’sidentity)

􏰀n􏰁 •∀n∈N, n =1.

􏰀n􏰁
• ∀k,n∈Z,k<0∨k>n⇒ k =0.

􏰀n􏰁 n!
You may not use the formula k = (n − k)!k! or any other external results that you may know.

(a) [3 marks] Prove using induction that the sum of the values in the row with index n of Pascal’s triangle is 2n. The first row has index 0. That is, prove:

􏰄n 􏰀 n 􏰁 n

k =2.

􏰄n 􏰀 i 􏰁 􏰀 n + 1 􏰁

k = k+1.

∀n∈N,

(b) [3 marks] Prove using induction on n that: ∀k,n∈N,n≥k⇒

k=0

i=k

Page 2/5

CSC165H1, Fall 2018 Problem Set 3

2. [9 marks] Binary Representation of Fractions In this question, we use the notation (x)2 to refer to a binary representation of a number x. For example, 9 = (1001)2, where 9 is the decimal representation of the number nine.

Let Q(0,1) = 􏰆m |m,n∈Z+ ∧n>m􏰇 be the set of all rational numbers between 0 and 1 (exclusive). n

For any x ∈ Q(0,1), its binary representation is of the form:
x = (0.b1b2b3 …)2

where ∀i ∈ Z+,bi ∈ {0,1}, and x = 􏰄∞ bi . The binary digits bi are called bits. i=1 2i

Note that when there are trailing zeros, one may choose not to write them. For example, 3 = (0.11)2. 4

Some rational numbers, however, may not have a finite binary representation. You are familiar with this

situation from decimal, where 1 = 0.16666… does not terminate. 6

We say that x = (0.b1b2b3 . . . )2 has a finite binary representation if and only if ∃n ∈ Z+, x = (0.b1b2b3 . . . bn)2, where bi ∈ {0, 1}.

(a) [1 mark] What is the binary representation of 21? Give the answer that uses the fewest bits. (Hint:

it has a finite binary representation.)

(b) [4 marks] Prove that 1 does not have a finite binary representation. 10

some positive integers p and q.

Page 3/5

CSC165H1, Fall 2018 Problem Set 3

3. [8 marks] Definitions of Asymptotic Notation. Using only the formal definitions of O, Ω and Θ, prove the following statements. You may not use other relationships that you have learned about O, Ω and Θ.

(a) [2 (b) [2 (c) [2 (d) [2

marks] 17n4 − 21n3 + 6n − 135 ∈ Θ(n4) marks] 2n − n2 ∈ Ω(2n)
marks] log2 n − log10n ∈ Ω(log12n) marks] ∀k ∈ N,nn ̸∈ O(kn)

Page 4/5

CSC165H1, Fall 2018 Problem Set 3

4. [13 marks] Properties of Asymptotic Notation. Prove or disprove the following statements. Assume all functions referred to in this question have domain N and range R≥0.

(a) [2 marks] If f(n) ∈ Ω(g(n)), then g(n) ∈ O(f(n)).
(b) [2 marks] If f(n) + g(n) ∈ O(h(n)), then f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)).
(c) [3 marks] If f(n) + g(n) ∈ Ω(h(n)), then f(n) ∈ Ω(h(n)) or g(n) ∈ Ω(h(n)).
(d) [3 marks] If f(n) + h(n) ∈ Θ(g(n) + h(n)), then f(n) ∈ Θ(g(n)).
(e) [3 marks] If f(n) is non-decreasing and f(n) = n2 for odd n’s (but we do not know the values of f(n) for even n’s), then f(n) ∈ Θ(n2).

Page 5/5

Related Posts