CSE2ALG / CSE5ALG: Algorithms and Data Structures Assignment Part 2, 2021

Department of Computer Science and IT, La Trobe University

Assessment This part of the assignment is worth 15% of the final mark.

Delays caused by computer downtime cannot be accepted as a valid reason for a late submission without penalty. You must plan to allow for both scheduled and unscheduled downtime. Late submission policy does NOT apply to this assessment.

As this part of the assignment is worth 15% or more of the final mark for this subject, please apply for Special Consideration if you need request an extension of time for submission due to any unforeseen circumstances that substantially affect your ability to complete it on time. . Once your application is approved by the University, the subject coordinator will grant you an extension of time for submission.

Plagiarism Plagiarism refers to submitting somebody else’s work in a manner that gives the impression that the work is your own, which is an academic misconduct. The CSIT Department treats academic misconduct seriously. When it is detected, penalties will be strictly imposed

Please make sure you have navigated to in the same directory where the files being submitted are. You must submit each file separately using the submit command submit ALG. For example, if the file is named LexiconTester.java, please use the following command for submission:

After submitting the files, you may run the following command that lists the files submitted from your account:

verify

You can submit the same filename as many times as you like before the deadline. The previously submitted file will be replaced by the latest one. If you encounter any problem regarding submission, please email the subject coordinator for assistance.

Platform While you are free to develop the code on any operating system, your solution must compile and execute using javac and java commands on the latcs8 server.

Return of ResultThe subject coordinator will mark your submission with a marking sheet during the next face-to-face / online lab classes after the deadline (i.e., 25 and 28 May 2021). You will be notified with your mark soon after marking. If you have any doubt, please immediately raise it to the subject coordinator before the lab class ends. Any post-lab inquiry will NOT be accepted. If you cannot attend the lab classes, please email the subject coordinator for an alternative arrangement.

Violating this restriction will lead to a mark of ZERO for this part of assignment.

Marking Criteria You mark for this part of the assignment relates to the program’s capability (i.e., whether being compiling and executing), the program’s efficiency (i.e., how fast it produces the result), the code’s quality (i.e., whether being reasonable and in good style), and the submission’s accomplishment (i.e., whether satisfying the task requirements). Details can be found in the example marking sheet.

Description of Tasks

This part of the assignment is an extension of the part 1. Whereas for part 1 we considered the correctness only, we are concerned with the efficiency for this part.

Specifically, you are required to accomplish the tasks described below. Besides the description below, please refer to the instruction of part 1 for any information you need.

Task 1 Design and implement the program LexiconTester.java. This program will

1. Read one text file using the first command-line argument and construct a lexicon that contains words from the file. Suppose the input the file is  in.txt , the command will execute as follows: java LexiconTester  in.txt 
2. Write the words, including spellings, frequencies and neighbors, from the lexicon to the text file  out.txt . The format must be the same as in the part 1 of the assignment.
3. Include only one solution. It is entirely up to you which data structure(s) and/or sorting algorithm(s) will be used, as long as they are included in the subject; however, you must take the program’s efficiency in consideration, as the test file is much larger in this part.
4. In principle, you program MUST accomplish the task less than 60 seconds on the latcs8 server. Otherwise, your mark will be severely impacted.

Task 2 Write a report  LexiconReport.pdf  in the PDF format. This report will

1. Describe which data structure(s) and/or sorting algorithm(s) are selected; if they are different from those in the part 1, describe the reason for your choice.

2. Describe the time complexities (i.e., the Big-Oh) of the involved data structure(s) and/or sorting algorithm(s) in the best, worst and average cases.

3. Describe any strategies or tricks from you to improve the program’s efficiency in addition to the choice on data structure(s) and/or sorting algorithm(s).