Assignment #1 - Department of Computer Science

Computer Science B63
Scarborough Campus
January 7, 2015
University of Toronto
Homework Assignment #1
Due: January 21 26, 2015, by 2:30 12:30pm
(in the drop box for your tutorial section)
• Appended to this document is a cover page for your assignment. Fill it out, staple your answers to it,
and deposit the resulting document into the drop box for your tutorial section. An assignment submitted
on behalf of two students will be returned to the tutorial in whose box it was deposited. Please do not
enclose your assignment in an envelope.
• For any question, you may use data structures and algorithms previously described in class without
describing them. You may also use any result that we covered in class, or is in the relevant sections of
the course textbook, by referring to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be graded based
on the correctness and completeness of your answers, and the clarity, precision, and conciseness of your
presentation.
Question 1. (10 marks) In the procedure Bizarre below, the input is an integer array A[1..n] of length
at least two.
Bizarre(A)
1
2
3
4
5
6
if A[1] 6= 2 then return
for i := 2 to n do
if A[i] 6= A[i − 1] then return
for j := 1 to i − 1 do
A[j] := A[j] − 4
A[i] := A[i] + 4
Let T (n) be the worst-case time complexity of executing procedure Bizarre(A) on an array A of size
n > 1.
a. (3 marks)
Is T (n) = O(n2 )? Justify your answer.
b. (7 marks)
Is T (n) = Ω(n2 )? Justify your answer.
Question 2. (10 marks)
a. (3 marks)
You are given the following array A of 8 integers: [5, 0, 3, 1, 14, 10, 16, 11].
Apply the linear-time algorithm Build-Max-Heap that turns an array into a max-heap, described in the
textbook (CLRS 6.3), to the array A and show the resulting array. Do not show any intermediate result.
b. (3 marks) Starting from an initially empty max-heap array A, successively insert the keys 5, 0, 3, 1,
14, 10, 16, 11 (one at a time and in that order) into A using the Max-Heap-Insert operation, described
in the textbook (CLRS 6.5). Show the resulting array. Do not show any intermediate result.
c. (4 marks) A max-leftist-tree is similar to the (min-) leftist trees we discussed, except that the key of
each node is greater than or equal to (instead of smaller than or equal to) the keys of the node’s children,
if any. This data structure supports the Extract-Max (instead of Extract-Min) operation, as well as
the Merge and Insert operations. The only adjustment needed in the algorithms we have seen for (min-)
leftist trees is to reverse the sense of comparisons between keys. (The sense of comparisons between dist
fields of nodes remains unchanged.)
1
Starting from an initially empty max-leftist-tree, successively insert the keys 5, 0, 3, 1, 14, 10, 16, 11
(one at a time and in that order) into the max-leftist-tree, using the insertion procedure described in the
notes on leftist trees, modified for max-leftist-trees as noted above. Show the resulting max-leftist-tree.
Do not show any intermediate result.
Question 3. (10 marks) Suppose you have an array A[1..n] containing integers. Let k be some integer
such that 1 ≤ k ≤ n, and x be any integer. We want an efficient algorithm that, given A, k, and x, outputs
k integers “closest” to x that appear in distinct entries of A, in order of their closeness to x.
For example, if A = [8, 6, 9, 3, 7, −2, 6, 3], k = 4, and x = 1, the algorithm should output 3, 3, −2, 6.
More precisely, the integers output by the algorithm satisfy the following properties:
• if A[i] is output and A[j] is not, then |x − A[i]| ≤ |x − A[j]| (i.e., A[i] is at least as close to x as A[j]);
and
• there is a sequence i1 , i2 , . . . , ik of pairwise distinct indices between 1 and n such that the sequence
of integers output is A[i1 ], A[i2 ], . . . , A[ik ], and for all 1 ≤ j < k, |x − A[ij ]| ≤ |x − A[ij+1 ]|.
a. (8 marks) Describe an algorithm that solves this problem. Your algorithm must use a data structure
discussed in class, and should run in O(n + k log n) time in the worst case. Give a clear and precise English
description of your algorithm, then give the corresponding pseudo-code.
b. (2 marks)
Explain why your algorithm achieves the above running time.
Question 4. (10 marks) Consider the following additional operations on a (min-) heap A.
• Change-Key(A, i, key), where 1 ≤ i ≤ heapsize(A), changes the priority of element A[i] to key and
restores the (min-) heap ordering property.
• Delete(A, i), where 1 ≤ i ≤ heapsize(A), deletes the element A[i] from the heap, leaving A as a
heap containing the remaining elements, of size one less than before the operation.
Give algorithms to implement each of these two operations. You should describe each algorithm using
high-level pseudo-code similar to that used in your textbook (and in the lectures), with clear explanations
in English where needed. Your algorithms should run in worst-case time Θ(log n), where n = heapsize(A),
and you should explain why.
Question 5. (10 marks) Consider (min-) leftist trees where each node contains a pointer to its parent,
in addition to the information normally stored at leftist tree nodes (i.e., the key, the distance, and pointers
to the children). The parent pointer of the root is nil.
a. (2 marks) Modify the algorithm for merging two leftist trees so that it correctly handles the parent
pointers. Your algorithm should work in O(max(log n1 , log n2 )) time, where n1 and n2 are the number of
nodes of the two trees being merged.
b. (8 marks) Give an algorithm Delete(r, p) which, given a pointer r to the root of a leftist tree with
parent pointers and a pointer p to an arbitrary node of that tree, deletes that node from the tree and
fixes up the data structure so that r now points to the root of a leftist tree that contains the remaining
nodes. You should describe your algorithm using high-level pseudocode and clear English explanations
where needed. Your algorithm should run in O(log n) time, where n is the number of nodes in the tree.
Explain why your algorithm achieves this time complexity.
2
Cover page for
CSCB63 Homework #1
Submitted by
(2) Family Name:
(1) Family Name:
Given Name:
Given Name:
Student Number:
Student Number:
Tutorial:
Tutorial:
By virtue of submitting this homework I/we acknowledge that I am/we are aware of the policy on
homework collaborationa for this course.
a
“In each homework you may collaborate with at most one other student who is currently taking CSC B63. If you
collaborate with another student on a homework, you and your partner must submit only one copy of your solution, with
both of your names on the cover. The solution will be graded in the usual way and both partners will receive the same mark.
Collaboration involving more than two students is not allowed. For help with your homework you may consult only
the instructor, TAs, your homework partner (if you have one), your textbook, and your class notes. You
may not consult any other source.”
3

Download Report