Comp 3170 - Analysis of Algorithms
& Data Structures
Quiz 2
University of Manitoba - Winter 2020
March 30, 2020
“When you come out of the storm, you won’t be the same person who walked in. That’s what this storm’s a
...
Comp 3170 - Analysis of Algorithms
& Data Structures
Quiz 2
University of Manitoba - Winter 2020
March 30, 2020
“When you come out of the storm, you won’t be the same person who walked in. That’s what this storm’s all about ... ”
Haruki Murakami
• Manage your time. We start the exam at 10:30 and end the quiz at 11:00. Any submission after
11:00 will NOT be marked. (You might be able to submit after 11:00 but we will ignore them). Make sure
to submit all your answers by 11:00. You have 30 minutes.
• Write your answers on paper and upload a separate picture for each question on its designated area in Crowdmark.
The marks will be scaled so that the highest mark gets the full mark. This exam also serves as a practice for the
online final exam.
• Consider the exam as an open-book exam. You can refer to the slides and handouts posted in the course. Yet, you
should not write the exam together, or to use any communication method during the exam (No Messenger, Telegram,
etc.). The exam is designed in a way that these methods do not help, and if you try them, it is likely that you run
out of time.
• The instructor will be online during the exam on WebEx. You are welcome and encouraged to join and ask your
questions.
• The exam has a few versions. Please enter your student id in the link below to get your version. Write down your
version in each of the pages that you submit (e.g., its enough to write V1 on top right of the picture you upload
if your version is 1). For each question only write down the answer for your version of the question. If you
write answer to another version, you get 0 for the question. Make sure to remember and follow your version.
Here is the link for finding your version: http://www.cs.umanitoba.ca/~kamalis/winter20/comp3170/quiz2.
html. The link will become available 10 minutes before the start of the exam.
This study source was downloaded by 100000834091502 from CourseHero.com on 11-18-2022 09:26:15 GMT -06:00
https://www.coursehero.com/file/107727938/quiz2-solutionspdf/
Problem 1 Short Answer Questions [12 marks]
Provide short answers for the following questions.
(a) Consider a problem E is reduced to problem H in time Θ(n
2
). Answer the following True/False question. There is
no need to justify your answer.
– Version 1: True or False: Assume there is an algorithm that solves H in O(n
2
log n). We can conclude there is
an algorithm that solves E in O(n
2
log n). Notes: True. A direct consequence of the reduction.
– Version 2: True or False: Assume there is an algorithm that solves E in O(n
3
). We can conclude there is an
algorithm that solves H in O(n
3
) as well. Notes: False. An algorithm for the easy problem cannot be
used for solving an arbitrary instance of the hard problem; reduction only creates particular, specific instances
of the hard problem and not all of them.
– Version 3: True or False: Assume we know any algorithm for E runs in Ω(n log n). We can conclude any
algorithm for H runs in Ω(n log n) as well. Notes: False. We cannot conclude any statement in terms of
lower/upper bounds when the reduction time (here Θ(n
2
)) dominates the existing bounds (here n log n).
(b) Answer the following question about a data structure which only supports insert operation.
– Version 1: Assume each operation is either ‘trivial’, ‘inexpensive’ or ‘expensive’. The time complexity of a trivial
operation is O(1), that of an inexpensive operation is Θ(log n) and that of an expensive operation is Θ(n), where n
is the number of items in the data structure. Assume each 90 trivial operations are followed by 9 inexpensive operations and 1 expensive operation. Write down the amortized cost of each operation using Θ notation. Notes:
For m consecutive operations, there will be 90m/100 trivial operations, 9m/100 inexpensive operations, and
m/100 expensive operations. The total cost will be 90m/100×Θ(1)+9m/100×Θ(log n)+m/100×Θ(n) = Θ(mn).
Hence, the amortized cost is Θ(n) per operation.
– Version 2: Assume each operation is either ‘inexpensive’ or ‘expensive’. The time complexity of an inexpensive operation is Θ(1) and that of an expensive operation is Θ(log n), where n is the number of items in
the data structure. Assume each n − 1 inexpensive operations are followed by a single expensive operation.
Write down the amortized cost of each operation using Θ notation. Notes: For m consecutive operations, there will be m/n expensive operations and (n − 1)m/n inexpensive ones. The total cost will be
(m/n) × Θ(log n) + (n − 1)m/n × Θ(1) = Θ(m). Hence, the amortized cost is Θ(1) per operation.
– Version 3: Assume ach operation is either ‘inexpensive’ or ‘expensive’. The time complexity of an inexpensive
operation is Θ(1) and that of an expensive operation is Θ(log n), where n is the number of items in the data
structure. Assume each 99 inexpensive operations are followed by a single expensive operation. Write down the
amortized cost of each operation using Θ notation.
Notes: For m consecutive operations, there will be m/100 expensive operations and 99m/100 inexpensive
ones. The total cost will be (m/100) × Θ(log n) + 99m/100 × Θ(1) = Θ(m log n). Hence, the amortized cost is
Θ(log n) per operation.
(c) Answer the following question about disjoint sets:
– Version 1: Consider a disjoint set maintained by union-find data structure with path-compression and union-byweight. Indicate whether it is possible that in the union operation, the root of the tree with the shorter height
becomes the new representative. Briefly justify your answer.
Notes: It is possible: Rank is just an upper bound for height. It is possible to have, for example, a
tree of rank 4 and height 1 and a tree of rank 3 and height 2. Note that ‘rank’ and ‘weight’ are often used
interchangeably. You should know this and their difference from ‘height’.
– Version 2: Consider we are given a union-find data structure with path-compression and union-by weight. There
are n elements a1, a2, . . . , an in the data s
[Show More]
