Mcdermott 6014 Final Summer B 17

CST 370 Design and Analysis of Algorithms
Summer B 2017
Final Exam
Name: _____Cian McDermott____________________
Four-digits ID: ____6014___________________________
Test time is 2 hours and 30 minutes.

Note that there are 10 problems in the exam.
This is a closed book exam. You cant use a calculator during the
exam. However, as a reference during the exam, you can prepare two
pages (= total of 4 sides) cheat sheet. The cheat sheet can be typed or
hand-written.
If possible, enter your answers directly into the Word file to increase the
readability of your answers. However, if it is too difficult or time
consuming to type in a Word file, write down your answer on paper.
Then, take a picture and insert the picture into the Word file.
During the exam, you must sign into the midterm Zoom session and turn
on the video. We will record the video. However, turn off the audio on
your computer.
If you have a question during the exam, please use "Chat" in Zoom. I will
answer.
When you finish the exam, submit your Word file (and PDF file) on the
iLearn. But keep the Word file well in case we need it.
Use your time wiselymake sure to answer the questions you know first.
Read the questions carefully.
CST370 Page 1 of 14 Final (Summer B)

1. (3 points) (a) Is this an AVL tree? (Yes/ No)
Yes. Height difference between subtrees is less than or equal to 1.
(b) Is this a max heap? (Yes/ No)
No. Tree may be complete, but the child nodes are not left-justified.
(c) Is this a 2-3 tree? (Yes/ No)
Yes. All of the leaves are at the same level, and all nodes have only 1 or 2 values.
2. (3 points) Consider an AVL tree as below. Add the following nodes to the tree. You should
present each step clearly.
10, 11, 8, 9
7
2
Adding 10 to the tree:

Adding 11 to tree:
Tree is now unbalanced. Rotating at node 10:
Adding 8 to tree:

Unbalanced. Rotating:
Still unbalanced. Rotating again:
Adding 9 to tree:

3. (3 points) Draw all possible AVL trees with 4 nodes of the key values 10, 15, 20, and 25 that
satisfy the balance requirement of AVL trees.

4. (2 points) Draw a sample 2-3 tree of height 2 with the largest number of key values. In your
answer, the tree should have integer values such as 10, 20, 30, etc. Note that a tree with only one
node (= root node) has the height zero.
5. (4 points) (a) Construct a max heap for the list 9, 5, 6, 10, 4, 8, and 3. You should assume that
the numbers are given in that order and use the bottom-up approach covered in the class. For the
problem, you dont need to describe the intermediate results. A final result is good enough.

(b) For the result of question (a), delete the maximum value and draw the updated heap.
(c) For the result of the question (b), insert a node with the value 7 and draw the updated heap.

6. (3 points) Apply the Warshalls algorithm to get the transitive closure of the digraph defined by
the following graph. Present R(0), R(1), R(2), R(3), and R(4) as we discussed in the class.
1 2
3 4
R(0):
1 2 3 4
1 0 1 0 0
2 0 0 0 1
3 0 0 0 0
4 1 0 1 0
R(1):
1 2 3 4
1 0 1 0 0
2 0 0 0 1
3 0 0 0 0
4 1 1 1 0
R(2):
1 2 3 4
1 0 1 0 1
2 1 0 1 1
3 0 0 0 0
4 1 1 1 0
R(3):
1 2 3 4
1 1 1 1 1
2 1 1 1 1
3 0 0 0 0
4 1 1 1 1
R(4):
1 2 3 4
1 1 1 1 1
2 1 1 1 1
3 0 0 0 0
4 1 1 1 1

7. (3 points) Assume that you are going to solve the MST (Minimum Spanning Tree) problem
using the Prims algorithm for the following graph. Draw the final MST. For the problem, you
have to start from the vertex a. You must also provide the sequence of vertices to be added to the
"visited" set as we covered in the class.
Using Prim's algorithm, we start at a and we continue to choose the edge with the lowest value
connected to all nodes reached so far, until all nodes have been visited. Given this, the sequence
the vertices are visited is:
{a, b, d, c, e}
8. (3 points) Assume that you are going to solve the single-source shortest-paths problem using
the Dijkstras algorithm for the following graph. For the problem, you should start from the
vertex a. Fill out the table as you learned in the class.
a 5 c
7 1 3
1
b 3 d 6 e
V a b c d e
a 0a 7a 5a 1a inf
d 3d 1c 1a 6d
c 3d 1c 3c

e 3d 3c
b 3d

9. (3 points) Two missionaries and two cannibals must cross a river. Their boat can only hold two
people. If present, missionaries cannot be outnumbered by cannibals. How can all four get across
the river with the fewest crossings? Note that we covered this puzzle in the class. But at that time,
we solved the puzzle of six persons. But this problem is about 4 persons, and you have to present
the minimum number of crossings. And also, you should draw a diagram to explain your
answer clearly. If the instructor cant under your diagram, you will not get the full credits. If its
not possible for the four persons to cross the river, indicate it clearly.
Both missionaries cannot cross first, or else the one who brings the boat back will get
outnumbered. The options left are that one each cross first, or both cannibals cross first. In both
cases, the minimum number of crossings that will not end with missionaries being outnumbered
is 5.
10. (3 points) Suppose you have a max heap. Design an efficient algorithm to find and delete an
arbitrary element of a value v in the max heap. After that, you have to present the time efficiency
of each operation (= find and delete). You should write your answer in English step-by-step so
that the instructor can understand your idea clearly.

The algorithm takes a value v and an array h, meant to represent the heap (index 0 is blank, first
half are parent nodes, second are children). If there is a value equivalent to v in the array, it is
replaced by the last value in the array. Afterwards, in order to make sure the conditions for a heap
are met, the values in the array are rearranged if either child of a certain parent node is greater
than the parent (checking if, at any index i, where 1 < i < n/2, if 2i or 2i+1 is greater than i). If
that is the case, then the greater of the child nodes switches with the parent node. This continues
until the array qualifies as a heap. When re-sorting after removing a node, we should follow the
"button-up" approach, and start at the "lowest" parent node and move all the way to index i = 1.
The operation for finding the value within the heap searches every node until the exact value is
found, so it has a time efficiency of O(n).
The operation for deleting and resorting the heap continues until the values are properly sorted, so
they have a time efficiency of O(log(n)).

Mcdermott 6014 Final Summer B 17

Uploaded by

Copyright:

Available Formats

Mcdermott 6014 Final Summer B 17

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mcdermott 6014 Final Summer B 17

Uploaded by

Copyright:

Available Formats

CST 370 Design and Analysis of Algorithms

Name: _____Cian McDermott____________________

Four-digits ID: ____6014___________________________

Test time is 2 hours and 30 minutes.

CST370 Page 1 of 14 Final (Summer B)

Yes. Height difference between subtrees is less than or equal to 1.

(b) Is this a max heap? (Yes/ No)

(c) Is this a 2-3 tree? (Yes/ No)

CST370 Page 2 of 14 Final (Summer B)

Tree is now unbalanced. Rotating at node 10:

CST370 Page 3 of 14 Final (Summer B)

Still unbalanced. Rotating again:

CST370 Page 4 of 14 Final (Summer B)

CST370 Page 6 of 14 Final (Summer B)

CST370 Page 7 of 14 Final (Summer B)

CST370 Page 8 of 14 Final (Summer B)

CST370 Page 10 of 14 Final (Summer B)

CST370 Page 11 of 14 Final (Summer B)

CST370 Page 12 of 14 Final (Summer B)

CST370 Page 13 of 14 Final (Summer B)

CST370 Page 14 of 14 Final (Summer B)

You might also like

Name: _Cian McDermott________________

Four-digits ID: 6014_______________________