# Algorithm Analysis Exercise

### Objective

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.

### Details

• 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.

### Submitting

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