Assignment #6: Trees and Graphs Solution



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)

    1. an empty B tree of order 5 (you should redraw the tree just before one or more nodes are split)

  1. Understanding graphs (7 pts)

For the graph below compute the following:

  1. Find its adjacency matrix representation.

  1. Find its path matrix using powers of the adjacency matrix (show your work).

  1. Find its path matrix using Warshall’s algorithm (show your work).




3. Implementing a graph (TBA)

Complete the \A6Graphs-LastName.c” program. This program computes the path matrix of a given graph in two di erent ways and then compares the runtimes and outputs.

A number of test data les 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 le is being read can be changed at the top of the main.

You can check your computed path matrices in the le \GraphOutput.txt”. For Graphs of more than 50 nodes these may be di cult to read.


Problem 3 should be submitted as one C source code les.

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 les in UTSA’s Blackboard system ( under Assign-ment 6.


The program you submit should be the work of only you. Cheating will be reported to judicial a airs. Both the copier and copiee will be held responsible.