Programming and Computation II Lab #8

CMPSC-132: Programming and Computation II

Lab #8

Watch the video lectures before starting the assignment. For any credit, final answer must be
uploaded using the answer sheet provided.
Instructions:
- The work in this lab must be completed alone and must be your own.
- This is a non-coding assignment
- Make sure your answers are legible, you must submit 1 question per page. You can use the
Word document provided on Canvas. File should be only 7 pages long (no more, no less).
- To receive any credit, circle your final answer, that will help us to locate your answers
faster. If you are unable to complete a question, leave the page blank
- In order to ease the grading process, please use the provided Word template (if you are
creating your own file, please exact 7 pages, 1 page per question) so graders get direct
access to the page instead of traversing the entire file looking for your answers. Check the
Sample Solutions File for do’s and don’ts
- Submit your answers as a PDF file to the Lab8 GradeScope assignment before the due date
Question 1 [2.5 pts]: Draw the binary search tree obtained when inserting the values 47, 5, 3, 70,
23, 53, 15, 66, 81, 64, 85, 31, 83, 33, 9, 7 in that order into an empty BST. In which order are the
elements of the obtained binary search tree accessed during a BFS, Preorder DFS, Inorder DFS
and Postorder DFS traversal? What is the height of the tree? List the child node(s) of the node
with value of 23
Question 2 [1 pt]: Draw the heap that results from inserting 10, 12, 1, 14, 3, 17, 7, 2, 5, 8, 6 and
70 (in that order) into an initially empty binary max heap. What is the array representation of the
obtained heap? Show the result of performing 3 deleteMax operation in the resulting heap
Question 3 [1.5 pt]: Based on the following undirected graph (where there are no weights assigned
to the edges), draw the BFS tree (vertices and tree edges) that results when performing a BFS
traversal starting at node D, also draw the DFS tree that results when performing a DFS traversal
starting at node H. Include with each tree the traversal path. Follow the alphabetical convention
discussed in the video lectures
Question 4 [1 pts]. Performing DFS starting at node A, what is the topological sorting of the
following graph? Draw the final topological sort. Remember that the topological sort is the
decreasing ending times of the DFS traversal. When doing the traversal, follow the nodes in
alphabetical order
Question 5 [1 pt]. Run Dijkstra's algorithm in the directed graph given below and complete the
status of the table when the algorithm is done calculating the shortest path from node s to every
other node in the graph. Based on that table, what is the shortest path and its cost from node s to
node t?
Question 6 [1 pt]: Find the minimum spanning tree for the graph given below using both Prim’s
and Kruskal’s algorithms. 
Question 7 [2 pt]: Assume you have a hash table of size 11. What is the final status of the hash
table after inserting the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5 (in that order) assuming
collisions are handled by open addressing using:
a) linear probing (+1 probe) and the hash function H(i) = (3*i+5) %11
b) quadratic probing and the hash function H(i) = (i) %11
c) double hashing and using the hash functions H1(i) = (i) %11 and H2(i) = 7- (i %7).