-
Notifications
You must be signed in to change notification settings - Fork 0
/
assignment#2.html
366 lines (352 loc) · 25.8 KB
/
assignment#2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="content-type"
content="text/html; charset=ISO-8859-1">
<title>assign2</title>
</head>
<body style="color: rgb(0, 0, 0);" link="#0000ee" alink="#0000ee"
vlink="#551a8b">
<p class="MsoNormal" align="center" style="text-align: center;"><b
style=""><u><span style="font-size: 12pt;">Department
of Computer Science.<o:p></o:p></span></u></b></p>
<p class="MsoNormal" align="center" style="text-align: center;"><st1:place><st1:PlaceName><b
style=""><u><span style="font-size: 12pt;">Georgia</span></u></b></st1:PlaceName><b
style=""><u><span style="font-size: 12pt;"> </span></u></b><st1:PlaceName><b
style=""><u><span style="font-size: 12pt;">State</span></u></b></st1:PlaceName><b
style=""><u><span style="font-size: 12pt;"> </span></u></b><st1:PlaceType><b
style=""><u><span style="font-size: 12pt;">University</span></u></b></st1:PlaceType></st1:place><b
style=""><u><span style="font-size: 12pt;"><o:p></o:p></span></u></b></p>
<p class="MsoNormal" style="text-align: left;"><b style=""><span
style="font-size: 12pt;">
CSc 3410<span style="">
</span>J. L. Bhola<o:p></o:p></span></b></p>
<p class="MsoNormal" align="center" style="text-align: center;"><b
style=""><span style="font-size: 12pt;">Fall 2010 -
Assignment #2<o:p></o:p></span></b></p>
<p class="MsoNormal" align="center" style="text-align: center;"><b
style=""><span style="font-size: 12pt;">Due </span></b><st1:date
year="2001" day="19" month="9"><b style=""><span
style="font-size: 12pt;">September 15<sup>th</sup> and September
16<sup>th</sup>
2010</span></b></st1:date><b
style=""><span style="font-size: 12pt;"><o:p></o:p></span></b></p>
<p class="MsoTitle" align="left" style="text-align: left;"><u
style="font-weight: bold;">Note:</u><span style="font-weight: bold;"> </span>(1)
For all
assignments, always use comments to explain your program. </p>
<p class="MsoTitle" align="left" style="text-align: left;"><span
style=""> </span>(2)
No copying allowed. If it is
found that students copy from each other (in the opinion of the
instructor), all of these programs will get 0.<br>
</p>
<p class="MsoTitle" align="left"
style="margin-left: 30pt; text-align: left;"><!--[if !supportLists]--><span
style="">(3)<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span><!--[endif]-->You must use the names given to name your
program.
Should you use different names, <u>you would lose 10%
of what each program is worth</u>.</p>
<p class="MsoNormal" align="center" style="text-align: center;"><b
style=""><span style="font-size: 12pt;"><o:p> </o:p></span></b></p>
<p class="MsoNormal"><b style=""><u><span style="font-size: 12pt;">Objectives:<o:p></o:p></span></u></b></p>
<p class="MsoNormal"><b style=""><u><span style="font-size: 12pt;"><o:p></o:p></span></u></b></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">1.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">To
gain experience with
string objects.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">2.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">To
gain experience with
vectors.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent:
-0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">3.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">To
gain experience with
generic algorithms.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent:
-0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">4.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">To
gain experience with files - opening for input
and output.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<u><b> Documentation:</b></u><p>
<ol>
<li>Explain the purpose of the program as detail as possible -<b>
13%.</b>
<li>Develop a solution for the problem and mention algorithms to be
used -<b>16% </b>
<li>List data structures to be used in solution. - <b>5%.</b>
<li>Give a description of how to use the program and expected
input/output - <b> 5%</b>
<li>Explain the purpose of each class you develop in the program. -
<b>5%.</b>
</ol><p>
<u><b>Programming:</u></b><p>
<ol>
<li>For each method, give the pre and post conditions and invariant,
if any - <b> 10%</b>
<li>Program execution <b><u>according to the requirements given
</u></b> <b> 36%</b>
<li>Naming of program as required
<b> 5%</b>
<li>Print out of source code
<b> 5%</b>
</ol>
<p class="MsoNormal"><b style=""><u><span style="font-size: 12pt;">Description
of program:<o:p></o:p></span></u></b></p>
<p class="MsoNormal"><b style=""><u><span style="font-size: 12pt;"><o:p></o:p></span></u></b></p>
<p class="MsoBodyText">You are to write a program name anagram.java that prompt
the user for a user input file, reads the input words and computes anagram
of words. An anagram of a word is a permutation of the letters in that
word;
for example, “stop” is an anagram of “tops”.</p>
<p class="MsoNormal"><span style="font-size: 12pt;">As indicated, the
input to the program is a list of words from a <span
style="font-weight: bold;">user input file</span>. The output is a list
containing the same words, but with anagrams displayed on the same line both
on the screen and the output file. The output file must be named <b>
output.txt.</b><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">The input file, may look like the
following: <span
style="font-weight: bold; text-decoration: underline;">You must prompt
the user for the name of the input file.</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Pans naps<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Pots<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">opt this that<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Sit<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">it’s<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">snap<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">and
so on.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><span
style="font-weight: bold; text-decoration: underline;">Execute
the program, example:</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">C:\>java anagram
<b><u>OR</u></b> C:\java -jar anagram.jar
[Enter]
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p><span
style="font-weight: bold;"> Enter the name of the input
file: input.dat </span>[Enter]<br>
</o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Pans
snap<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Pots<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Sit
it’s<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">opt<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><span
style="font-weight: bold; text-decoration: underline;">Here
are some requirements for the program:</span><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">1.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">When
determining if two words
are anagrams, the program must treat upper and lower case letters as
equivalent
(thus “Pans” and “snap” are anagrams) and ignore punctuation marks
(“it’s” and
“Sit” are anagrams). However, the program must display words with their
original capitalization and punctuation – as shown above. <o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">2.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">The
“word” is assumed to be
any series of nonblank characters; words may be separated by any number
of
white-space characters. Any number of words may appear on a
line, <br>
including
none. You may assume that no word is more than 12 characters long. And
maximum
number of words would be 50.<span style=""><br>
</span></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><span
style="font-size: 12pt;"><span style="">3.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">The
program must work even
if the input file is empty. If this is the case print a message saying
that “<b style="">the input file is empty</b>” and then
terminate the program.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">4.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">The
program must test the
number of characters per word. If a word consist of more than 12
characters,
the program should ignore that word and continue. That word would also
be
ignored in the total number of words of 50.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="font-size: 12pt;"><span style="">5.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span><!--[endif]--><span style="font-size: 12pt;">The
program must also test
the number of words. If there are more than 50 words, print a message
saying
that “<b style="">there are more than 50 words in
the input file</b>” and then terminate the program<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><b style=""><span style="font-size: 12pt;">Algorithm:<o:p></o:p></span></b></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoBodyText">Use efficient algorithms. The first insight is
to create a
“signature” for each word by sorting the letters in the word
after removing punctuations..</p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p> </o:p></span></p>
<h1><small><small><small>Original Word</small></small></small><span
style=""><small><small><small> </small></small></small>
</span><small><small><small>Signature</small></small></small></h1>
<p class="MsoNormal"><span style="font-size: 12pt;">Pans<span style="">
</span>anps<o:p></o:p></span><small style="font-weight: normal;"><small><br>
<big><big><big>Pots</big></big></big></small></small><span style="">
</span><big><big><big><span
style=""></span></big></big>opts</big><br>
<span style="font-size: 12pt;">opt<span style="">
</span>opt<o:p></o:p><br>
Sit<span style="">
</span>ist<o:p></o:p><br>
it’s<span style="">
</span>ist<o:p></o:p><br>
snap<span style="">
</span>anps<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Upper
case are converted to lower case and <b style="">non-alphabetic
characters</b> (eg. <b style="">/<>[{</b>) are
removed before the signature is computed. Punctuation marks are also
ignored
when computing signatures.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Creating
signatures for words makes it easy to check whether two words are
anagrams.
However, we still have the problem of (apparently) having to compare
every
input word against every other input word. Actually, all we need to do
is sort
the <b style="">lines</b> by their signatures.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p> </o:p></span></p>
<h1><small><small><small>Original Word</small></small></small><span
style=""> </span><small><small><small>Signature</small></small></small></h1>
<p class="MsoNormal"><span style="font-size: 12pt;">Pans<span style="">
</span>anps<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">snap<span style="">
</span><span style=""> </span>anps<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Sit<span style="">
</span>ist<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">it’s<span style="">
</span>ist<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Pots<span style="">
</span>opts<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">opt<span style="">
</span>opt<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">We
next make a pass over from top to bottom, printing the original words.
The
words that have the same signature are anagrams, so we print them on
the same
line:<o:p><br>
</o:p><br>
Pans
snap<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Pots<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">Sit
it’s<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;">opt<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p> </o:p></span></p>
<p class="MsoNormal"><b style=""><span style="font-size: 12pt;">Implementation:<o:p></o:p></span></b></p>
<p class="MsoBodyText">Use as many generic algorithm as possible so
that the size
of the program can be reduced.</p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal" align="center" style="text-align: center;"><b
style=""><u><span style="font-size: 12pt;">What to
turn in:<o:p></o:p></span></u></b></p>
<p class="MsoNormal"><span style="font-size: 12pt;"><o:p></o:p></span></p>
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoBodyText2"
style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><span
style="">1.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span><!--[endif]-->A 3.5 inches floppy disk (IBM compatible)or a Flash drive
consisting of
all of the .java and the<span style=""> </span>.class/jar files. <u>M<span
style="font-variant: small-caps;">AKE SURE THAT YOUR DISK IS VIRUS
CLEAN.</span><o:p></o:p></u></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]-->
<span style="font-size: 12pt;"><span style="">
2.<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal;
font-size-adjust: none;"> </span></span><!--[endif]-->
<span style="font-size: 12pt;">A print out of each of the<span style="">
</span>.java file (source code).<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]--><b
style=""><span style="font-size: 12pt;"><span style="">3.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal;
font-size-adjust: none;"> </span></span></span></b><!--[endif]--><span
style="font-size: 12pt;">Make sure that your name is written clearly both on the print out and
the disk.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><!--[if !supportLists]-->
<b style=""><span style="font-size: 12pt;"><span style="">4.<span
style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-stretch: normal; font-size-adjust: none;">
</span></span></span></b><!--[endif]--><span
style="font-size: 12pt;">Make sure that both the .java and .class/jar files
are on the root directory i.e. on the a:\<span style=""> </span>drive. Example:<span
style=""> <br> </span></span></p>
<p class="MsoNormal" style="margin-left: 0.25in; text-indent: -0.25in;"><b
style=""><span style="font-size: 12pt;"><span style="">
</span>a:\anagram.java<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left: 0.25in;"><b style=""><span
style="font-size: 12pt;"><span style="">
</span>a:\anagram.class<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left: 0.25in;"><b style=""><span
style="font-size: 12pt;"><o:p> </o:p></span></b><span
style="font-weight: bold;">
<span style="text-decoration: underline;">AND</span></span><br>
</p>
<p class="MsoNormal" style="margin-left: 0.25in;"><b style=""><span
style="font-size: 12pt;"><span style="">
</span><span
style="">
</span>a:\anagram.java <b><u>OR</u></b> a:\Main.java<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left: 0.25in;"><b style=""><span
style="font-size: 12pt;"><span style="">
</span>a:\anagram.jar
<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left: 0.25in;"><b style=""><span
style="font-size: 12pt;"><span style="">
</span><o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left: 0.25in;"><b style=""><span
style="font-size: 12pt;">Should you use
any subdirectory (whatsoever) your program would not be graded and you
will
receive a 0 (zero).<o:p></o:p></span></b></p>
</body>
</html>