You may work in a group of up to 2 students (i.e. you may work with up to 1 other students in the course, from any section).  For each question indicate the name of the (main) author and the proofreader.  Each of these roles, of course, gets the same credit.

Your solutions must be typed using a word processing tool such as Google Documents, MS Word, or LATEX, and produce a PDF document ps1.pdf, which you submit to Markus at https://markus.teach.cs. toronto.edu/2022-09/courses. Handwritten, then scanned, submissions will receive a grade of zero.

Any proofs you devise must be clear to the reader, without expecting them to fill in details in your steps. In particular, any proof by induction must make clear:  where you establish your base case(s), where you assume your inductive hypothesis, any bounds on variables, and where you use your inductive hypothesis and those bounds.

1.  Read function split in split .py. You may assume that its post-condition follows from its precondition, when it is called. You may also assume that its worst case run-time complexity is (n), where ❥A❥ = n. Now read function ith_element.

(a)  Prove that ith_element’s post-condition follows from its precondition when it is run.

(b)  Prove that there is at least 50% probability that if split is called on array A with n elements, both A[0 : less] and A[more :] have no more than 3n=4 elements.

(c)  Use part (b) to prove that the expected number of calls to split until ith_element is called on an array of no more than 3n=4 elements is no more than a constant with respect to n.  Hint:   The notion of Bernoulli trials is helpful here.

(d)  Use (c) to form a recurrence for the expected run-time, T(n), of ith_element on an array of size

n. Then use the Master Theorem to deduce the asymptotic expected run-time class.

2.  GutSend (aka GS) contracts drivers to pickup and deliver fast food orders. They want you to produce software to keep track of the details. They need you to design:

GS-add(new-driver):  Add a new driver with an initially empty list of deliveries to GS’s contractors. Return a unique identifier driver-ID

GS-schedule(order-ID, current-time):  Add  order-ID  and the  current-time  (the time GS-schedule is executed) to the list of deliveries for the driver with a shortest list.  If there are two or more drivers with a shortest list, arbitrarily add the order to one of them.  Return the driver-ID of the driver contracted to deliver this order.

GS-next(driver-ID):  Remove the order with the earliest current-time recorded from driver-ID’s list. Again, for ties arbitrarily choose one. Return the removed order’s order-ID.