Description

Weight: (80 * 0.20) % [Assignment 2 of 4]
—————————————————————————————————————————–
Collaboration
IMPORTANT
1. Collaborative coding is strictly prohibited. Your assignment submission must be strictly your code. Discussing anything beyond assignment requirements and ideas is a strictly forbidden form of collaboration. This includes sharing code, discussing code itself, or modelling code after another student’s algorithm. You can not (even with citation) use another student’s code.
2. Discuss and share ideas with other programmers as much as you like, but make sure that when you write your code that it is your own. A good rule of thumb is to wait 20 minutes after talking with somebody before writing your code. If you exchange code with another student, write code while discussing it with a fellow student, or copy code from another person’s console, then this code is not yours.
4. Cite all sources of code that you hand-in that are not your original work. You can put the citation into comments in your program. For example, if you find and use code found on a web site, include a comment that says, for example:
# the following code is from https://www.quackit.com/python/tutorial/python_hello_world.cfm.
Use the complete URL so that the marker can check the source.

Late Penalty:

LATE ASSIGNMENTS WILL NOT BE ACCEPTED

Goal

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 “CPSC319S21A2″ and will be called from the command line as follows
$ java CPSC319S21A2 file

where file is a file containing a list of words to be sorted into anagrams and is read by the program through standard input. The number of words in the input is arbitrary. The 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. exactly one space between words on the same line, and
3. no other spaces.

For example, this input text file:

car
mega bed stop game pots arc tops  Should yield the output text:

arc car
game mega pots stop tops bed

Note that the input can be large. Some test files will be available on the course website.

The Algorithms

You are required to use 1-D arrays and singly linked lists in your program to deal with the arbitrary number of words in the input as follows:

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

LIST A
0 car
1 mega
2 bed
3 stop
4 game
5 pots
6 arc
7 tops
 1-D array of words

Input text file

is not a must)

0 arc
1 bed
2 car
3 game
4 mega
5 pots
6 stop
7 tops
n be sorted (example): (It
LIST A

Sorted 1-D array of words
Step #3. A new LIST B should then be created directly from LIST A (i.e., the sorted 1-D array of words, step #2) as follows (example):

car
0 


 arc
1 bed
2 game
3 pots
mega
stop
tops
  NULL

 NULL

  NULL

   NULL

LIST B

1-D array of singly linked lists

LIST B is a 1-D array storing, at each array entry, a singly linked list of all the anagrams found in the sorted LIST A (step #2) – i.e., (arc, car), (game, mega), (pots, stop, tops) – as well as any remaining word(s) with no anagrams found in the sorted LIST A (step #2) – i.e., (bed).

Note: all the words in each of the singly linked lists are stored in alphabetical order and subsequently stored at each array entry also in alphabetical order – e.g., note the first word at LIST B [0]  (arc, car), LIST B [1]  (bed), LIST B [2]  (game, mega), and LIST B [3]  (pots, stop, tops). This is achieved by structuring LIST B (i.e., both 1-D array and singly linked lists) directly from LIST A which is sorted already (i.e., step #2). Step #4. Traverse LIST B to generate the required output text format (refer to previous page).

arc car
bed 
game mega
pots stop tops
Output text

Sorting is not mandatory. But it would make your output elegant and increase understanding.

Finding Anagrams: 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:

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

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

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

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

‘o’ ‘p’ ‘s’ ‘t’
0 1 2 3
After sorting
⎯⎯⎯⎯⎯⎯⎯⎯⎯>

After sorting
⎯⎯⎯⎯⎯⎯⎯⎯⎯>

After sorting ⎯⎯⎯⎯⎯⎯⎯⎯⎯>

Instructions
1. Write the program described above.

Hand-In (digitally to D2L dropbox)
1. Your source code file that generates the output in the form requested. The README file should include description of which class begins execution of your submitted code. For example, “CPSC319S21A2.java” is my main class and should be executed.
2. Include all of the above items in a zipped folder (standard ZIP) titled CPSC319S21A2-LASTNAME-ID.zip before submission to the D2L dropbox for assignment 2.

Grading
• Assignment grades will be base equally on the submitted components as described on grading summary

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

• Code that produces incorrect output (Ex. wrong format of output) will be penalized appropriately.

GRADING SUMMARY

PROGRAM: /40

Name:

ID:

PROGRAM

Program builds correctly Yes No
Runs: completes with zero run-time errors Yes No
IMPORTANT: Source code that does not compile or produces run-time errors will receive 0%

Criteria TOTAL
Functionality: produces correct output (28 Marks)
Readability: code is clear and easy to read (3 marks)
Modularity: code is easy to extend, or use (3 marks)
Generality: easy to extend to more sophisticated applications (3 marks)
Documented: code classes/functions/inline commented (3 marks)
TOTAL: /40