Description
1. Understanding Multiway Search Trees (7 pts)
Consider inserting the numbers “1,2,3,4,5,24,22,10,26,30,15,16,23,31,12,32,33” into:
(1) an empty top-down tree of order 5 (you should redraw the tree just before each new
node is created)
(2) an empty B tree of order 5 (you should redraw the tree just before one or more nodes
are split)
2. Understanding graphs (7 pts)
For the graph below compute the following:
(1) Find its adjacency matrix representation.
(2) Find its path matrix using powers of the adjacency matrix (show your work).
(3) Find its path matrix using Warshall’s algorithm (show your work).
A
B
C
D
E
3. Implementing a graph (TBA)
Complete the “A6Graphs-LastName.c” program. This program computes the path matrix
of a given graph in two different ways and then compares the runtimes and outputs.
A number of test data files have been provided of varying sizes. The simple 8 node one is
recommended when you are trying to error check your code since you can easily compute
the path matrix be hand to check your work. Which file is being read can be changed at the
top of the main.
You can check your computed path matrices in the file “GraphOutput.txt”. For Graphs of
more than 50 nodes these may be difficult to read.
Deliverables:
Problem 3 should be submitted as one C source code files.
Your answers to homework problems 1 and 2 can be typed or handwritten and should
submitted in a separate document (there are free scanners in the JPL).
Archive and submit the files in UTSA’s Blackboard system (learn.utsa.edu) under Assignment 6.
Remember:
The program you submit should be the work of only you. Cheating will be
reported to judicial affairs. Both the copier and copiee will be held responsible.