Project 1 COSC 511 This project was rewritten on 9/24

Due: 9/30/2014

Experimentally measure the running time for breadth first traversal on graphs represented as an adjacency matrix.

1. Obtain running time measurements
2. Plot the measured times. Fit several curves, t0, t1, t2, t3, where a0, a1, a2, and b are constants, and n is size of data set.
   • polynomial of degree 0: t0 = a0
   • polynomial of degree 1: t1 = a0 + a1 n 1
   • polynomial of degree 2: t2 = a0 + a1 n 1 + a2 n2
   • log linear: t3 = a0 + a1 n 1 + b n log n
3. Which of the fitted curves best characterize the BFS algorithm and why is it the best of the four?
4. Make an argument, proof, or demonstration for why your algorithm is implemented correctly.

• Source code
• Table of measurements
• Graphs of fitted curves
• Answers to questions, (1)which is best curve and why, and (2)how do you know your code is correct?