Objectives

• Work through the details of AVL tree and hash table implementations.
• See how asymptotically better algorithms and efficient coding let you solve problems that were previously unsolvable.
• Solve some fun puzzles... faster!

Overview

For this project, we revisit the Universal Puzzle Solver that you worked on in Project 1. In particular, now that you've learned some new, more powerful data structures, we can go back and make the solver a lot faster and more powerful!

In Project 1, we focused on different implementations for the data structure that holds the "active states", i.e., the states from which we intend to continue searching for a solution. As you discovered, if you use a stack, you get depth-first search; if you use a queue, you get breadth-first search; and if you use a priority queue, you get best-first search.

In this project, we'll focus on the other important data structure in the Universal Problem Solver: the seenStates dictionary. This is a dictionary or set ADT, used to keep track of whether the solver has seen a state previously. If so, the solver skips putting that state into the activeStates; this prevents the solver from getting stuck in an infinite loop, because we'll never try to explore the same state more than once. In addition, the seenStates dictionary is used to keep track of how we got to each state: each state keeps track of its predecessor, so that when the solver eventually finds a solution, it can follow the trail of predecessors back to the start state, thereby spelling out a step-by-step solution to the puzzle.

For Project 1, we provided a very simple implementation of this dictionary, as a linked list. Not surprisingly, it's called LinkedListDict. For this project, your job will be to write 3 new dictionary implementations (AVL Tree, Hash Table with Linear Probing, Hash Table with Double Hashing), and compare their performance to the LinkedListDict.

We'll stick with the Slider Puzzle, because it was the hardest puzzle to solve in Project 1. That means we'll also have to stick with best-first search. You are welcome to play with the other puzzles from Project 1 (or write your own!), but for the experiments in this project, you must use the new, improved VectorPriorityQueue that we supply.

We have also provided you with a new implementation of the LinkedListDict. This is much faster than before, but it's asymptotically still Theta(n) average case for find(). Important: Notice what we did in LinkedListDict and make sure that your dictionary implementations similarly call getUniqId() exactly once per call to find() or add(). If you don't do this, your code will be much slower than necessasry.

Assignment

1. Get the supplied project files (see below), similarly to how you did it for Project 1. Be sure to use the newer versions (the ones supplied in Project 2, not the ones from Project 1) of VectorPriorityQueue.*, LinkedListDict.*, and solve.cpp.
2. Build the solve program ("make solve") using VectorPriorityQueue and LinkedListDict and experiment with some timings. See the HANDIN.TXT file for specific questions. Marvel at how much faster my newer code runs!
3. Fill in the missing code in AVLDict.hpp and AVLDict.cpp to implement the AVL Tree class. You can search for the string "TODO" in the source files to find places you need to add code, but you might have to add code elsewhere to get things to work. Your implementation must be from scratch, not using any C++ STL libraries. You might want to modify code from your labs, though, and that's allowed. You must use the rotate_left and rotate_right functions we have named (but that you'll complete), and you must not modify any of the tracing code that's labeled "DO NOT CHANGE". When you implement double rotations, you must perform them using our single rotation functions (again, similarly to how it was done in your lab).

   You should also notice that find() keeps track of how deep it goes each time it is called, and it records statistics in an array depth_stats. Notice how it does this, as you will need to track how many probes you make when doing find() in your hash table implementations.

4. Fill in the missing code in LinearHashDict.hpp and LinearHashDict.cpp to implement a hash table with linear probing. We have supplied less skeleton code here, so you'll have more work to do. Your implementation must be from scratch, not using any C++ STL libraries (in particular, you may not use STL hashtable functions, nor the STL vector class). Do not modify any of the tracing code that's labeled "DO NOT CHANGE". Also, do not modify the hash function, nor the list of primes.

   You will also need to add code to find() to count how many probes are needed, and to update the statistics in the probes_stats array. This will be similar to how it's done in the AVLDict code.

   At the beginning of your add() function, you should check if the add will push the load factor over 1/2; if so, add() should call rehash() to rehash into the next bigger sized hash table before performing the insertion.

5. Fill in the missing code in DoubleHashDict.hpp and DoubleHashDict.cpp to implement a hash table with linear probing. You'll find that this is very similar to LinearHashDict, so do that first and make sure you have it fully debugged, and then you can re-use almost all of that code for DoubleHashDict. The same rules about the implementation apply.

You also must answer some questions in the HANDIN.txt file.

Important marking constraints: We will mark your code semi-automatically. Therefore, you must ensure that your code will compile and link correctly by simply running make on the ugrad Linux servers, with our supplied Makefile. Also, your code must respect the supplied interface types, with no modifications. And do not modify the tracing code marked with "DO NOT CHANGE".

You are responsible for deallocating any memory that you allocate. (The rule of thumb is: if you create something with new, you should destroy it with delete when you've finished with it. If you used new with brackets to make an array, use delete [] rather than just delete.)

Teams

You may work on a team of at most two on this assignment, subject to the course's Academic Conduct policy, and we strongly encourage that you do so. We recommend that you work (literally) together as much as possible, but you may choose how to divide the work under three conditions: (1) document each team member's effort in the HANDIN.txt file; (2) work together on and both understand your HANDIN.txt; (3) understand how your team member's code is structured and why it works. Remember to test your team's code as an integrated whole! Except in extreme cases, all team members will receive the same grade for the project. Check out All I Need to Know about Pair Programming I Learned in Kindergarten for advice on working in a pair.

What we've provided

As a starting point we've provided some files:

Makefile

The command make will use this to build your program. You should not need to modify the makefile, even if you add new .cpp and .hpp files. DO NOT MISS the following commands: make handin-proj2 hands in your final project 2 submission (run early and often). These commands must be executed on our undergrad linux servers, in a directory that contains the relevant HANDIN.txt, and various .cpp and .hpp files you wish to hand in.

HANDIN.txt

Key documentation file for your final submissions. Read it and fill in the TODO items! Also, answer the questions there.

solve.cpp

This is the main code that solves the puzzles. You will edit this code to choose what kind of puzzle to solve, set up the initial configuration, and select which search strategy and dictionary implementation to use. You'll make a only few changes to it to select different puzzle sizes and data structrues..

BagOfPuzzleStates.hpp

This is exactly the same as it was in Project 1.

VectorPriorityQueue.hpp, VectorPriorityQueue.cpp

An improved, but still naive implementation of a priority queue that scans the unsorted array looking for the min on every remove operation. You'll use this unmodified.

PredDict.hpp

This defines the abstract type which the dictionaries must implement.

LinkedListDict.hpp, LinkedListDict.cpp

An improved, but still naive implementation of a dictionary that scans the linked list for each find operation.

AVLDict.hpp, AVLDict.cpp

Skeleton code for the AVL Tree class. Implement it!

LinearHashDict.hpp, LinearHashDict.cpp

Skeleton code for the hash table with linear probing. Implement it!

DoubleHashDict.hpp, DoubleHashDict.cpp

Skeleton code for the hash table with double hashing. Implement it!

PuzzleState.hpp

An abstract class to represent a puzzle configuration.

SliderPuzzle.*, etc.

Code that implements the PuzzleState interface, and lets us solve different puzzles using the same code for the rest of the program.

~cs221/assignments/project2

Copy them all by by changing directory (using the cd command) into your project2 directory and running:

cp -R ~cs221/assignments/project2/* .

Type make in that directory, and then run the solve program. Start playing with solve.cpp.

Milestone

We'll try not having a milestone, but treat the task of copying/downloading the files, getting them to compile, and getting timings with LinkedListDict to be a personal milestone. Try to get that done ASAP. Don't put this project off to the last minute!

Final Submission

You are required to hand in your project2 directory with your implementations of the Dictionary ADT. Included in this directory should be at least these files:

• AVLDict.{hpp,cpp}, LinearHashDict.{hpp,cpp}, DoubleHashDict.{hpp,cpp},
• Your completed HANDIN.txt file

You should not need to hand in changes to any other files in the project.

Turn your files in electronically using handin, by running make handin-proj2.

Checking Your Stats:

If you want to check whether your probe-counting code is working correctly, here are the number of probes you should see when running on the 3x3 slider puzzle.

For the LinearHashDict:

0: 329
1: 64
2: 40
3: 13
4: 3
5: 8
6: 1
7: 3
8: 1
9: 0
...

For the DoubleHashDict:

0: 324
1: 82
2: 43
3: 5
4: 7
5: 0
6: 1
7: 0
...