Algorithm Analysis Exercise
To gain experience measuring program runtime, and analyzing algorithms.
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.
- Download the DFS program.
- Download the four input mazes: maze1.txt, maze2.txt, maze3.txt and maze4.tar.gz. The last is compressed with tar. Use tar -xzvf maze4.tar.gz to decompress it.
- Compile the program.
- Run the program on each of the four mazes. The program takes the filename as a command-line parameter.
- To time how long a program takes to run, put the word "time" at the beginning of the command:
$ time ./a.out
- The DFS program will tell you how many steps it takes through the maze.
- The time program will tell you how long the program takes to run.
- Report this information for each of the 4 mazes.
- Lastly look at how the DFS algorithm works, how many steps it takes, and how long it takes, and come up with the Big-O complexity.
Email the number of steps and run time of each maze, along with the Big-O complexity, to email@example.com.
Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.