Due Saturday, June 17 (11:59 p.m.)

Instructions

• Answer each question on a separate page.

• Submit your homework as a single pdf file to Gradescope. It can be either a scanned copy of your written solutions or photos joined into a pdf; your solution should be readable. You are also encouraged to typeset the solutions in TEX or MS Word. Gradescope will ask you to mark where each answer is - please make sure to do this - points will be deducted otherwise.

•  For each question where you are required to design an algorithm, you need to clearly explain the algorithm and prove the running time complexity as asked in the question.

• You are encouraged to discuss with your peers/consult supplementary material if neces- sary, but the final written solutions must be your own.

–  For each solution that you discussed or looked at extra materials for hints, you are required to mention it in your solution. This will not incur any penalty, but if noticed otherwise by the graders it may bright into question your academic integrity and there will be more serious repercussions. Writing down solutions or answers from some source without citing the source or without understanding how what you have written is correct is cheating and will be treated as such.

Question 0: List all your collaborators and sources: (–∞ points if left blank)

You must enter the names of your collaborators or other sources as a response to Question 0. Do NOT leave this blank; if you worked on the homework entirely on your own, please write “None”here. Even though collaborations in groups of up to 3 people are encouraged, you are  required to write your own solution.

Question 1: (6+4=10 points)

Recall that a sorting algorithm is stable if objects with equal keys appear in the same order in the sorted output as in the unsorted input. For example, consider a list of Student Objects, with two fields, Student.name and Student.age. If sorting according to age, given a list of Student objects, a stable sort will order the list in increasing order of the student ages. If two students have the same age, they will appear in the same order as in the unsorted list.

1. State and prove an appropriate loop invariant for the Merge subroutine (as seen in class) needed to prove the stability of MergeSort.

2.  Using the result of part 1, prove that MergeSort (as seen in class) is stable for any input size n ∈ N by induction on n.

Question 3: (5 points)

Consider the following inductive step in an attempted proof by induction showing n2 = O (n). Suppose for the strong inductive hypothesis that n2 = O (n) for all n ≤ k . Then

(k + 1)2 = k2 + 2k + 1

= O(k) + 2k + 1 by the inductive hypothesis

= O (k)

Explain precisely why this is incorrect.