This is a two-part lab:
- An application that solves a maze using either breadth-first or depth-first search.
- Written answers to questions regarding algorithmic analysis, induction, and invariants.
The main goals of this lab are to use data structures to
implement algorithms and to gain practice using induction.
Concepts you will be familiar with after
this lab include:
- Stacks and Queues
- Depth-First Search
- Breadth-First Search
- gdb
- Induction
- Invariants
Note: This is a two-part, two-week lab assignment.
However, the lab is due in three weeks because of spring break.
This lab is not designed to make you work over spring break, nor
are you expected to. We do expect you to work on it this week
though, and the coding part of this lab should be especially good
practice for the quiz. Plan accordingly.
As with most assignments for the rest of the semester, you will
be working with a partner.
Both partners should be present and working on the
code together. You will both be responsible for
understanding all concepts, so dividing and conquering is not an
option. The academic
integrity policy applies to the entire pair; you cannot work
or share code with anyone outside your partner.
You and your lab partner will share the same git repository,
which is named lab05-<user1>-<user2>.git.
Please access your lab by cloning the appropriate git
repository, e.g.:
$ git clone git@github.swarthmore.edu:CS35-s17/lab05-jbrody1-adanner1.git
Part I: The A-Maze-ing Race
Images taken from UncleShuck's farm, Dawsonville, GA, and from The MAiZE Company.
In this lab, you will implement two search
algorithms—depth-first search and breadth-first search—for finding
a path through a maze.
Search Algorithms
In class last week, you saw the following search algorithm:
Algorithm MazeSearch:
mark start as visited
add start to data structure
while (data structure is not empty):
current = remove location from data structure
if (current == destination): // found a path!
return path found
else for each neighbor of current:
if neighbor not visited:
mark neighbor visited
add neighbor to data structure
return no path exists
The way this algorithm traverses through locations depends on which data
structure is used to store visited locations. When we use a stack, the
algorithm is called
Depth-First Search (DFS). When a queue is used,
it is commonly called
Breadth-First Search (BFS).
In this lab you will implement both DFS and BFS, use them to find
paths through a 2-D maze, and explore how the two search algorithms
produce different paths.
Starting Code
Below is an overview of the
files required for submitting this lab. Those highlighted
in blue will require implementation on your part.
Those highlighted in black are complete and
should not be modified except for comments.
- adts: A directory containing the C++
declarations of the ADTs you will use for this lab.
- stlList.h, stlQueue.h, stlStack.h: C++
implementations of the List,Queue, and Stack ADTs using the C++
Standard Template Library (STL). You will not have to implement a Stack or Queue this lab.
- position.h, position.cpp:
The Position class, which keeps track of the contents of a
position in a maze.
- maze.h, maze.cpp: The Maze class, which is used
to represent a maze and provide solutions to it.
- mazeUtils.h, mazeUtils.cpp: definitions for
Maze helper functions which load a maze from a file and render an
answer.
- main.cpp: the main program which loads a maze from a file, solves it, and prints out the result.
- Makefile: The build instructions for your lab.
- test_data: a directory containing several maze files. The format is described below.
- tests.cpp: a collection of unit tests for your maze program.
ADT Implementations
For this and future labs, you will occasionally be provided with
implementations of the ADTs we discussed in class. These
implementations make use of the C++ Standard Template Library
(STL) and are written as classes named e.g. STLList. To
use these classes, simply #include the header the same way
you normally would.
Programming Requirements
The Maze Layout
Each maze is a rectangular grid. Each space in the grid is assumed
to be connected to the adjacent spaces (left, right, up, and down,
but not the diagonally adjacent spaces. The starting point of each
maze is the upper left corner; the exit is in the bottom right
corner.
The layout of a particular maze will be stored in a file with the
extension .map; you can find several examples in
your test_data directory. A map file contains
the following information:
- The width of the maze in squares (i.e., the number of columns in the map)
- The height of the column in squares (i.e., the number of rows in the map)
- For each row of the map, a string describing all of the spaces in that row.
- Each # character is a wall.
- Each . character is an open space.
For instance, the following is a valid map:
5 3
.#.#.
.#...
...#.
We have given you the code which loads files in this format;
this explanation is just for reference.
The Position Class
We will represent a maze as a two-dimensional grid of pointers
to Position objects. Each Position object
contains relevant information for one place in the maze: the
(X,Y) coordinates (where (0,0) is the upper-left), whether that
position is a wall, and some fields which will be used during
the search to construct an appropriate path through the maze.
The constructor of the Position class should take the
X and Y coordinate values and initialize the other fields to
suitable default values (like NULL
or false).
The 2-D grid that you create for your maze should take the
form of a data member positions of
type Position***. This is an array of arrays
of Position pointers. This way, you can write
e.g. positions[0][0] to get the Position*
which points to the Position object in the upper-left
corner. You'll have to use nested for-loops to
initialize positions correctly.
The Maze Class
A
maze object represents our knowledge of a particular
maze. We can use this information to find a path through the maze
using various search algorithms. You will write two
methods---
solveDepthFirstSearch
and
solveBreadthFirstSearch---which are very similar.
These methods will return a
List*: a pointer to
a list of
Position pointers, which constitute a correct
path through the maze from the start to the finish. If no such path
exists, the method should return
NULL.
You have been given the declaration of
the maze class. You only need to implement each
of the methods. The real magic of making the program work happens in
these methods, which find a path through the maze using the search
algorithm given above.
At the end of the loop, you can determine whether a path has been
found by looking at the exit position and seeing if it has been
visited. If so, you just need to follow the previous position
pointers backward until you reach the start. This gives you the path
to take (in reverse order). If the exit position has not been
visited, then there is no possible path through the maze.
Testing the Maze class
Make sure to run the unit tests we've
provided on your code as you develop. Definitely test your code once
you've finished the
Maze class! It will be easier to find
bugs in your Maze implementation by direct testing than it will be by
trying to find them by hand running the
maze program.
Some of the map files in test_data have
multiple possible solutions. As a result, your output may differ from
the provided solutions depending on how you explore the maze. To get
the same results as the provided solutions, you should explore
neighboring spaces in the following order: up, left, right, and then
down.
Implementing Main
The implementation of
main
should be less work than the
Maze class. It just
involves something assembling the pieces you've constructed above.
The
loadMap and
renderAnswer functions have been
written for you.
loadMap will read a map file and return
a
Maze* if loading was successful. Otherwise, it will
throw a
runtime_error.
renderAnswer should
produce a string containing a solution, which looks like the map from
the input file, but contains \@ characters on the path you found. For example, here is a possible execution of the program:
$ ./maze
Welcome to CS35 lab 05: The A-Maze-ing Race.
where is your maze file? test_data/cycle.map
Which search algorithm to use (BFS or DFS)? DFS
@@###
#@@@#
#.#@#
#..@@
####@
Invalid Inputs: Your maze program should
gracefully handle the following cases of invalid input:
- The user provides a search type other than "BFS" or "DFS"
- The user provides an invalid maze file (to be handled by catching the exception from loadMap)
Memory Management
Your program should run without any memory
errors. It's OK if your destructor(s) do not clean everything up, but
you should at least make a reasonable attempt, and in any case, you should avoid dereferencing uninitialized memory.
Part II: Algorithmic Analysis, Induction,
Invariants
For this part of your assignment, you will give written answers much
in the same way as you did in
Lab 03. Your
submission must be in either PDF or .tex format. To get you started
with LaTeX, we've given you a
WrittenLab.tex which
contains the problems below. For further details about LaTeX, see the
file
LearningLaTeX.tex.
- Prove each of the following claims by induction:
- Claim 1: The sum of the first $n$ odd numbers is
$n^2$; i.e. $$\sum_{k=1}^n (2k-1) = n^2\ .$$
- Claim 2: $\sum_{k=1}^n k^2 =
\frac{n(n+1)(2n+1)}{6}$.
- Claim 3: $\sum_{k=1}^n \frac{1}{2^k} = 1-\frac{1}{2^n}$.
- The function maxEven, given below in pseudocode,
takes as input an array $A$ of $n$ integers and returns the
largest even integer in the array. If no such integers
appear in the array, it returns $-\infty$ (minus infinity). Using
induction and loop invariants, prove that the maxEven
function works correctly. (Hint: you should use the loop
invariant "S(k): at the beginning of the loop iteration with $i ==
k$, max is equal to the largest even integer in the
first $k$ elements of the array, or $-\infty$ if no such numbers
exist.")
function maxEven(A,n):
max = -infinity
for i = 0..n-1:
if A[i] > max and A[i] is even then:
max = A[i]
end if
end for
return max
end function
- The Horserace. You are in charge of organizing a
large horse race. There are 25 horses, and you must determine the
three fastest horses (Win, Place, and Show) by placing them
into races. Unfortunately, your track only has space for five
horses, and you have no timing equipment. You're able to race
five horses at a time, and have decided to run multiple races to
determine the three fastest horses. You can race each horse any
number of times. However, you can only race five horses at a
time, and you cannot directly compare results from two different
races (since you don't keep track of exact times).
Give a method to determine the three fastest horses. What is
the minimum number of races you need to arrange?
Commenting and Coding Style Requirements
For this and future labs, graders will assign minor penalties for poor commenting and coding style. Here are some style tips for this lab:
- You should pick meaningful variable names.
// good
int *array = new int[size];
// bad
int *a = new int[size];
- You should use correct and consistent indentation. Lines of
code within a block should be indented two spaces further than lines
surrounding them.*
//good
if(condition) {
cout << "Test" << endl;
}
//bad
if(condition) {
cout << "Test" << endl;
}
*if your text editor's default indenting is four spaces instead of two, don't stress about it. Just be consistent when indenting.
-
You should use a code block whenever possible, even if it's not
necessary. This will help you avoid subtle/messy errors in the
future.
//good
if(condition) {
cout << "Something" << endl;
}
//legal but bad
if(condition)
cout << "Something" << endl;
- Do write comments at the top of each file, indicating your name and the purpose of the code file
- You don't have to write a comment for each line of code, but do write comments about meaningful chunks of code such as a loop, if/else statement, etc.
- Do write comments describing the purpose and signature of each
function declaration. Use @param to describe an input
parameter, @return to describe what gets returned, and
@throws to describe exceptions that should be thrown. An example
lies below:
/**
* Retrieves the first element of the list.
* @return The element at index 0 of this list.
* @throws runtime_error If the list is empty.
*/
virtual T peekHead() = 0;
Extra Challenges
- We've given you STL implementations for each of the ADTs you've
seen so far this semester. In particular, you didn't need to
implement a Stack or Queue ADT> Give those implementations as an extra
challenge. Do they perform better or worse than the STL
implementations?
- Give some analysis which compares the performance of DFS and BFS
over several graphs. Does one algorithm tend to find a path in fewer
steps? Does one return a shorter path?
- In the Horserace Problem, there were 25 horses. Suppose
you wanted to know the three fastest horses out of a group of $n$
horses? How many races would you need? Express your answer as a
function of $n$ and do not use big-O notation.
These additional features are optional -- we'll look at them, but
they won't be for credit. Make sure you complete and push
both parts of the main lab before starting any extra challenge, and
note in your README file that you've done extra challenges so the
graders know which version of your lab to grade. (There's a chance
your added features will break our grading scripts; we'll grade the
base version of your lab to ensure you don't get penalized in the
off-chance your extra features break our grading scripts)
Survey
When you have completed your lab, answer a few short survey questions
in the file
README.md.
Summary
To summarize the requirements of this lab:
- You should have a working maze class.
- You should have a main function which provides a simple interface to solve maze problems.
- The input should be validated, and your code should contain no
memory errors.
- You should have written answers to the analysis questions in a PDF or LaTeX document.
Submit
Once you are satisfied with your code, hand it in using git.
Remember the add, commit, push development cycle. You can push
as many times as you like, but only the most recent submission will be
graded. You may want to
run git
status to confirm all modifications have been pushed.