Background: In class you have learned about many data structures: stacks, queues, trees, tables, lists, and directed and undirected graphs. Each of these are ways that we use to model world problems in a way that a computer can solve it.  Data structures make us formulate the problem in a structured way and give us a clue as to the algorithms at our disposal for finding a solution.  However, often the data structures that we use simplify the problem such that aspects of the original problem are ignored or glossed over.  It is important to examine the assumptions we make about the problem when we use a certain data structure, and we have to think about what happens when the assumptions don't hold.

Tasks:  This lab will give you several problems sets.  In the first, you will compare the application of two different data structures to a problem.  Then you will decide which data structure you would use to solve a problem.  Finally, you will solve one problem from start to finish using Multiple-Choice Programming.

Objectives:

• To think about the advantages of using one data structure over another
• To consider the assumptions inherent in modeling the world with a data structure
• To practice problem-solving using data structures
• To have fun

In this lab, you will help Herbie get around a maze and hopefully find his way out!  Data structures will help you to sort out the problem as we go and eventually solve the problem.

Problem 1:  First, let's see the structure inherent in the problem.  Write out a graph that represents the maze.  Each intersection in the maze is marked with a letter.  Write each intersection as a node, labeled with the intersection's letter.  Draw arrows from the intersection to the other intersections that are directly accessible from that intersection.  What things do you notice about your graph?

Problem 2:  Now you should give a multiple-choice programming algorithm for getting Herbie through the maze.  The data that needs to be stored is again the intersections, but the data structure used should be either a stack, queue, or list of nodes from the graph you made.  You may use the following commands:

Multiple-Choice Programming:  Actions allowed include actions presented in class for whichever data structure you choose to use.  (If you're not sure, ask!)  Also allowed are:

go_to_next_intersection(DIRECTION) -> letter returns the letter at the next intersection after going left, right, or straight.
go_to_intersection(LETTER) works only for letters that have been crossed already!

The output of the algorithm should be a list of intersections that are encountered on a path out of the maze.

Testing:  Use your props to test your algorithm.  Does it find the way out for any maze?

Questions:

Questions marked with (*) are asking for your informed opinion.  They will not be judged as right or wrong, but simply given credit for the amount of thought put into the answer.  Questions marked with (!) are essential to showing your understanding of the material and will be worth more.

(Theoretical !) 1. Does your algorithm find the shortest possible path out of the maze?  If not, how could you change it to ensure it finds the shortest path?

(Theoretical !) 2. Does your algorithm find a path in the shortest amount of time possible?  (Measure algorithm time in terms of the number of intersections visited.)  If not, how could you change it to give it a better chance of working quickly to find a path out?

(Technical) 3. Many times, a graph is represented in the computer as a table.  Can you make a table that says the same thing as this graph?

(Virtual) 4. Often the different data structures have a similar implementation underneath (as seen in problem 3).  For example, both queues and stacks are specific types of lists.  Why is it advantageous to use a stack or a queue instead of the more general list?

(Social *) 5. Can you think of ways that we "use" data structures in life?  For example, we queue up at the bank.  Why do we choose one over the other?  (That is, why not "stack" up at the bank?)

(Philo-ethical *) 6. Do you use data structures in your personal life?  For example, I notice that I tend to work using a stack - once I think of something that needs done, I quit what I'm doing and do the thing I just remembered before I forget.  Do you think you have data structures in your head?  How do you organize your tasks for the day?  your friends' faces and names?  your life goals?

(Philo-ethical *) 7. Are there certain data structures that seem more fair than others?  In other words, most people would say that using a stack instead of a queue at the ticket booth is just unfair.  Is a queue always more fair than a stack?  Can you think of examples when other data structures seem to be more fair?