Spring 2020 CSE310 Midterm 2
Instructions:
• This is a take home examination. While you can check the textbook/lectures and
other resources while working on the examination, it should be your own work.
The instructor may ask any of the students to have a one-on-one recorded zoom video
session (up to 30 minutes) to ask questions either on the exam paper or closely related
to the questions on the exam paper. Depending on the zoom session, the student’s
score on this exam may be adjusted. Refusing the zoom session will result in the
student’s score on this exam invalid. The zoom session is a way to validate that
the student knows the answers submitted.
• There are six problems in this exam. You have to typeset your answers and submit
a PDF file on canvas before 11:59pm on 04/11/2020. You should name your file using
the format CSE310-MD02-LastName-FirstName, where LastName is your last name
and FirstName is your first name.
• Hand-written answers (or photo of hand-written answers) are not accepted.
Problem 1. (21 points: 3+3+3+3+3+3+3)
A max-heap with 11 elements is given in the following array format. The first three subquestions
all refer to this max-heap (not the heap you obtained after doing some operations).
i 1 2 3 4 5 6 7 8 9 10 11
A[i] 11 10 6 7 9 2 5 1 4 3 8
(a) Show the result after applying Heap-Increase-Key(A, 9, 12) to the max-heap at
the top of this page (in array format):
i 1 2 3 4 5 6 7 8 9 10 11
A[i]
(b) Show the result after applying Heap-Extract-Max(A) to the max-heap at the top of
this page (in array format):
i 1 2 3 4 5 6 7 8 9 10
A[i]
(c) At the end of the Heap-Extract-Max(A) operation in (b), will reading A[11] result in
a memory fault or not? Answer YES or NO.
(d) Given the sequence of numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Show the max-heap obtained
by applying the linear time buildheap algorithm (in array format):
i 1 2 3 4 5 6 7 8 9 10 11
A[i]
(e) In (d), how many Max-Heapify operations will be called in total?
(f) What is the worst case time complexity of Heap-Extract-Max in a heap with n elements?
Use the most accurate asymptotic notation to write your answer.
(g) What is the maximum number of Max-Heapify calls when we perform Heap-Extract-Max
in a heap with n elements? Use the most accurate asymptotic notation to write your
answer.
1
Problem 2. (19 points: 3+3+4+3+3+3)
This problem is related to disjoint set operations. Assume that we are using union by rank
and find with path compression. Suppose that you are given a disjoint set structure
described by the following array representation.
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
A |-2 |-2 |-3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 5 | 10| 11| 11| 15|
(a) Write the array representation of the disjoint set structure after applying union(12,
8) to the given disjoint set structure at the top of this page.
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
A | | | | | | | | | | | | | | | | |
(b) Write the array representation of the disjoint set structure after applying union(16,
12) to the given disjoint set structure at the top of this page.
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
A | | | | | | | | | | | | | | | | |
(c) Write the array representation of the disjoint set structure after applying union(8,
12) followed by union(16, 12) to the given disjoint set structure at the top of this
page.
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
A | | | | | | | | | | | | | | | | |
(d) Using the most accurate asymptotic notation, write down the worst-case time complexity
for link in a disjoint set with n elements.
(e) Using the most accurate asymptotic notation, write down the worst-case time complexity
for union in a disjoint set with n elements.
(f) Using the most accurate asymptotic notation, write down the worst-case time complexity
for find-set in a disjoint set with n elements.
2
Problem 3. (20 points: 16 + 1 + 3)
Figure 1 shows a directed graph G. Assume that the adjacency list lists the edges in
alphabetical order.
Figure 1: Graph for P3.
(a) Apply depth first search (DFS) to graph G, and show the discovery and finish times
of each vertex. In the main-loop of DFS, check the vertices in alphabetical
order. You can write the results on the graph in Figure 1.
(b) Draw the transpose graph GT of the graph in Figure 1. The vertices are given for your
convenience.
Figure 2: The transpose graph
(c) Apply DFS to GT
to compute the strongly connected components. You need to show
the strongly connected components and indicate the order they are computed.
3
Problem 4. (14 points: 7+7)
This problem is concerned with shortest paths in graphs.
(a) Figure 3 shows an edge-weighted undirected graph G. Assume that the adjacency
list lists the edges in alphabetical order. Compute the shortest A-v path for each
Figure 3: Graph for P4(a).
vertex v in the graph. Write the shortest A-v distance next to vertex v. Show the
predecessor field of vertex v by adding a direction on the edge connecting vertex v and
its predecessor, where the arrow points to the predecessor.
(b) Figure 4 shows an edge-weighted directed graph G. Assume that the adjacency
list lists the edges in alphabetical order. Compute the shortest A-v path for each
Figure 4: Graph for P4(b).
vertex v in the graph. Write the shortest A-v distance next to vertex v. Show the
predecessor field of vertex v by adding a direction on the edge connecting vertex v and
its predecessor, where the arrow points to the predecessor.
4
Problem 5. (17 points: 3+4+3+4+3)
Figure 5 illustrates a red-black tree, where a black square denotes a black node, a red circle
denotes a red node, and the nil nodes are omitted. Alternatively, you may use a square to
represent a black node, and use a circle to represent a red node.
Figure 5: A red-black tree.
(a) Treat the tree in Figure 5 as a binary search tree, draw the resulting binary search tree
(not necessarily a red-black tree) after inserting 28 into the tree in Figure 5. Which
property of red-black tree is violated after this insertion?
(b) Draw the red-black tree after inserting 28 into the red-black tree in Figure 5.
(c) Treat the tree in Figure 5 as a binary search tree, draw the resulting binary search tree
(not necessarily a red-black tree) after deleting 40 from the tree in Figure 5. Which
property of red-black tree is violated after this insertion?
(d) Draw the red-black tree after deleting 40 from the red-black tree in Figure 5.
(e) Use the most accurate asymptotic notation to denote the worst-case time complexity
of rotation in a red-black tree with n internal nodes.
5
Problem 6. (9 points: 3+3+3)
This problem is concerned with your understanding of various data structures studied in
class.
(a) Suppose that you are asked to choose a data structure to accomplish a given task that
involves insertion and delete-min, and your choice are limited to (1) binary min heap,
(2) binary search tree, and (3) red-black tree. Assume that worst-case time complexity
is the main metric for selection, and ease of implementation is the secondary metric
for selection. Which data structure is the best choice? Why?
(b) Suppose that you are asked to choose a data structure to accomplish a given task that
involves insertion and deletion, and your choice are limited to (1) binary min heap, (2)
binary search tree, and (3) red-black tree. Assume that worst-case time complexity is
the main metric for selection, and ease of implementation is the secondary metric for
selection. Which data structure is the best choice? Why?
(c) Suppose that you are asked to choose a data structure to accomplish a given task
that involves insertion, deletion, and search, and your choice are limited to (1) binary
min heap, (2) binary search tree, and (3) red-black tree. Assume that worst-case time
complexity is the main metric for selection, and ease of implementation is the secondary
metric for selection. Which data structure is the best choice? Why?