Project #3

Due Dates: Saturday, November 4 at 11:59pm

Submit: eLearning

Late Policy: -10 points per hour late

Instructions: This is an individual assignment. All work should be your own.

Objectives:

Create a hash table. Use the hash table to solve a word puzzle.

Description:

The word puzzle is described in section 1.1 in the textbook and discussed further at the end of chapter 5.

A grid consisting of letters is to be checked against a dictionary of words to see if the grid contains any of the words.

The user can input a value for the rows and columns of the grid and the program will create a grid of random characters.

The program will read in a dictionary file (provided) and use an algorithm to solve the word puzzle.

The hash table should be a linear probing hash table of your own creation, not copied other sources. You should design and code it yourself. You can use code from the QuadraticProbingHashTable given in the text if you wish.

The program should use the algorithm described as the "second" algorithm in 1.1, which checks each word in the grid for presence in the dictionary.

The user should also have the option of using the following enhancement: When reading the input file of words, store each prefix of the word as well. For example, if the word is "apple", store "a", "ap", "app", "appl", "apple". In the algorithm, if a prefix is not found, the rest of this string can be treated as "not found". For example, if the string is "apbum", and after checking and finding "a" and "ap" I find that "abp" is not in my dictionary, then there is no point in checking further in this direction. Note you will need to indicate for each entry whether it is a word or only a prefix of a word.

Have the program output the elapsed time in both cases.

Submit to eLearning: WordPuzzle.java MyHashTable.java

Chapter 1 Introduction 1 2 3 4 1 t h i s 2 w a t s 3 o a h g 4 f g d t Figure 1.1 Sample word puzzle A second problem is to solve a popular word puzzle. The input consists of a twodimensional array of letters and a list of words. The object is to find the words in the puzzle. These words may be horizontal, vertical, or diagonal in any direction. As an example, the puzzle shown in Figure 1.1 contains the words this, two, fat, and that. The word this begins at row 1, column 1, or (1,1), and extends to (1,4); two goes from (1,1) to (3,1); fat goes from (4,1) to (2,3); and that goes from (4,4) to (1,1). Again, there are at least two straightforward algorithms that solve the problem. For each word in the word list, we check each ordered triple (row, column, orientation) for the presence of the word. This amounts to lots of nested for loops but is basically straightforward. Alternatively, for each ordered quadruple (row, column, orientation, number of characters) that doesnt run off an end of the puzzle, we can test whether the word indicated is in the word list. Again, this amounts to lots of nested for loops. It is possible to save some time if the maximum number of characters in any word is known. It is relatively easy to code up either method of solution and solve many of the real-life puzzles commonly published in magazines. These typically have 16 rows, 16 columns, and 40 or so words. Suppose, however, we consider the variation where only the puzzle board is given and the word list is essentially an English dictionary. Both of the solutions proposed require considerable time to solve this problem and therefore are not acceptable. However, it is possible, even with a large word list, to solve the problem in a matter of seconds. An important concept is that, in many problems, writing a working program is not good enough. If the program is to be run on a large data set, then the running time becomes an issue. Throughout this book we will see how to estimate the running time of a program for large inputs and, more important, how to compare the running times of two programs without actually coding them. We will see techniques for drastically improving the speed of a program and for determining program bottlenecks. These techniques will enable us to find the section of the code on which to concentrate our optimization efforts