Reference no: EM132261865

Assignment -

Learning outcomes: To be able to: take informal descriptions of algorithms and describe them formally in pseudocode; assess the run-?me complexity of algorithms; implement formal descriptions of algorithms using the Java programming language; run and report the findings of practical timing experiments. Develop bespoke data structures.

Overview - Split in two parts. The first involves designing algorithmic solutions to a specific problem (Exercise 1) and the second requires you design, implement and test a bespoke data structure (Exercise 2).

Exercise 1: Algorithm Design and Implementation

Let a be an array of n positive integers. If a particular value, v, occurs more than n/2 times in a then we say that this value dominates a. Obviously, for any array, a, there is at most a single value that dominates a (which we call it SVD). For example, 7 is the SVD for the array

[7, 7, 9, 3, 2, 7, 7],

but the array

[7, 7, 9, 3, 2, 7]

has no SVD. The SVD problem is:

given an array, a, of positive integer values, find the single value dominating a, if it exists, or report that one does not exist otherwise.

1. Design an algorithm for solving the SVD problem whose worst-case run-time complexity is O(n²). This should be the most obvious approach involving nested iteration over the array, and not use sorting nor any secondary data structure.

2. Design an algorithm for solving the SVD problem whose worst-case run-time complexity is O(nlog(n)). This can employ a secondary data structures and/or assume standard algorithms are available (i.e. those available in Java).

3. Design an algorithm for solving the SVD problem whose space complexity and worst-case run-time complexity are both O(n). The best way of solving this does not require any secondary data structure, although partial marks will be given for approaches that do so, assuming the time complexity is O(n).

For each part, you should first give an informal description of the ideas underlying your proposed algorithm. Then, using pseudocode, you should give a formal description of your algorithm. You should then use the approach described in lectures to analyse the algorithm to demonstrate that it does indeed have the required worst-case run-time complexity. Remember to follow all steps of the analysis.

4. Implement and test your algorithm for questions 1, 2 and 3. Design an experiment to test the timing, and produce graphs for each approach that experimentally verify the worst case run time complexity of each approach. Marks will be awarded for correctness (i.e. following the algorithm), clarity and code design, experimental method and the presentation of results.

Exercise 2: Data Structure Design and Implementation

For this question you will implement a hash table with chaining that uses arrays to store the chains rather than linked lists. This is not necessarily a sensible approach, but it is included to test your ability to manipulate array based data structures. You must implement the hash table with arrays, not with the ArrayList class. Your data structure need not be generic, it can work with just objects, but you will not be penalised for using any of the Collections features (generics. iterable etc) taught in Programming 2. You can include class variables and methods not specified. You may, if you wish, adapt the abstract class, but please keep the methods that are already in there. Please note do not want you to implement rehashing for this hash table. The capacity should remain constant.

1. Basic structure and constructor.

Implement a class ArrayHashTable that extends the abstract class HashTable and uses chaining. The data should be stored in a two dimensional array called table. In addition to the inherited variables, the class should have an integer variable chainSize (the initial size of each array to store the chain, default to 5). These variables should be updated when items are added or removed from the table. The default capacity should be to and the constructor should initialise table to an array of arrays size capacity, with each value set to null.

table = new Object [capacity] [];

the number of elements at each location of the hash table should be stored in an array of integers called counts, all initialised to zero.

2. Implement the method add.

Use the method hashCode to find the hash value for the location in the hash table. If the entry is empty (e.g. if the hash value is 5 and table [5] == null), create a new array of size chainSize. If the entry is not empty, insert the item at the correct location, if it is not already present. If this means the current array is now full, double the size of the current array and copy over the values. This method should return true if the item is added to the table, false if not (i.e. if it is already present).

3. Implement the method contains.

This should be trivial once you have implemented add.

4. Implement the method remove.

Use the method hashCode to find the hash value for the location in the hash table. If the entry is empty, or the array for that entry does not include the object passed, return false. Otherwise, remove the item, adjusting the hash table variables and remaining hash table objects accordingly.

5. Design an experiment to test the run time of your hash table and of the Java class HashSet for inserting n randomly generated Integer objects into a hash table with initial capacity to, then removing the same n integers. The timing experiment code is similar to that for question 1. Use n =< 1000, 2000, . . . , 10000, 15000, 20000, 25000, . . . , 50000 >, although you can reduce the maximum if it is too slow to run. You can generate an array of numbers to add then remove with the following code (or use your own technique).

int [] numbers=new int [n];

Random r=new Random() ;

for(int j=0; j < n; j++){

numbers[j] = Math.abs(r.nextInt());

}

Using Microsoft Excel or otherwise, plot a graph of these results and explain what the graph demonstrates and why there are any observed differences.