CS 3304 UHV Data and Information Structures Questions

CS 3304 – Data and Information StructuresAssignment 6
Due: 12/06/2022, 23:59
Submission: Submit your solutions as a single .pdf file through Blackboard. .pdf file will contain
your solutions for all questions. If you scan your handwritten solutions, be sure that your
handwriting is legible.
Q1 (20 pts). 2-3-4 Tree. Given an empty 2-3-4 Tree, insert the following numbers into 2-3-4
Tree in the given order and show the tree after each insertion. Note that when there are 4
values in a node, select the second value as median and move it to upper level.
55, 22, 79, 36, 13, 31, 24, 26, 44, 34, 37
Q2 (10 pts). Red-Black Tree. Given an empty Red-Black Tree, insert the following numbers into
Red-Black Tree in the given order and show the tree after each insertion. Note that, rotation
will not be needed. You will only need recoloring after inserting some of the values.
15, 20, 10, 5, 13, 12
Q3 (10 pts). Adjacency Matrix. Give the adjacency matrix representation of the directed graph
given below:
Q4 (15 pts). Depth-First Search. Given the directed graph below, show the traversal order (e.g.,
1, 2, 3, 4, ….) when you apply (i) depth-first search starting from 1 and (ii) depth-first search
starting from 2.
Q5 (15 pts). Breadth-First Search. Given the directed graph below, show the traversal order
(e.g., 1, 2, 3, 4, ….) when you apply (i) breadth-first search starting from 2 and (ii) breadth-first
search starting from 10.
Q6 (20 pts). Shortest Path Algorithm. Given the directed graph below, determine the shortest
path from 1 to 11 using the algorithm given in the textbook (it is also given in the slides).
Therefore, you will firstly compute the shortest path from 1 to all vertices. Then, you will
determine the path using the Step 5 of the algorithm.
An example is given below to compute shortest path from A to G:
Step 5 then determines a sequence of vertices on a path from A to G, for example, p[3] = ‘G’,
p[2] = ‘F’, p[1] = ‘B’, p[0] = ‘A’. Then, the shortest path is A -> B -> F -> G.
Q7 (10 pts). Edge List Representation. Give the edge list representation of the undirected
graph given below: