From: Charles Kelemen
Subject: some assignments
For Friday, 12 December 97: Final Project due
Text of Tech report on real paper handed to me or slid under my
office door.
email of source code and test run(s).
--charles
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Final Project
Please work in groups of two on this project. Hand in one
paper with both names on it. Both members of the group will get the
same grade. If you must work alone, it is ok, but you will miss a
valuable experience (and make me look at more papers).
DUE Friday 12 December 97
Final version of the tech report and working ANSI C
implementation of the project. Email me your source code and test
runs. Hand in a real paper copy of your tech report. This can be
handed to me in my office or put under my office door if I am not
there. This is part of the writing expected in a PDC course. Feel
free to make use of the writing center to help you with the prose in
your tech report. Documentation and coding should be done with care.
The Project
(This was inspired by one of the problems in the 1987 ACM
Scholastic Programming Contest.) Write an ANSI C program to produce
an Anagram Dictionary. The program should be well-documented.
An anagram of a word is a different word formed using the same
characters that comprise the original word. For example, the word
BRAINY is an anagram of the word BINARY.
An anagram dictionary showing all words that can be constructed using
a given set of letters is useful for certain kinds of word puzzles and
games. Each entry in such a dictionary contains a key giving a the
set of letters in alphabetic order, and one or more words that can be
formed using the letters found in the key. The anagram dictionary
entry for the key ABINRY might then appear like this:
ABINRY : BRAINY BINARY
For this problem you are to produce an anagram dictionary containing a
given set of words. The words will be in an input file. The input
file will be a text file and the words will be separated from each
other by white space. There will be no duplicate words in the input,
and each word will contain 12 or fewer alphabetic characters.
Your program must produce the anagram dictionary so the keys
themselves are in alphabetic order. Each line of each entry in the
dictionary will contain five anagrams, except for the last line of
each entry, which may contain fewer than five anagrams. The anagrams
in each entry need not be in any particular order. The first line of
each entry will begin with the key, left-justified in a 12 character
field, followed by a colon. Each additional line of each entry will
begin with 13 blanks. The five or fewer anagrams on each line are
displayed left-justified in character fields starting in column 14,
each field preceded by a blank.
For example, if the input data contained the words:
CRAPES
INTEGRAL
RELATING
ESCARP
PACERS
ALTERING
SYZYGY
ALGORITHM
CAPERS
TRIANGLE
MARTLESSNESS
SCRAPE
LOGARITHM
BINARY
SPACER
TRAMLESSNESS
ALERTING
STY
BRAINY
RECAPS
then the corresponding anagram dictionary your program might produce would be:
ABINRY : BRAINY BINARY
ACEPRS : RECAPS SPACER SCRAPE CAPERS PACERS
ESCARP CRAPES
AEELMNRSSSST: TRAMLESSNESS MARTLESSNESS
AEGILNRT : ALERTING TRIANGLE ALTERING RELATING INTEGRAL
AGHILMORT : LOGARITHM ALGORITHM
GSYYYZ : SYZYGY
STY : STY
The technical report
In order to help you understand the process of problem
solving, I want you to describe for me your process of problem
solving. That is, write down the steps you take in coming up with a
solution to this problem. You will probably start by trying to
'break' the problem down into several subproblems or modules. Some
approaches will appear to work better than others. The false starts
and rejected alternate solutions do, in fact, help shape your final
solution. Tell me about your false starts. I want to see your final
solution but I also want to see (and I want you to understand) how you
got that final solution.
In particular, compare and contrast 2 different data structures for
constructing an anagram dictionary. Make any necessary 'sort of
realistic' assumptions needed to answer this question (i.e. complete
the specification of the problem). Do not consider the issue of
external storage. Assume you have lots of internal storage available
(at some expense). One of the data structures you describe may be
naive. The other should show that you learned something in this
course. For each of your proposed data structures, try to give the
expected and worst case running times for constructing the dictionary.
Depending on the data structures you pick, you may not possess the
mathematical tools to compute expected running times. Try to make a
reasonable estimate and explain why you think your estimate is correct
(or close to correct).
so neil epstein and justin hall did this
unix & c | coursework | swat | justin's links