GOAL

The goal of this assignment is to prepare you for assignment 3 which will require you to write a program in a LISP like language which stands for List Processing. These languages generally are built under the functional paradigm class of languages. Functional based languages have immutable types and LISP like languages work on immutable lists and scalars. The restrictions in this document are not to make the assignment harder but to get you thinking in terms of working with lists and scalars and to guide your thinking that will help with the next assignment. Try to focus on coming up with an algorithm first as you should be familiar with Java. If you are not, email me ASAP. After the first week, you will be behind if you do not have a solid background in Java.

What you need to turn in

You must submit your work to Canvas. Your submission must include:

1. A single .java file that contains your solution to the problem. The .java file should be compilable and runnable. Multiple .java files will result in significant penalties.

2. A report, not to exceed two pages, as a Word document, PDF, or RTF that contains a description of the algorithm implemented by you and an analysis of its complexity. It is important that you write a description of the algorithm and not a description of your program. Do not explain your classes and methods but the sequence of operations that you used to solve the problem and why this sequence of operations correctly solves the problem.

Pseudo-code is a standard way to explain an algorithm.

Pack all your files into a .zip file (The extension must be .zip and it must be a zip archive file). Name the zip file your netID.zip so if your netID is broge2 your zip file would be broge2.zip. Files which are not zipped correctly or named properly will receive a 0.

The Problem

Write a program called MostCount that reads a text file called in.txt that contains a list of integers, duplicates are possible, separated by spaces. As you read the integers in the program should save them into a singly linked list in the same order they appear in the file. No modification of the list, before, during, or after reading, is allowed. This includes sorting, shuffling, or any other modifications of the nodes or elements. The nodes of the list should only have 2 pieces of information which are the reference to the next node and a data element to store the integer. No additional information may be stored by the list or the nodes.

The program should determine and print the count of the most frequent element in the list using only recursion. No looping structures such as while-loops or for-loops are allowed when determining this value. There may be more than one element with the same maximum frequency. We only want the count and not the element with the count.

Examples

List - [ XXXXXXXXXX]
Output - 4
Reason - The element 3 is the most frequent element with a count of 4.

List - [ XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX]
Output - 6
Reason - The element 109 is the most frequent element with a count of 6.

List - []
Output - 0
Reason - There are no elements in the list
List - [10]
Output - 1
Reason - There is only 1 element with a frequency of 1.
List - [ XXXXXXXXXX XXXXXXXXXX XXXXXXXXXX]
Output - 1
Reason - All elements only occur 1 time so 1 is printed.

Restrictions

To receive maximum points for this assignment you must follow the guidelines presented here.

1. You must implement and utilize a singly linked list. The linked list must be written from scratch by you. You only need to implement the necessary methods that will help you solve the problem. Try to keep your linked list implementation minimal.

a. You may not use the built-in list implementations in the Java library. This includes Linked List and Array List.

b. Each node of the linked list may include only two elements: one integer type and a reference to the next node of the list.

c. You may not have more than one instance of the singly linked list.

2. Read the integers from a file called in.txt as specified. You can assume this file is in the same location as your program.

a. No calculations are permitted while reading in the data from in.txt.

b. Once the data is read into your linked list, you may not manipulate the data or the list. For example, you may not sort, shuffle, remove, or add to the list. Once the integers have been read in, the list must remain the same throughout the runtime of the program.

c. Your program may not modify the file at all. It should perform read-only operations.

3. No additional data structures are allowed. This includes arrays, strings, trees, etc. All computations must be done in place in the original linked list (section 2b). Your program may use auxiliary scalar variables and reference variables (used to point to nodes of the list).

a. There is only one exception to this rule and that is while you are reading in the data you may use strings. This is also the only time you may use the standard library as well. For example, you can use StringTokenizer and/or the Scanner library. Use of Exceptions classes is a given since you will need to handle the FileNotFoundException.

4. All code should be placed in one .java file and must be able to be compiled and ran from that .java file. Inner classes are allowed. Again, try to write a short and simple program. I/O, exception handling, and the linked list implementation should be kept to a minimum.

5. Only print the value. Remove any debugging output from your program before submitting.

Assignment 2 must be solved by following these guidelines. Bypassing any of these, such as saving numbers in a string or using an array to keep track of additional data will be penalized. If you have any questions about what can and cannot be used, you may email me.

Your Analysis

The final part to this assignment is your analysis of the problem and your algorithm and the complexity of the problem. The report should not exceed two pages and should be in the format of an ASCII text document, MS Word document, or PDF.

NOTE: It is important that you write a description of the algorithm and not a description of your program!

You should explain

· The sequence of operations that you use to solve the problem

· Why this sequence of operations correctly solves the problem

o Pseudocode is a standard way to explain an algorithm

· The complexity. (The BigO of the problem)

Plagiarism

Plagiarism is defined as copying or receiving materials from a source or sources and submitting this

material as one's own without acknowledging the source (quotations, paraphrases, basic ideas), or

otherwise representing the work of another as one's own, is not allowed. Collaboration or group work,

usually evidenced by unjustifiable similarity, is not permitted. The homework will be subject to

screening by software programs designed to detect evidence of plagiarism or collaboration. Keep in mind that posting a message (including anonymous messages) about the homework on the Internet (blog, software development forums, etc.) is plagiarism. I will be monitoring the Web for the next couple of weeks and taking actions if such a message is posted. Any student (or a group of students) accused of a violation of academic integrity will receive an F for the course.

Use of sites like Chegg, CourseHero, Bartleby, etc. is considered plagiarism. Action will be taken for anyone that is found to have posted the problem to any online site. The content of the course is copyrighted by the University and posting without permission can be considered a copyright violation. If you are struggling with the problem, you may email your questions about what you are struggling with.