Computer Science CSC263H Homework Assignment #1

Computer Science CSC263H
Homework Assignment #1

• You must submit your assignment as a PDF file of a typed (not handwritten) document through
the MarkUs system by logging in with your CDF account at:
https://markus.teach.cs.toronto.edu/csc263-2019-01
To work with one or two partners, you and your partner(s) must form a group on MarkUs.
• The PDF file that you submit must be clearly legible. To this end, we encourage you to learn and use
the LATEX typesetting system, which is designed to produce high-quality documents that contain
mathematical notation. You can use other typesetting systems if you prefer, but handwritten
documents are not accepted.
• If this assignment is submitted by a group of two or three students, the PDF file that you submit
should contain for each assignment question:
1. The name of the student who wrote the solution to this question, and
2. The name(s) of the student(s) who read this solution to verify its clarity and correctness.
• By virtue of submitting this assignment you (and your partners, if you have any) acknowledge that
you are aware of the homework collaboration policy that is stated in the csc263 course web page:
http://www.cs.toronto.edu/~sam/teaching/263/#HomeworkCollaboration.
• For any question, you may use data structures and algorithms previously described in class, or in
prerequisites of this course, without describing them. You may also use any result that we covered
in class, or is in the assigned sections of the official course textbook, by referring to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be marked
based on the correctness and completeness of your answers, and the clarity, precision, and conciseness of your presentation.
• Your submission should be no more than 2.5 pages long in a 10pt font.
1
Question 1. (1 marks)
In the following procedure, the input is an array A[1..n] of n arbitrary integers, and “return” means the
procedure stops immediately (breaking out of the loop of the procedure). Note that the indices of array
A start at 1.
nothing(A)
1 A[1] = −1
2 n = A.size
3 for i = 1 to n // i = 1, 2, . . . , n (including n)
4 for j = 1 to n − 1 // j = 1, 2, . . . , n − 1 (including n − 1)
5 if A[j] 6= 1 − A[j + 1] then return
6 if i + j n − 1 then return
7 return
Assume that each assignment, comparison and arithmetic operation takes constant time.
Let T(n) be the worst-case time complexity of calling nothing(A) 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. (1 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 can occur at any point between keys in the input sequence. When a print occurs, the algorithm
must print (in any order) the m smallest keys among all the keys that were input before the print.
For example, suppose m = 3, and the keys and print operations occur in the following order:
20, 15, 31, 6, 13, 24, print, 10, 17, 9, 16, 5, 11, print, 14, . . .
Then the first print should print 15, 6, 13 (in any order), and the second print should print 6, 9, 5 (in any
order).
Assume that at least m keys are input before the first print occurs and that m does not change during an
execution of the algorithm.
Describe a simple algorithm that solves the above problem with the following worst-case time complexity:
• O(log m) to process each input key.
• 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 your algorithm for each operation clearly and concisely, in English.
• 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?)
2
[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) In class we studied binary heaps, i.e., heaps that store the elements in complete
binary trees. This question is about ternary heaps, i.e., heaps that store the elements in complete ternary
trees (where each node has at most three children, every level is full except for the bottom level, and all
the nodes at the bottom level are as far to the left as possible). Here we focus on MAX heaps, where the
priority of each node in the ternary tree is greater or equal to the priority of its children (if any).
a. Explain how to implement a ternary heap as an array A with an associated Heapsize variable (assume
that the first index of the array A is 1). Specifically, explain how to map each element of the tree into the
array, and how to go from a node to its parent and to each of its children (if any).
b. Suppose that the heap contains n elements.
(1) What elements of array A represent internal nodes of the tree? Justify your answer.
(2) What is the height of the tree? Justify your answer.
c. Consider the following operations on a ternary heap represented as an array A.
• Insert(A, key): Insert key into A.
• Extract MAX(A): Remove a key with highest priority from A.
• Update(A, i, key), where 1 ≤ i ≤ A.Heapsize: Change the priority of A[i] to key and restore the
heap ordering property.
• Remove(A, i), where 1 ≤ i ≤ A.Heapsize: Delete A[i] from the heap.
For each one of these four operations, describe an efficient algorithm to implement the operation, and
give the worst-case time complexity of your algorithm for a heap of size n. Describe your algorithm using
high-level pseudo-code similar to that used in your textbook, with clear explanations in English. Express
the worst-case time complexity of your algorithm in terms of Θ and justify your answer.
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 Buildby-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 Θ(n log 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.)
3
Question 5. (0 marks)
Let In be the set of n integers {1, 2, . . . , n} where n is some power of 2.
Note that we can easily use an n-bit vector (i.e., an array of n bits) B[1..n] to maintain a subset S of In
and perform the following three operations (where j is any integer in In) in constant time each:
Insert(j): insert integer j into S.
Delete(j): delete integer j from S.
Member(j): return true if j ∈ S, otherwise return false.
Describe a data structure that supports all the above operations and also the following operation
Maximum: return the greatest integer in S
such that:
• The worst-case time complexity of operations Insert(j), Delete(j), and Maximum is O(log n)
each. The worst-case time complexity of Member(j) is O(1).
• The data structure uses only O(n) bits of storage.
Note that the binary representation of an integer i where 1 ≤ i ≤ n takes Θ(log n) bits. Assume that
any pointer also takes Θ(log n) bits.
A solution that does not meet all the above requirements may not get any credit.
Hint: Complete binary trees can be implemented without using pointers.
a. Describe your data structure by drawing it for n = 8 and S = {1, 2, 6}, and by explaining this drawing
briefly and clearly. Your drawing must be very clear.
b. Explain how the operations Insert(j), Delete(j), and Maximum are executed, and why they take
O(log n) time in the worst-case. Be brief and precise.
c. Explain how the operation Member(j) is executed, and why it takes O(1) time in the worst-case.
Be brief and precise.
4