University of Waterloo
CS240 Winter 2020 Assignment 2
Due Date: Wednesday, February 12 at 5:00pm
Please read http://www.student.cs.uwaterloo.ca/~cs240/w20/guidelines.pdf for guidelines on submission. This assignment contains both written problems and a pro- gramming problem. Submit your written solutions electronically as a PDF with file name a2Submit.pdf using MarkUs. We will also accept individual question files named a2q1.pdf, a2q2.pdf, … , a2q6.pdf if you wish to submit questions as you complete them.
Note: you may assume all logarithms are base 2 logarithms: log = log2. Problem 1 [8 marks]
Generalize quickSelect1 to work on two input arrays. Let the resulting algorithm be called quickSelect2Arrays(A,B,k). Arrays A and B are of size n and m, respectively, and k ∈ {0,1,…,n+m−1}. AlgorithmquickSelect2Arrays(A,B,k)shouldreturntheitemthat would be in C[k] if C was the array resulting from merging arrays A and B and C was sorted in non-decreasing order.
Your algorithm quickSelect2Arrays(A, B, k) must be in-place, i.e. only O(1) additional space is allowed. Briefly and informally (one or two sentences) argue that the time complexity of your algorithm is the same as of quickSelect1, i.e. O(v) in the average case where v is the total number of elements in A and B, i.e. v = n + m. Hint: use the same pivot-value for partitioning both arrays.
Problem 2 [4+5(+6)=9(+6) marks]
For this question, assume Quicksort algorithm selects the last element of A as pivot, and partition(A, p) is as below:
1
partition(A, p)
A: arrayofsizen, p: integers.t. 0≤p