Home CPSC 340

Algorithm Analysis Exercise

Objective

To gain experience measuring program runtime, and analyzing algorithms.

Task

For this lab, you will analyze how the depth first search program scales with solving larger and larger mazes.

I've modified the program to read in a square maze of any size from a file. You will run this program on mazes of size 10x10, 100x100, 1000x1000 and 5000x5000. Here "N" is the length of one side, 10, 100, 1000, or 5000. You will report how many steps through the maze the program takes and how long the program runs for each size maze. Finally you will look at how the program runs and come up with the Big-O complexity.


Details


Submitting

Email the number of steps and run time of each maze, along with the Big-O complexity, to ifinlay@umw.edu.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.