Amaze State

In this lab we begin our exploration of algorithms, the conceptual heart of computer science. You’ll develop a simple algorithm to escape a maze, and then learn about a highly-structured way of representing algorithms called state machines. In the second half, you’ll implement your maze-solving algorithm in Java.

1. Mazes and States (50 Minutes)

Let’s learn more about algorithms—systematic ways that we and computers use to solve problems.

Complete this part of the lab in pairs using Google Docs. Create a copy of our document template, and then edit it to record you and your partner’s answers. Note that you must open this document using your @illinois.edu Google Apps account. We will not grant access to non-Illinois users.

Have a course staff member check your answers as you go. When you are done, move on to the next section.

2. Implementing Your Maze Algorithm (60 Minutes)

Now let’s implement the maze solving algorithm that you designed in the first half in Java.

These examples use the CS 125 mazemaker Java library, which uses a well-known algorithm to automatically generate mazes. You can find the mazemaker source code and documentation on GitHub 1

2.1. Evaluating Algorithms

As you begin implementing your maze escape algorithm, think about the different ways that computer scientists evaluate algorithms. Here are some of the components of a good algorithm:

  1. It works. It should definitely solve the problem you are trying to solve, or at least have a good probability of solving it in most cases.

  2. It should perform well. It should not require a huge amount of resources to solve the problem—whether those resources are time, computational horsepower, computer memory, or disk space.

  3. It should be understandable. Good algorithms are easy to understand and reason about. The best ones are simple, and sometimes we even call them elegant. Complex algorithms are hard to understand, making it difficult to think about what they will do in certain cases.

  4. The implementation should be clear and understandable. Many times we encounter algorithms while reading computer code. So just as the algorithm must be clear, the implementation in computer code must also be clear. We will have a lot more to say about code quality throughout the semester—particularly on the MPs.

These are not non-contradictory goals. Frequently the desire for simplicity clashes with attempts to improve performance, or handle all inputs correctly. But particularly when you are starting off as a computer science, err on the side of simplicity. Remember: computation is (increasingly) cheap, humans are expensive. If it takes me 10 times longer to understand or modify your algorithm, it is not worth a only minor improvement in performance. Let your algorithms waste a bit of computer time, but never human time.

2.2. Forking and Cloning the Lab2 IntelliJ Project

We’ve set up an Lab 2 GitHub repository containing an IntelliJ Project that’s correctly configured for Lab 2. Getting access to it is similar to how you imported MP0. But you have to fork our repository first. If it’s not obvious how to do that, try following these instructions.

2.3. Implementing Your Solution

There is only one Java file in this lab project: SolveMaze.java. Inspect it and you’ll find a place to implement your solution.

2.3.1. Visualization and experimentation

Once you have your basic algorithm working, tinker around a bit. Try some of the following:

  1. Try starting or ending at a different location

  2. Try using mazes with different dimensions

  3. See if you can visualize your movement through the maze. The maze object is printable, and can be passed to System.out.println just like a string. However, to slow down the display and see what is going on you might want to explore Thread.sleep.

2.3.2. Your algorithm’s performance

Once you have a working algorithm, spend some time understanding its performance. Answer the following questions 2:

  1. How many steps—each consisting of moving one square—does it take to finish the maze? Because the maze generation is random, you might want to run multiple trials and average the results.

  2. For a maze with dimensions N by M, what is the minimum number of steps required to complete the maze, assuming you start at the bottom left and exit at the top right?

  3. How much worse does your algorithm do? Why?

  4. Can you come up with ways to improve your algorithm?

2.3.3. Your algorithm’s limitations

Now spend some time thinking about the limitations of your algorithm. In particular, the mazes that are generated by our maze creator all have something in common: They have no loops! This is due to the operation of the maze generation algorithm, which uses a simple depth-first search over the two-dimensional space. To make things more interesting, we could have inserted some holes at the end—but we didn’t.

But suppose you ran your algorithm on a maze with loops. Think up one way it could get stuck. So it’s possible that your algorithm may not work! But, assuming that the start and end point are always on the exterior wall of the maze, try to convince your partner that your algorithm will still work.

2.4. A Randomized Algorithm

The maze-solving algorithm you implemented above is deterministic. Provided the same maze, it will always navigate through it in the same way. You may want to rerun your algorithm on the same maze a few times to convince yourself of this.

Deterministic algorithms are great—easy to understand and reason about. But there is a different class of algorithms called randomized algorithms. As their name implies, these algorithms use randomness as part of their logic. In some cases, this allows them to dramatically outperform the best known deterministic algorithm.

IRobot Roomba 780

One randomized algorithm that you may have seen in action is a space-filling algorithm called a random walk. If you’ve ever watched a Roomba 3, you’ve seen a random walk in action. It turns out that mapping is a hard problem for robots to solve. So, rather than trying to map an area, early robotic vacuums 4 just implemented a random walk:

  1. Go straight until you hit something

  2. Turn a random amount but sufficient to not continue into the obstacle

  3. Repeat

To a human observer this looks crazy—how is it ever going to get every spot? But it turns out that there is some fairly sophisticated mathematics that shows that, given a certain number of passes, your random robot maid will get every spot with very high probability. Or at least chase a duck:

2.4.1. Implement a random walk

Inspired by your vacuum, try re-implementing your maze-solving algorithm using a random walk. More or less, here’s how that works:

  1. Go forward until you are facing a wall

  2. Randomly turn right or left

  3. Repeat

Note that you may have to give this algorithm many (many) more steps to allow it to finish! Once you are done, compare the running time of your randomized algorithm with the deterministic algorithm you implemented above. Are you surprised? With your partner, try to develop an explanation for the difference in performance.

2.5. Saving Your Work

Before you leave, please submit your work to GitHub. We are not going to grade it, but you should submit it anyway!

CS 125 is now CS 124

This site is no longer maintained, may contain incorrect information, and may not function properly.

Created 10/24/2021
Updated 10/24/2021
Commit a44ff35 // History // View
Built 10/24/2021 @ 21:29 EDT