$35
CPSC319- Assignment 2: Implementation of Lists Solved
Discussing the assignment requirements with others is a reasonable thing to do, and an excellent way to learn. However, the work you hand-in must ultimately be your work. This is essential for you to benefit from the learning experience, and for the instructors and TAs to grade you fairly. Handing in work that is not your original work, but is represented as such, is plagiarism and academic misconduct. Penalties for academic misconduct are outlined in the university calendar.
Here are some tips to avoid plagiarism in your programming assignments.
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.
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.
Everything that you hand in must be your original work, except for the code copied from the textbook, lecture material (i.e., slides, notes), web, or that supplied by your TA. When someone else's code is used like this, you must acknowledge the source explicitly, citing the sources in a scientific way (i.e., including author(s), title, page numbers, URLs, etc.)
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.
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:
all the words that are anagrams of each other are printed on one line of output
exactly one space between words on the same line, and
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
X
Step #2. LIST A may the
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 ⎯⎯⎯⎯⎯⎯⎯⎯⎯>
IMPORTANT: You can use Arrays or ArrayLists, However you should use your own implementation of singly linked lists. You may use our textbook, lecture and tutorial materials or other sources of information as guidance but be sure to cite them. Check with your TA/instructor if you are unsure.
Instructions
Write the program described above.
Hand-In (digitally to D2L dropbox)
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.
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.
