Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC236: Problem Set 2

Problem Set Instructions

Please read the following instructions carefully before starting the assignment.  They contain important infor- mation about expectations, requirements, exercise submission instructions, and reminders of both course and university policies.

Grading

• Your problem set is worth 13% of your final grade in this course, with the following distribution:

➔ 12% (of the overall 13%) is graded using the following breakdown:

80%  is allocated to correctness (these marks are noted in this document)

20%  is allocated to writing/communication (these marks follow the writing rubric)              By writing/communication, we expect clear and formally written proofs. Solutions which are techni- cally correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them.

➔ 1% (of the overall 13%) is graded based on your submission using our VoiceEx (Voice and Text Explanations) platform.  More details will follow once the system is online and operational – there will be a second handout with additional instructions (and a separate/different due date) once the plat- form is online and operational.

Requirements

Problem Sets, like everything else in this course, are to be completed individually.  This means that you are forbidden from communicating, working with, and discussing these problem sets with anyone (except for the CSC236 Teaching Team).  Please be aware of UofT’s Academic Integrity Policies.  Please refer to the course syllabusfor additional details on this and the “Minimum Standards for Submitted Work”

Submission

All submission are required to be written in LATEX.  We would strongly suggest using Overleaf as a means of compiling and editing LATEX documents. However, you may use other programs that help compile LATEX, but you are not permitted to use another word processor (e.g., Microsoft Word, Apple Pages, Google Docs, etc.).

All files are to be submitted using the MarkUs platform (https://markus108.utm.utoronto.ca/markus22f/courses).   You may submit as many times as you like, in fact you are encouraged to do so! If you have not used MarkUs be-   fore, give yourself plenty of time to figure it out, and ask for help if you need it! Please ensure your answers are typed and submissions is clearly legible/understandable. Your submissions should be written in English and communi-   cated clearly, free from spelling and grammatical errors.

The required files for this problem set are ps2 .pdf and ps2 .tex.

Policies

Late Submissions

Late Problem Sets will be deducted 15% per day of lateness.  After three (3) calendar days, the Problem Set will no longer be accepted. If you do not submit within the 3-day period (i.e., you have no submission) you get a ZERO (0%) for the entire Problem Set (i.e., you forfeit 13% of your grade).

Mismatching or Missing Files

You are required to submit the LATEX file that matches the corresponding PDF. If mismatched files or not both files are submitted, you will receive a ZERO (0%) for the entire Problem Set (i.e., you forfeit 13% of your grade). Furthermore, an administrative deductions will be applied if the teaching staff need to compile or recompile your submission. If you did not upload your file correctly (i.e., it is not readable) you will receive a ZERO.

Academic Integrity

Academic integrity is essential to the pursuit of learning and scholarship in a university, and ensuring that a degree from the University of Toronto Mississauga is a strong signal of each student’s individual academic achievement. As a result, UTM treats cases of cheating and plagiarism very seriously.  The University of Toronto’s Code of Behaviour on Academic Matters outlines behaviours that constitute academic dishonesty and the process for addressing academic offences. See the course syllabus and UofT polcies forfurther details.

Please note that this course will extensively verify that the work you submit is your own, this includes utilizing software, programs, and other resources at our disposal for plagiarism and collusion detection.

Problem Set Exercises

1. Turtle Tree [3 marks]

The following code draws the image on the right. Use a recurrence relation to count the number of branches in a tree of depth n. We are counting branches as one line in the tree.

from  turtle  import  *  #  imports  Turtle  graphics

rt(- 90)  #  turning  the  turtle  to  face  upwards

def  tree_drawing(size,  n):  #  tree  drawing  function

if  n  >  0:  #  base  case

fd(size)  #  drawing  the  line  with  length=size

rt(30)  #  right  turn  30  degree

tree_drawing(0 . 8  *  size,  n- 1)  #  recursive  call

lt(60)  #  left  turn  60  degrees

tree_drawing(0 . 8  *  size,  n- 1)  #  recursive  call

rt(30)  #  right  turn  30  degrees

fd(-size)  #  traverse  backwards  the  way  you  came

tree_drawing(80,  10)  #  tree  of  size  80  and  level  10

2. Roots Method Closed Form [7 marks]

This problem is an extension of Tutorial 5 Problem 2. Refer to this question and solution as a starting point. Consider the following recurrence relation:

L(1) = 1                                                                                                                (2)

L(n) = 2L (「l) + L (「l) 2L (「l) for n N, n 2.                          (3)

Using the method described in Tutorial 5, Problem 2, find a closed form for L(n) that is correct when n is a power of 3.

Hint: define a recurrence relation L\ (n) where L\ (n) = L(3n ).

Note:  you can prove that your closed form is correct using induction, however, this is not required for this question but is fundamentally important.

3. Book Stacking [8 marks]

You are trying to create a stack of books overhanging off a table. Each book has the same size and weight, and has a homogeneous mass. The length of each book is 1. You are attempting to stack them such that the horizontal distance from the edge of the table to the book at the top is maximized. Let’s call this distance 北n for a stack of n books.

In the case of n = 1 book, 北1  is clearly  . This is because the centre of mass is balanced, since half the book is on the table, and the other half is hanging off, so the book will stay put.

Now, consider the case with two books i.e., n  =  2.  You can see in the second drawing (below on the right) that if you count up the square units drawn on the book, there are a total of 4 units on the table, and 4 overhanging. Therefore, these two books would be balanced since their combined centre of mass* is aligned with the edge of the table. In this case, we can see that the total overhang distance 北2 is  .

*Think of the combined centre of mass as being a point along the 北-axis, where half the mass is on one side, and half the mass is on the other. There is no need to worry about the physics of this too much. Hope- fully the intuition from the first two examples make it clear. We will define Cn  as the x-coordinate of the combined centre of mass for n books. C1 and C2 are labelled on the 北-axis of the diagrams.

1

1

2

C

2

In this problem, you will define a recurrence relation of 北n+1 with respect to 北n . You will solve the recurrence to look for a“closed form”. The reason that this is in quotations is because you will find that the outcome is a sum which has no geometric closed form.

Consider the following diagram. We have n books stacked on the edge of the table such that 北n is a maxi- mum, and their combined centre of mass is Cn where Cn is lined up with the edge of the table.

Cn

北n

n books

Now suppose we add a book underneath the current stack (refer to the diagram below). Think of the new book being added as if it is replacing what was the table before. Since the books were stacked without falling before, we will align the centre of mass Cn  of the n books with the right edge of the (n + 1)th book. This maximizes the overhang 北n . The centre of mass Cn  of the previous n books has now shifted to the right ofthe table. Now, to ensure the new stack of books is stable, the centre of mass of all the n + 1 books together

Cn+1 must be aligned with the edge of the table.

Since we are trying to find a recursion of xn , we are interested in the difference between xn  and xn+1 , which is precisely the difference between Cn and Cn+1 .

Cn+1     Cn

(n + 1)th book

 n books

A. [3 marks] Find the recurrence relation of xn+1 . Remember to specify the base case.

Hint: recall that at stable equilibrium when adding the (n + 1)th book, the total weight times the centre of mass of the (n + 1) books should be equal to the weighted sum of Cn  and the centre of mass of the (n + 1)th book. w(n) is is the weight of n books. The formula to relate Cn and Cn+1 is as follows:

w(n + 1) ∗ Cn+1  = w(n) ∗ Cn + w(1) ∗ (centre of  mass of  (n + 1)th   book)            (4)

B. [3 marks] Solve the recurrence relation you defined in Part A., above. You will not find a closed form, leave your findings as a sum.

C. [2 marks] How many books would you need to stack such that the top book is completely overhung off the table?

4. Complexity Analysis of Recursive Program [10 marks]

Consider the program below and the description of each function. The main function is dec2bin which takes a string representation of a decimal number 北 and returns a string representation of 北 converted to binary.  All the functions above are helper functions used in dec2bin.  The functions karatsuba and

add_bin are not implemented since it is not relavent to the question, however their descriptions are present. The complexity of karatsuba is Θ(nlog23), and the complexity of add_bin is Θ(n).

In this question, you will use Master theorem to analyze the complexity of the functions p2b and dec2bin.

A. [3 marks] Analyze the function p2b to develop a recurrence relation for the worst-case time complexity

bound. Explain your reasoning by explaining the number of steps in each line of code. Note: any fact you use in this question must be proven.

B. [2 marks] Find the closed form for the complexity of p2b using Master theorem.

C. [3 marks] Use the complexity found in Part B., above, to develop a recurrence relation for the worst- case time complexity bound of the function dec2bin.  Explain your reasoning by explaining the number of steps in each line of code.

D. [2 marks] Finally, use Master Theorem to solve for the closed form of the complexity of dec2bin.

import  math

def  karatsuba(x:  str,  y:  str)  ->  str :

"""

param  x :  binary  string  representation  of  a  non-negative  integer param  y :  binary  string  representation  of  a  non-negative  integer

return :  binary  string  representation  of  x  *  y

>>>  karatsuba ('0b10 ','0b11 ')

'0b110 '

"""

def  add_bin(x:  str,  y:str)  ->  str :

"""

param  x :  binary  string  representation  of  a  non-negative  integer param  y :  binary  string  representation  of  a  non-negative  integer

return :  binary  string  representation  of  x  +  y

>>>  add_bin ('0b10 ','0b11 ')

'0b101 '

"""

def  p2b(n:  int)  ->  str :

"""

param  n :  integer  in  decimal  form ,  power  of  2

return :  binary  string  representation  of  10ˆn

>>>  p2b (2)

'0b1100100 '

"""

if  n  ==  1:

return  " 0b1010" 

x  =  p2b(math .floor(n/2))

y  =  p2b(math .ceil(n/2))

return  karatsuba(x,  y)

def  dec2bin(x:  str)  ->  str :

'''

param  x :  a  string  representation  of  a  decimal  integer ,  with  length  a  power of  2

return :  a  string  representation  of  x  converted  to  binary

>>>  dec2bin ("1234")

0b101111000110000101001110

'''

n  =  len (x)

if  n  ==  1:

return  str (bin (int (x)))

x  =  int (x)

half  =  n  /  2

left  =  int (x  //   (10  **  half))

right  =  int (x  %   (10  **  half))

a  =  dec2bin(str (left))

b  =  p2b(half)

left_half  =  karatsuba(a,  b)

right_half  =  dec2bin(str (right))

return  add_bin(left_half,  right_half)