Homework 4: Something Amazing
In this homework, we're going to do something amazing! Mazes!
Take a look at the image below. It's small enough that you can probably figure out how to solve if you stare at it for a bit. (Want a spoiler? Click the image!)
Of course, that was a fairly small maze. But there's no upper limit on how big a maze could be, at least in principle. Here's a bigger one if you want to try it out.
Meh. Too much work.
I bet we could write a program to solve mazes!
Funny you should say that, Duck. That's exactly what this assignment is about.
In this assignment, you will develop a program that can solve mazes of arbitrary size, using data structures you've made entirely from scratch (including making a class that works just like std::vector
or Python's list()
). In doing this work, you'll gain experience with
- Writing code with dynamically allocated arrays of both primitives and objects on the heap.
- Memory management using
new
anddelete
. - Debugging memory management problems with
valgrind
. - Evolving a codebase over time, including writing new classes from scratch.
- Maintaining a Makefile.
- Testing your code (using the CS 70 testing library).
Let's Go!
Both team members should accept the assignment:
- Accept Starter Code on GitHub Classroom
- (Create a new team with your new partner. Please use your first names to make the team name.)
Outline
- Part 1: Written Questions and Partner Contract
- Part 2: Maze Representation
- Part 3:
CoordVector
, Part 1 - Part 4: Solving the Maze, Part 1
- Part 5:
CoordVector
, Part 2 - Part 6: Interlude: A Crack in the Maze
- Part 7:
CoordVector
, Part 3 - Part 8: Solving the Maze, Part 2
- Part 9: Your Turn!
- Part 10: Check Your Submission
Useful Information
Other Resources
You might find Sections 12.1 and 12.2 of the textbook, C++ Primer, 5th Edition, to be helpful.
As always, ask and answer questions on Piazza!
In addition, please review the following pages in the Help Pages:
(When logged in, completion status appears here.)