Data Structures and AlgorithmsCOMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday...

Question

Data Structures and AlgorithmsCOMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday 3rd May 2018, 4:00pm �� ��Important: Please read all instructions carefully before starting the assignment. Basic information • Assignment: 2 (of 2) • Deadline: Thursday 3rd May 2018 (Week 11), 4:00pm • Weighting: 20% • Electronic Submission: https://sam.csc.liv.ac.uk/COMP/Submissions.pl?qryAssignment=COMP108-2 • What to submit: three java files named A2Node.java, A2List.java and A2Graph.java • Learning outcomes assessed: – Be able to apply the data structures arrays and linked lists and their associated algo- rithms – Be able to apply a given pseudo code algorithm in order to solve a given problem – Be able to apply the iterative algorithm design principle • Marking criteria: – Correctness: 90% – Programming style: 10% • There are two parts of the assignment (Part 1: 55% & Part 2: 35%). You are expected to complete both. 1 Part 1: The List Accessing Problem (55%) Suppose we have a filing cabinet containing some files with (unsorted) IDs. We then receive a sequence of requests for certain files, given in the IDs of the files. Upon receiving a request of ID, say key, we have to locate the file by flipping through the files in the cabinet one by one. If we find key, it is called a hit and we remove the file from the cabinet. Suppose key is the i-th file in the cabinet, then we pay a cost of i, which is the number of comparisons required. If key is not in the cabinet, the cost is the number of files in the cabinet and we then go to a storage to locate the file. After using the file, we have to return the file back to the cabinet at the original location or we may take this chance to reorganise the file cabinet, e.g., by inserting the requested file to the front. As the file can only be accessed one after another, it is sensible to use the data structure linked list to represent the file cabinet. 1 1.1 The algorithms We consider three accessing/reorganising algorithms. To illustrate, we assume the file cabinet initially contains 3 files with IDs 20 30 10 and the sequence of requests is 20 30 5 30 5 20. • Append if miss: This algorithm does not reorganise the file cabinet and only appends a file at the end if it was not originally in the cabinet. Therefore, there will be 5 hits, the file cabinet will become 20 30 10 5 at the end, and the number of comparisons (cost) for the 6 requests is respectively 1 2 3 2 4 1. The following table illustrates every step. request list beforehand hit? # comparisons list afterward 20 20 30 10 yes 1 no change 30 20 30 10 yes 2 no change 5 20 30 10 no 3 20 30 10 5 30 20 30 10 5 yes 2 no change 5 20 30 10 5 yes 4 no change 20 20 30 10 5 yes 1 no change • Move to front: This algorithm moves the file just requested (including newly inserted one) to the front of the list. In this case, there will be 5 hits. The file cabinet will become 20 5 30 10 at the end. The number of comparisons (cost) for the 6 requests is respectively 1 2 3 2 2 3. The following table illustrates every step. request list beforehand hit? # comparisons list afterward 20 20 30 10 yes 1 no change 30 20 30 10 yes 2 30 20 10 5 30 20 10 no 3 5 30 20 10 30 5 30 20 10 yes 2 30 5 20 10 5 30 5 20 10 yes 2 5 30 20 10 20 5 30 20 10 yes 3 20 5 30 10 • Frequency count: This algorithm rearranges the files in non-increasing order of frequency of access. This means that the algorithm keeps a count of how many times a file has been requested. When a file is requested, its counter get increased by one and it needs to be moved to the correct position. If there are other files with the same frequency, the newly requested file should be put behind those with the same frequency. We assume that the files initially in the cabinet has frequency of 1 to start with. A newly inserted file also has a frequency of 1. In this case, there will be 5 hits. The file cabinet will become 30 20 5 10 at the end. The number of comparisons (cost) for the 6 requests is respectively 1 2 3 2 4 2. The following table illustrates every step. request list beforehand hit? # comparisons list afterward frequency count afterward 20 20 30 10 yes 1 no change 2 1 1 30 20 30 10 yes 2 no change 2 2 1 5 20 30 10 no 3 20 30 10 5 2 2 1 1 30 20 30 10 5 yes 2 30 20 10 5 3 2 1 1 5 30 20 10 5 yes 4 30 20 5 10 3 2 2 1 20 30 20 5 10 yes 2 no change 3 3 2 1 2 1.2 The programs A2Node.java and A2List.java Two programs A2Node.java and A2List.java can be downloaded from http://www2.csc.liv.ac.uk/~pwong/teaching/comp108/201718/assess.html The program A2Node.java contains a class called A2Node with the following attributes public int data; public A2Node next; public int freq; The program A2List.java has declared two global variables head and tail which point to the head (first node) and the tail (last node), respectively, of the list representing the file cabinet. The program contains a number of methods already written which you must NOT change, including • public static void main(String[] args) • static void insertNodeHead(A2Node newNode) which inserts the node called newNode to the head of the list • static A2Node deleteHead() which deletes the node at the head • static void printList() which prints the list from head to tail • static void emptyList() which empties the whole list The main method takes care of the input, reading (i) number of files in the initial cabinet, (ii) the file IDs in the initial cabinet, (iii) number of file requests, and (iv) IDs of the file requests. (Notice that the input part has suppressed printing text asking for input.) It then creates a list of the initial cabinet and calls each algorithm in turn. The order of calling the algorithm has been pre-determined and you should not change the order, otherwise, you may lose all your marks. The header of each algorithm has been provided. They can all access global variables head and tail. 1.3 Your tasks There are three tasks you need to do. Each task is associated with each of the algorithms, and each should print and only print the following. See Test Cases below for examples. (i) The number of comparisons for each request separated by a space , e.g., 1 2 3 (Note: one single space at the end is allowed.) (ii) x h where x is the number of hits (iii) The content of the final list in the form List: a b c d where a b c d are the IDs of file in the final list. (Again one single space at the end is allowed.) If your list is maintained properly the method printList will do the job. • Task 1.1 (20%) Implement the appendIfMiss() method that appends a missed file to the end of the list and does not reorganise the list. • Task 1.2 (15%) Implement the moveToFront() method that moves a requested file or inserts a missed file to the front of the list. When moving a node in the list, you have to make sure that the next field of affected nodes, head, and tail are updated properly. • Task 1.3 (20%) Implement the freqCount() method that moves a requested file or inserts a missed file in a position such that the files in the list are in non-increasing order. Importantly when the requested file has the same frequency count as other files, the request file should be placed at the end among them. Again make sure you update next, head, tail properly. 3 1.4 Test cases Below are some sample test cases and the expected output. These test cases can be downloaded as listTest01.txt, listTest02.txt, listTest03.txt on the assessment page: http://www2.csc.liv. ac.uk/~pwong/teaching/comp108/201718/assess.html You can run the program easier by typing java A2List

Snehil · Accepted Answer

A2Graph.java
A2Graph.java
/*
    Name:
    Student ID:
    Departmental username:
    University email address;
*/
import java.util.*;
import java.io.*;
class A2Graph {
    private static final int MaxVertex = 100;
    private static final int MinVertex = 1;
    private static Scanner keyboardInput = new Scanner(System.in);
    // adjacency matrix, adjMatrix[i][j] = 1 means i and j are adjacent, 0
    // otherwise
    public static int[][] adjMatrix = new int[MaxVertex][MaxVertex];
    public static int numVertex; // total number of vertices
    // DO NOT change the main method
    public static void main(String[] args) throws Exception {
        boolean userContinue = true;
        int distance = 1;
        int[][] neighbourMatrix = new int[MaxVertex][MaxVertex];
        input();
        try {
            // System.out.print("Enter a distance (" + MinVertex + "--" +
            // numVertex + ", -1 to exit): ");
            distance = keyboardInput.nextInt();
        } catch (Exception e) {
            keyboardInput.next();
        }
        if (distance  numVertex)
            System.out.println("incorrect range");
        else {
            neighbourhood(distance, neighbourMatrix, numVertex);
            printSquareArray(neighbourMatrix, numVertex);
        }
        degreeSeparation();
    }
    // find the degree of separation of the graph using the method
    // neightbourhood()
    static void degreeSeparation() {
        int[][] neighbourMatrix = new int[MaxVertex][MaxVertex];
        neighbourhood(numVertex, neighbourMatrix, numVertex);
        boolean connected = true;
        int degree = 0;
        for (int i = 0; i  distance) {
                    result[i][j] = 0;

COMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday 3rd May 2018, 4:00pm �� Important: Please read all instructions carefully before starting the assignment. Basic information •...

Answer To: COMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday 3rd May 2018, 4:00pm ��...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment

COMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday 3rd May 2018, 4:00pm �� ��Important: Please read all instructions carefully before starting the assignment. Basic information •...

Answer To: COMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday 3rd May 2018, 4:00pm ��...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment

COMP108 Data Structures and Algorithms Assignment 2 Deadline: Thursday 3rd May 2018, 4:00pm �� Important: Please read all instructions carefully before starting the assignment. Basic information •...