CMSC--202 , Section 1 Computer Science II for Majors
Fall 1997 6 September 1997 Homework 2

Assigned: 16 Sep
Due Date: 28 Sep
Late Date: 30 Sep

This assignment will give you some experience thinking about and writing recursive functions. You will also be introduced to command-line arguments. An important feature of the assignment is:

You may not use any iteration constructs.

Assignment

Write a C program that searches for ``anagrams'' in a dictionary. An anagram is a word obtained by scrambling the letters of some string. For example, the word ``pot'' is an anagram of the string ``otp.'' The program takes two command line arguments:

1. the string from which to make anagrams, and
2. the name of the file containing a dictionary of words.

For example, to list the anagrams of ``otp'' that are in the file /usr/lib/dict/words, you would type:

    hw2 otp /usr/lib/dict/words

Purpose of the Assignment

Since the purpose of this assignment is to give you experience using recursion, you may not use any of C's iteration constructs (do, while, for, and goto). All repetition must be accomplished using recursion. This applies to every operation in the program, even file operations.

Error Checking the Command Line

The program should terminate after issuing an error message if the command line

1. does not contain exactly two arguments, or
2. the file named in the second argument cannot be opened for reading.

File Structure

Your program must be organized in a modular way. It must be segmented into multiple files. The main function should appear (with little else) in its own file (suggestion: name it hw2.c). Other functions must be declared in an appropriate interface file (for example, hw2_aux.h) and be defined in a corresponding implementation file (for example, hw2_aux.c). The interface files must be guarded.

Makefile

Write a makefile which causes correct compilation of your homework You may name your files as you wish (suggestions were given above), but the executable must be named hw2. Your makefile will be used to compile your submitted code, so be sure it works. A simple makefile which just does the compilation is fine.

Hints

A sample main file is given in Section 9. A sample interface file is given in Section 10. The Roberts text ``Programming Abstractions in C,'' Section 5.2, discusses a method for permuting the characters in a string. The function RecursivePermute provides a model for you. However, RecursivePermute uses iteration (a for loop), which this assignment does not allow. Suppose you have a for loop of the form:

   for (i = initval; i < maxval; i++)
      {
        statement;
      }

Consider the following recursive function:

    void Loop(int i, int max)
     {
        if (i >= max)
          return;
        statement;
        Loop(i + 1, max);
     }

You can replace the for loop above with the following invocation of Loop:

    Loop(initval, maxval);

Submitting the Homework

You must submit the following files:

1. the ``main function'' file,
2. all of your interface files,
3. all of your implementation files, and
4. your makefile.

To submit the files, use the submit program. For example, to submit the files hw2.c and hw2_aux.c, enter
submit cs202_01 hw2 hw2.c hw2_aux.c

Due Date

The homework is due on 28 Sep . Submittals received by midnight of the due date will receive some bonus credit. There is an automatic extension of two days, so submittals received by midnight of 30 Sep will receive full credit. No submittals will be accepted after 30 Sep .

Sample Main File

/*
  hw2.c
  Main function
  CMSC-202  Fall 1997  Homework 2
  Thomas Anastasio
  Created: 5 September 1997
  Current: 5 September 1997
*/

#include "hw2_aux.h"
#include <stdio.h>

int main(int argc, char * argv[])
{
  dict_type dict;   /* the dictionary */
  FILE *dictfile;   /* file containing the list of words */
  int nwords;   /* number of words read from dictionary */

  CheckCommandLine(argc);
  dictfile = GetDictFile(argv[2]);
  nwords   = ReadDictionary(dictfile, dict);
  
  if (RecursivePermute(argv[1], dict, nwords) == 0)
    printf("No matches found\n");
}

Sample Interface

/*
  hw2_aux.h
  Interface for auxiliary functions for HW 2
  CMSC-202  Fall 1997  Homework 2
  Thomas Anastasio
  Created: 5 September 1997
  Current: 6 September 1997
*/

#ifndef HW2_AUX_H
#define HW2_AUX_H

#include <stdio.h>

#define TRUE        1
#define FALSE       0

#define MAXWORDLEN    30     /* dictionary word max length */
#define MAXWORDS      19000  /* max no of valid words to read */

/* Type definitions */
typedef char word_type[MAXWORDLEN + 1];
typedef word_type dict_type[MAXWORDS];

/**** Function Declarations  ****/

/* CheckCommandLine
 * Issues an error message and exits if argc is not precisely 3
 * (i.e. there are not precisely 2 command line arguments).
 */
extern void CheckCommandLine(int argc);

/* RecursivePermute
 * Permutes the characters in str, and prints (to stdout) each
 * permutation found in dict. dict has dictsize words in it.
 * Returns the number of permutations of str that were found in dict.
 */
extern int RecursivePermute(char str[], dict_type dict, int dictsize);

/* GetDictFile
 * Opens (for reading) and returns file pointer if filename exists, 
 * else issues error message and exits.
 */
FILE * GetDictFile(char filename[]);

/* ReadDictionary 
 * Reads the already opened dictfile into dict.
 * Only valid words (cf. is ValidWord) are read. 
 * Returns the number of valid words read.
 */
extern int ReadDictionary(FILE * dictfile, dict_type dict);

/* isValidWord
 * Returns TRUE if word is a valid dictionary word, FALSE otherwise.
 * Valid means:
 *  no longer than MAXWORDLEN long
 *  contains only characters   'a' through 'z'
 */
extern int isValidWord(char * word);

#endif

Example

  Here is an example of how your program should work

umbc9 [501]: hw2 ipns /usr/lib/dict/words
   spin
   snip
umbc9 [502]: hw2 ipns 
>>  Usage:  hw2 string filename
umbc9 [503]: hw2 foo /usr/lib/dict/words
>>  No anagrams found
umbc9 [504]: hw2 foo bar
>>  Could not open dictionary file bar