Question Details

(Solved) Need help with question 3 ONLY. Need full, detailed solution.


Need help with question 3 ONLY.

Need full, detailed solution. Thanks


CSC236H, Winter 2016

 

Assignment 4

 

Due March 25th, 11:59 p.m.

 

? You may work in groups of no more than two students, and you should produce a single solution in a

 

PDF ?le named a4.pdf, submitted to MarkUs. Submissions must be typed.

 

? Please refer to the course information sheet for the late submission policy.

 


 

1. Consider the following code.

 

Precondition: a ? R and b ? N.

 


 

1.

 

2.

 

3.

 

4.

 

5.

 

6.

 

7.

 

8.

 


 

def rec exp(a, b):

 

if b == 0:

 

return 1

 

else if b mod 2 == 0:

 

x = rec exp(a, b/2)

 

return x ? x

 

else:

 

x = rec exp(a, (b ? 1)/2)

 

return x ? x ? a

 


 

State a postcondition for this algorithm (your postcondition must involve exponentiation). Then, prove

 

that the algorithm is correct with respect to your speci?cation.

 

2. Consider the following algorithm.

 

Precondition: a, b ? N, and b > 0.

 

Postcondition: a = b ? q + r and q ? 0 and 0 ? r < b.

 


 

1.

 

2.

 

3.

 

4.

 

5.

 

6.

 


 

def Div(a, b):

 

q=0

 

r=a

 

while r ? b:

 

q =q+1

 

r =r?b

 

return [q, r]

 


 

(a) Give an appropriate loop invariant for the purpose of proving both partial correctness and termination for the above program with respect to its given speci?cation.

 

(Hint: your loop invariant should relate a, b, q, and r).

 

(b) Give a formal proof of the partial correctness of Div with respect to the given speci?cation.

 

(c) Give a formal proof of termination of Div.

 

1

 


 

3. Recall that a point p in the plane can be given by a pair of numbers (a, b) where a is the x-coordinate

 

and b is the y-coordinate. For any two such points p given by (p1 , p2 ), and q given by (q1 , q2 ), one can

 

calculate the distance between p and q by various formulas. In the following exercise you may assume

 

that the function Distance(p, q) terminates and returns the distance between any two points p, q, each

 

given as a tuple of numbers.

 

Write a detailed proof of correctness for the following algorithm.

 

Precondition: A is a list of tuples of integers, and len(A) ? 2, and 1 ? e < len(A).

 

Postcondition: Returns a pair of points in A[0 : e + 1] with minimal distance.

 


 

1.

 

2.

 

3.

 

4.

 

5.

 

6.

 

7.

 

8.

 

9.

 

10.

 

11.

 

12.

 


 

def F ind Closest P air Rec(A, e):

 

if e == 1:

 

return (A[0],A[1])

 

(p, q) = F ind Closest P air Rec(A, e ? 1)

 

min = Distance(p, q)

 

i=0

 

while i < e:

 

if Distance(A[e], A[i]) < min:

 

min = Distance(A[e], A[i])

 

p = A[e]

 

q = A[i]

 

i=i+1

 

return (p, q)

 


 

2

 


 

 


Solution details:

Pay using PayPal (No PayPal account Required) or your credit card . All your purchases are securely protected by .
SiteLock

About this Question

STATUS

Answered

QUALITY

Approved

DATE ANSWERED

Oct 15, 2019

EXPERT

Tutor

ANSWER RATING

YES, THIS IS LEGAL

We have top-notch tutors who can do your essay/homework for you at a reasonable cost and then you can simply use that essay as a template to build your own arguments.

You can also use these solutions:

  • As a reference for in-depth understanding of the subject.
  • As a source of ideas / reasoning for your own research (if properly referenced)
  • For editing and paraphrasing (check your institution's definition of plagiarism and recommended paraphrase).
This we believe is a better way of understanding a problem and makes use of the efficiency of time of the student.

NEW ASSIGNMENT HELP?

Order New Solution. Quick Turnaround

Click on the button below in order to Order for a New, Original and High-Quality Essay Solutions. New orders are original solutions and precise to your writing instruction requirements. Place a New Order using the button below.

WE GUARANTEE, THAT YOUR PAPER WILL BE WRITTEN FROM SCRATCH AND WITHIN A DEADLINE.

Order Now