2 Pages
Unlock Document

Computer Science
Nathalie Fournier

CSC165H1F Homework Assignment # 3 Fall 2011 Worth: 8% Due: By 10pm on Wednesday 7 December. Remember to write the full name, student number, and CDF/UTOR email address of each group member prominently on your submission. Please read and understand the policy on Collaboration given on the Course Information Sheet. Then, to protect yourself, list on the front of your submission every source of information you used to complete this homework (other than your own lecture and tutorial notes, and materials available directly on the course webpage). For example, indicate clearly the name of every student with whom you had discussions (other than group members), the title of every additional textbook you consulted, the source of every additional web document you used, etc. For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjusti▯ed, ambiguous, or vague claims in your solutions. [10] 1. Recall the following algorithm from Exercise 5. # Precondition: A is a non-empty list of integers (i.e., len(A) > 0) sorted in non-decreasing # order (i.e., A[0] 6 A[1] 6 ::: 6 A[len(A) ▯ 1]) and x is an integer that occurs in A # (i.e., 9i 2 f0;1;:::;len(A) ▯ 1g;A[i] = x). ▯rst 0 last len(A) ▯ 1 # Loop Invariant: 0 6 ▯rst 6 last < len(A) and x occurs in A[▯rst:::last] # (i.e., 9i 2 f▯rst;:::;lastg;A[i] = x). while ▯rst < last: midpoint b(▯rst + last)=2c if A[midpoint] < x: ▯rst midpoint + 1 else: last midpoint index ▯rst # Postcondition: 0 6 index < len(A) and A[index] = x. Write a detailed argument that the loop invariant is correct. (You may assume the results from Exercise 5, i.e., do not prove them again|just use them!) Note: Parts of this will involve working with the \ oor" function (b:::c). In your answer, you may use the properties of the oor function proved in the course notes (on page 41). [30] 2. For each algorithm below, ▯nd the simplest asymptotic bound possible on
More Less

Related notes for CSC165H1

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.