Assignment 1

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

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 – [1 2 3 2 3 2 1 1 3 3]Output – 4Reason – The element 3 is the most frequent element with a count of 4.

List – [102 109 102 100 104 109 109 103 102 107 104 104 109 105 103 110 107 108 101 108 101 109 105 109 102 105 103 106 110 107]Output – 6Reason – The element 109 is the most frequent element with a count of 6.

List – []Output – 0Reason – There are no elements in the listList – [10]Output – 1Reason – There is only 1 element with a frequency of 1.List – [5 7 0 10 1 -3 -6 -5 3 -2 -7 -9 6 -8 -4 -11 -1 4 9 2 -10 8]Output – 1Reason – 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 1 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

· Pseudocode is a standard way to explain an algorithm

· The complexity. (The BigO of the problem)