[SOLVED] CSC263H Data Structures and Analysis September 4 2024 Homework Assignment 1

Computer Science CSC263H

September 4, 2024

Homework Assignment #1

Due: September 11, 2024, by 11:00 am

Question 1. (20 marks)  The following procedure has an input array A[1..n] with n ≥ 2 arbitrary integers.

In the pseudo-code, “return” means immediately exit the procedure and then halt. Note that the indices of array A starts at 1.

weirdo(A[1..n])

1   n = A. size

2 for i = 1 to n                           // i = 1, 2, . . . , n

3 for j = 1 to n                    // j = 1, 2, . . . , n

4 if A[n – j + 1] j then return

5 if (A[i] n – i + 1) or (A[1] + A[2] = 2n – 1) then return

6 return

Assume that each assignment, comparison, and arithmetic operation takes constant time.

Let T(n) be the worst-case time complexity of calling weirdo(A[1..n]) on an array A of size n ≥ 2. Give a function f(n) such that T(n) is Θ(f(n)).

Justify your answer by explaining why it is O(f(n)), and why it is Ω(f(n)). Any answer without a sound and clear justification may receive no credit.

Question 2. (20 marks)

We want to compute the median of every prefix  of an  input array A[1..n] of arbitrary integers.   More precisely, design an algorithm that outputs another array M[1..n], so that M[i] is equal to the median of the integers in the subarray A[1..i]. Recall that when i is odd, the median of A[1..i] is the element of rank (i+1)/2 in the subarray, and when i is even, the median is the average of the elements with ranks i/2 and i/2 + 1. Your algorithm should run in worst-case time O(nlog n).

Hint: Maintain two heaps for the subarray A[1..i]:  one that contains「i/2l elements of this subarray, and one that contains  li/2」elements of this subarray. What elements of A[1..i] should each one of these heaps contain?  What kind of heap each one them is?  How do you use them to compute the median of A[1..i]? How do you maintain these heaps when you increase i to i + 1?

a. Describe your algorithm in clear and concise English, and also provide the corresponding pseudocode. Argue that your algorithm is correct.

b. Justify why your algorithm runs in time O(nlog n) in the worst case.

[The questions below will not be corrected/graded.  They are given here as interesting problems that use material that you learned in class.]

Question 3. (0 marks)   Design an efficient algorithm for the following problem.  The algorithm is given an integer m ≥ 1, and then a (possibly infinite) sequence of distinct integer keys are input to the algorithm, one at a time. A print operation input can also occur at any point between keys in the input sequence. When the algorithm gets a print operation input, it must print (in any order) the m smallest keys among all the keys that were input before this print.

For example, suppose m = 3, and the keys and print operations are successively input to the algorithm in the following order:

18, 13, 29, 4, 11, 22, print, 8, 15, 7, 14, 3, 9, 12, print, 2, 5, . . .

The first print should print 13, 4, 11 (in any order), and the second print should print 4, 7, 3 (in any order). Assume that:  (1) m does not change during an execution of the algorithm,  and  (2) at least m keys are  successively input to the algorithm before the algorithm gets its first print input.

Describe a simple algorithm that solves the above problem with the following worst-case time complexity:

•  O(log m) to process each key input.

• O(m) to perform. each print operation.

Your algorithm must use a data structure that we learned in class.

•  State which data structure you are using and describe the items that it contains.

• Explain how your algorithm processes a key input, and how it processes a print operation input. First describe this clearly and concisely in English, and then give the pseudo code.

• Explain why your algorithm achieves the required worst-case time complexity described above.

• Prove that your algorithm is correct (Hint: use induction. What is your induction hypothesis?)

Question 4. (0 marks)   Let A be an array containing n integers.  Section 6.3 of our textbook  (CLRS) describes a procedure, called Build-Max-Heap(A), that transforms array A into a max-heap in O(n) time. That procedure works “bottom-up”, using Max-Heapify repeatedly.

Another way of transforming A into a max-heap is to insert the elements of A into the heap one at a time. Specifically, the algorithm is as follows:

Build-by-Inserts(A)

A.heapsize := 1

for i := 2..n do

Max-Heap-Insert(A, A[i])

a. Give an example of an input array A for which the two procedures Build-Max-Heap and Build- by-Inserts produce different outputs. Keep your example as small as possible.

b. Let T(n) be the worst-case time complexity of Build-by-Inserts for an input array A of size n. Prove that T(n) is Θ(nlog n).  (Recall that the worst-case time complexity of Build-Max-Heap is O(n), and therefore Build-Max-Heap is more efficient than Build-by-Inserts.)