CPSC Assignment 1 Searching & Sorting Solution

The goal of this assignment is to write a Java program that arranges a list of words into separate lists of anagrams. Your program should be named “asgmt1" and will be called from the command line. The only input to your program is a file containing a list of words to be sorted into anagrams and is read by your program through standard input. The number of words in the input is arbitrary. Your program should print to standard output the lists of anagrams in the following way:

    1. All the words that are anagrams of each other are printed on one line of output.

    2. The words on each line should be in alphabetic order.
    3. The groups should be ordered alphabetically by the string that results by sorting the characters in each word.

    4. Exactly one space between words on the same line, and no other spaces.


For example, this   
Should yield this
input text file:
output text file:
car
arc car
mega
bed
bed
game mega
stop
pots stop tops
game

pots

arc

tops




Note that the input can be large, so attention to the efficiency of the algorithms is essential. Also, we will grade the program using utilities that compares text files. That is, we will have a large input file with the known correct output. If your output file does not match the correct output, you will lose some marks. You must test your program with 4 test files (available on D2L) as shown in the right:



Input File
Expected Output
example_1--8_words
example_1_out
example_1--13_words
example_2_out
example_1--19_words
example_3_out
example_1--267_words
example_4_out


ALGORITHMS & DATA STRUCTURES



Step #1. The data from the input text file should be structured in a 1-D array of words (example: input text file “example_1--8_words”):



0


car
LIST A


1


mega
1-D array



2


bed










of words
Input


3


stop













4


game

text file

5


pots



6


arc




7


tops




Step #2. “LIST A” should then be sorted:

Finding Anagrams: A good way to determine if two words are anagrams is to sort the letters in both words. If the two sorted words are the same, then the original two words are anagrams. For example, array entries #5, #6, and #7 (i.e., “pots”, “stop”, and “tops”) from the sorted LIST A of words (i.e., step #2) are anagrams:

0
1
2
3

0
1
2
3
‘s’
‘t’
‘o’
‘p’
�⎯⎯⎯⎯⎯⎯⎯⎯⎯�
‘o’
‘p’
‘s’
‘t’
‘p’
‘o’
‘t’
‘s’

‘o’
‘p’
‘s’
‘t’


















0
1
2
3

0
1
2
3




�⎯⎯⎯⎯⎯⎯⎯⎯⎯�













‘t’
‘o’
‘p’
‘s’

‘o’
‘p’
‘s’
‘t’
0
1
2
3

0
1
2
3




�⎯⎯⎯⎯⎯⎯⎯⎯⎯�





IMPORTANT: You should use your own implementation of the sorting algorithm(s) covered in class (e.g., Selection, Bubble, Insertion Sort) You may use our textbook, lecture and tutorial materials or other sources of information as guidance but be sure to cite them. For the required data structure (1-D arrays) you can either use Java classes or implement your own. No hard coding is allowed. You need to have your code explicitly reading the input text files (i.e., Step #1 above), sorting the arrays, and explicitly save the solution (i.e., Step #3 above). Our TAs will assist you with every aspect of the assignment.


HAND-IN


    • Submit your source code electronically to D2L dropbox.

    • Please name your source code file as follows: “asgmt-1-your-last name-UCID”

    • Late assignments will not be accepted.


MARKING

Source code that does not compile or produces run-time errors will receive a grade of 0%

Input File
Expected Output

# Points


for correct output
for partially correct output


(Step #3)
(Step #2)
example_1--8_words
example_1_out
2
1
example_1--13_words
example_2_out
2
1
example_1--19_words
example_3_out
2
1
example_1--267_words
example_4_out
2
1

Total
8
4











2



























3