University of Waterloo
CS240 Spring 2022 Assignment 2
Due Date: Wednesday, June 1 at 5:00pm
The integrity of the grade you receive in this course is very important to you and the University of Waterloo. As part of every assessment in this course you must read and sign an Academic Integrity Declaration before you start working on the assessment and submit it before the deadline of June 1 along with your answers to the assignment; i.e. read, sign and submit A02-AID.txt now or as soon as possible. The agreement will indicate what you must do to ensure the integrity of your grade. If you are having difficulties with the assignment, course staff are there to help (provided it isn’t last minute).
The Academic Integrity Declaration must be signed and submitted on time or the assessment will not be marked.
Please read https://student.cs.uwaterloo.ca/~cs240/s22/assignments.phtml#guidelines for guidelines on submission. Each question must be submitted individually to MarkUs as a PDF with the corresponding file names: a2q1.pdf, a2q2.pdf, a2q3.pdf, a2q4.pdf . It is a good idea to submit questions as you go so you aren’t trying to cre-
ate several PDF files at the last minute.
Late Policy: Assignments are due at 5:00pm on Wednesday. Students are allowed to submit one late assignment, 2 days after the due date on Friday by 5:00pm. Assignments submitted after Friday at 5:00pm or Wednesday at 5:00pm (if you have already used your one late submission) will not be accepted for grading but may be reviewed (by request) for feedback purposes only. If you want to use your one time late assignment allowance, please send an email to with the title “Using one time late assignment al- lowance”.
Question 1 [4 marks]
Suppose we are working with a heap, represented as an array, and we want to remove an element from it that is not necessarily the root. We are given the index of this element in the array. Describe an algorithm that performs this task and analyse its complexity (since we did not prove correctness of fix-up/fix-down in class, we do not require you to prove correctness).
程序代写 CS代考 加微信: cstutorcs
Question 2 [8 marks]
We want to prove the following: there is no comparison-based algorithm that can merge m sorted arrays of length m into a unique sorted array of length m2 doing O(m2) comparisons. We argue by contradiction, and we assume that it is possible, so that we have such an algorithm (which we call FastMerge).
Modify MergeSort in order to use FastMerge, and derive a contradiction. You may use the following property: if a function T (n) satisfies T (n) = √nT (√n) + O(n), then T (n) = O(n log(log(n))). Do not worry about n being a perfect square or not.
Question 3 [8 marks]
Given an array A[0 . . . n − 1] of numbers, show that if A[i] ≥ A[i − j] for all j ≥ log(n), the array can be sorted in O(n log(log(n))) time.
Hint: Partition A into contiguous blocks of size log(n); i.e. the first log(n) elements are in the first block, the next log(n) elements are in the second block, and so on. Then, establish a connection between the elements within two blocks that are separated by another block.
Question 4 [3+3+4 marks]
The median of a sequence (a1, . . . , an) of integers is defined as follows: assume we sort these integers, and write them as (a′1, . . . , a′n) once sorted. Then their median is a′⌈n/2⌉. For instance:
• ifn=1,themedianof(2)is2
• ifn=2,themedianof(5,1)is1
• ifn=3,themedianof(2,10,1)is2
• if n = 4, the median of (5,5,2,1) is 2, etc
Even though we sort the sequence to define the median, it is possible to avoid using any sorting algorithm to compute it: for instance, quickselect finds the median of a sequence of length n in average time O(n).
In this problem, we study an online algorithm for finding the median of a sequence: we suppose that we receive the entries of the sequence one at a time, and we want to print the medians of all these partial sequences as we go. For instance:
• suppose we first receive 15. We print 15, which is the median of the sequence (15) • next, we receive 10. We print 10, which is the median of the sequence (15, 10)
• next, we receive 1. We print 10, which is the median of the sequence (15, 10, 1)
• next, we receive 20. We print 10, which is the median of the sequence (15, 10, 1, 20)
Code Help
• next, we receive 30. We print 15, which is the median of the sequence (15, 10, 1, 20, 30)
Re-computing the median from scratch every time would be too slow. Here is an idea for a better algorithm: use two heaps Hlo and Hhi, each of which will roughly contain half of the elements seen so far: if we have seen n elements, Hlo should contain the ⌈n/2⌉ smallest elements, Hhi should contain the ⌊n/2⌋ largest ones.
(a) On the example (15, 10, . . . ) above, show us what these heaps would contain at each of the 5 steps (we don’t know if these are min-heaps or max-heaps yet, so just tell us what elements they contain).
(b) We would like to be able to read off the (current) median using just one access to Hlo. What kind of heap should it be, a min-heap or a max-heap? How long does finding the current median take?
(c) Describe how to update the two heaps when inserting the next element. In particular, in which heap do you insert the element, and how do you ensure that Hlo and Hhi have the required size afterwards? Give the runtime of your update method, with a short justification; it should be o(n). (At this stage, you will have to explain whether Hhi should be a min-heap or a max-heap.)
Programming Help, Add QQ: 749389476