EECS 311: DATA STRUCTURES Home Course Info Links Grades Lectures Newsgroup Homework Exams

# Assignment 1

## Goal

The goals of this assignment are:

• Set up your C++ programming environment, with UnitTest++ and make
• Practice with C++ containers, like vectors and sets, and the book's `matrix` built on top of vectors
• Do some basic algorithm design and analysis in the context of a potentially combinatoric problem.

There are three parts to this assignment:

• Write and test a program to solve Boggle™ problems
• Analyze the mathematical complexity of your algorithm.
• Compare the formal analysis with empirical results.

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:

• For each word in the word list, see if it appears in the grid.
• For each position in the grid, find all the words, if any, that can be formed by some path from that position.

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.

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:

• N -- the size of the word list
• M -- the size of the grid, e.g., 3 for a 3x3 grid
• K -- the number of answers found for a grid
• L -- the average answer length for a grid
• T -- the time to solve a grid

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:

• Boggle::Boggle(std::string) -- given the name of word file, the constructor should read this file into a data structure.
• int Boggle::solve(std::string) -- given a grid as a simple linear string, this function should return the number of distinct words found in the grid.
• std::string Boggle::randomGrid(int) -- given a grid size N, this function should return a grid represented as a string of N squared randomly generated letters.

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:

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.

• read the word list file, just once, and generate 3 internal word lists:
• a small list with the first 25% of the words
• a half list with the first 50% of the words
• a full list with all the words

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

• "esaopfkov" and 3 randomly generated 3x3 grids
• "naovhnochswieaii" and 3 randomly generated 4x4 grids
• "eqttumenostsrsdsadfdogatd" and 3 randomly generated 5x5 grids
• "ceiliokatcdrlswehnitvtihvvyuaruzvtlb" and 3 randomly generated 6x6 grids

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.

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.
```