EECS 311: DATA STRUCTURES

Assignment 1

Goal

The goals of this assignment are:

Task

There are three parts to this assignment:

Pair-programming is allowed but only if it is true pair programming, i.e., coding done by both partners together, on one computer, switching every 20 minutes or so. The analyses should be done individually.

Boggle™ Problems

A Boggle™ grid is just a square grid of letters. Real games use a 5 x 5 grid, but 3 x 3 and up are possible. The goal of the game is to find as many words as possible in the grid. Words must be formed from letters in adjacent positions. Because diagonals are allowed, quite a few words can be formed, even in a 3 x 3 grid. Here's an example, using the words in crosswd.txt:

GridWords in grid
mmg
eus
kde
des, due, dues, dug, dugs, duke, ems, emu, emus, gude, gudes, gum, gummed, gums, kue kues, mem, mems, mud, muds, mug, mugs, mum, mums, mus, muse, mused, sedum, smug, sue sued, suede, sum, summed, uke, use, used

If interested, the complete rules are here. There's a page that generates 4x4 Boggle™ grids if you want to try your hand at them.

You can use any algorithm you want to find words, efficient or not, but you have to be able to analyze the time and space requirements of whatever algorithm you choose. Here are two possible simple but dumb algorithms:

Notice that the same word may appear in multiple positions, but duplicates don't count.

Make no assumptions about the size of the dictionary, the size of the grid, or maximum word length, though note that the rules of Boggle™ place a word length limit for a given grid size.

Analyze your algorithm

Do as formal an analysis of the upper and lower complexity bounds of your algorithm as you can, in terms of the size of the puzzle, the size of the word list, the number of solutions present, and so on.

To help me compare analyses, use the following variable names:

Use other variable names as needed. Use "big-Oh" notation, as shown in the book. Include in your analysis the key lines of code that dominate the program run-time.

Obtain empirical results

Create a project directory called boggle. Put your source code and the Magic Makefile in that directory.

Input

Use crosswd.txt from the Moby Project as your word list.

Classes

Define a class Boggle with the following member functions:

Example usage:

Test(mmgeuskde)
{
  Boggle boggle("crosswd.txt");
  CHECK_EQUAL( 14, boggle.solve("mmgeuskde");
}

Test(random3x3)
{
  Boggle boggle("crosswd.txt");
  std::string grid = boggle.randomGrid(3);
  CHECK_EQUAL( 9, grid.length() );
  std::cout << grid << " has " << boogle.solve(grid) << " words" << std::endl;
}

Testing

Put tests in your code to theake sure your code gets the answers shown in pa1-test1.txt and pa1-test2.txt. Each file contain a grid, as a single word string, followed by all the words in that grid.

To generate random grids of different sizes, make matrices and fill them with characters randomly selected from this string:

aaaaaabbccdddeeeeeeeeeeeffgghhhhhiiiiiijkllllmmnnnnnnoooooooppqrrrrrssssssttttttttuuuvvwwwxyyyz

This string has the same mix of letters as Boggle™ dice and generates grids with many solutions on average. (Boggle™ treats the letter 'Q' specially but we won't worry about that.)

Output

Your program must run standalone, with no user input of any kind. That includes not stopping at the end with a "hit any key to continue" message. If your program can't be run automatically from a script, it will be returned.

Your program should

Then your program should print the results (as described below) for

Results to calculate and print:For each grid, print

input Ksmall Tsmall Khalf Thalf Kfull Tfull

where input is the input grid, as a single word, Ksmall is the number of words found for the small word list, Tsmall the time it to to find those words, and similarly for the half-size and full-size word lists. Print runtime in seconds to three decimal places. Put the results for each grid on a separate line, e.g.,

uaesotwislfntebg 26 .203 53 .438 151 1.843

Do not include the time to read the dictionary file, generate a random board, or print the results in your runtime.

Compare

How does your program behavior actually perform with word lists and grids of different sizes? Compare your theoretical predictions to your empirical results. Ideally they should match, but don't claim a match that isn't there. It's better to recognize mismatch than to fudge or misread the data.

Additional Requirements

You can organize your code into multiple .cpp and .h files, if that makes sense, but be sure to define main() in a file called main.cpp.

Store the grid using the book's matrix class, which is available online. Use appropriate data structures to store the dictionary and results.

What to Hand in

Use your Makefile to create a Zip file with your source code.

make handin

Create a text document with your algorithmic analysis and comparison to the empirical results.

Email both as attachments to me with the Subject line EECS 311 PA1.

Be sure your main.cpp file has an opening header comment of the following form:

// EECS311 PA1 solution: Brute-force approach to solving Boggle
// Date: September 30, 2009
// Authors: T.H.E.Hacker
// 
// Except for code provided by the instructor or textbook, this code was written
// solely by the authors listed above, and not copied from another student
// or external source.

Valid HTML 4.01 Strict