COMP108 Data Structures and AlgorithmsAssignment 2Deadline: Fridday 3rd May 2019, 4:00pmImportant: Please read all instructions carefully before starting the assignment.Basic information Assignment: 2 (of 2) Deadline: Friday 3rd May 2019 (Week 11), 4:00pm Weighting: 15% of the whole moduleElectronic 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 linked lists and their associated algorithms– 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: 75%– Time Complexity Anslysi: 15%– Programming style: 10% There are two parts of the assignment (Part 1: 45% & Part 2: 30%). You are expected tocomplete both.1 Part 1: The List Accessing Problem (45%)Suppose we have a filing cabinet containing some files with (unsorted) IDs. We then receive asequence 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 wefind key, it is called a hit and we remove the file from the cabinet. Suppose key is the i-th filein the cabinet, then we pay a cost of i, which is the number of comparisons required. If key isnot in the cabinet, the cost is the number of files in the cabinet and we then go to a storage tolocate the file. After using the file, we have to return the file back to the cabinet at the originallocation or we may take this chance to reorganise the file cabinet, e.g., by inserting the requestedfile to the front. As the file can only be accessed one after another, it is sensible to use the datastructure linked list to represent the file cabinet.11.1 The algorithmsWe consider three accessing/reorganising algorithms. To illustrate, we assume the file cabinetinitially 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 afile at the end if it was not originally in the cabinet. Therefore, there will be 5 hits, the filecabinet will become 20 30 10 5 at the end, and the number of comparisons (cost) for the6 requests is respectively 1 2 3 2 4 1. The following table illustrates every step.request list beforehand hit? # comparisons list afterward20 20 30 10 yes 1 no change30 20 30 10 yes 2 no change5 20 30 10 no 3 20 30 10 530 20 30 10 5 yes 2 no change5 20 30 10 5 yes 4 no change20 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 530 10 at the end. The number of comparisons (cost) for the 6 requests is respectively 1 23 2 2 3. The following table illustrates every step.request list beforehand hit? # comparisons list afterward20 20 30 10 yes 1 no change30 20 30 10 yes 2 30 20 105 30 20 10 no 3 5 30 20 1030 5 30 20 10 yes 2 30 5 20 105 30 5 20 10 yes 2 5 30 20 1020 5 30 20 10 yes 3 20 5 30 10 Frequency count: This algorithm rearranges the files in non-increasing order of frequencyof access. This means that the algorithm keeps a count of how many times a file has beenrequested. When a file is requested, its counter get increased by one and it needs to bemoved to the correct position. If there are other files with the same frequency, the newlyrequested file should be put behind those with the same frequency. We assume that thefiles initially in the cabinet has frequency of 1 to start with. A newly inserted file also hasa frequency of 1.In this case, there will be 5 hits. The file cabinet will become 30 20 5 10 at the end. Thenumber of comparisons (cost) for the 6 requests is respectively 1 2 3 2 4 2. The followingtable illustrates every step.request list beforehand hit? # comparisons list afterward frequency count afterward20 20 30 10 yes 1 no change 2 1 130 20 30 10 yes 2 no change 2 2 15 20 30 10 no 3 20 30 10 5 2 2 1 130 20 30 10 5 yes 2 30 20 10 5 3 2 1 15 30 20 10 5 yes 4 30 20 5 10 3 2 2 120 30 20 5 10 yes 2 no change 3 3 2 121.2 The programs A2Node.java and A2List.javaTwo programs A2Node.java and A2List.java can be downloaded from VITAL. The programA2Node.java contains a class called A2Node with the following attributespublic int data;public A2Node next;public int freq;The program A2List.java has declared two global variables head and tail which point to thehead (first node) and the tail (last node), respectively, of the list representing the file cabinet. Theprogram 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 newNodeto 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 listThe 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 ofthe initial cabinet and calls each algorithm in turn. The order of calling the algorithm has beenpre-determined and you should not change the order, otherwise, you may lose all your marks. Theheader of each algorithm has been provided. They can all access global variables head and tail,as well as the array reqData[] that stores the requests.1.3 Your tasksThere are three tasks you need to do. Each task is associated with each of the algorithms, andeach 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 dwhere a b c d are the IDs of file in the final list. (Again one single space at the end isallowed.) If your list is maintained properly the method printList() will do the job. Task 1.1 (15%) Implement the appendIfMiss() method that appends a missed file to theend of the list and does not reorganise the list. Task 1.2 (15%) Implement the moveToFront() method that moves a requested file orinserts a missed file to the front of the list. When moving a node in the list, you have tomake sure that the next field of affected nodes, head, and tail are updated properly. Task 1.3 (15%) Implement the freqCount() method that moves a requested file or inserts amissed file in a position such that the files in the list are in non-increasing order. Importantlywhen the requested file has the same frequency count as other files, the request file shouldbe placed at the end among them. Again make sure you update next, head, tail properly.31.4 Test casesBelow are some sample test cases and the expected output. These test cases can be downloadedas listSample01.txt, listSample02.txt, listSample03.txt on VITAL. You can run the program easierby typing java A2List and over again.Make sure you remove or comment print statements that you use for debugging before submission.The order of output should be appendIfMiss, moveToFront, freqCount. Your programwill be tested in this order, therefore, do NOT change the order (you should not change the mainmethod anyway)! Your program will be marked by five other test cases that have not be revealed.Test case Input Output (‘ ’ represents a space)#1listSample01.txt320 30 10620 30 5 30 5 20appendIfMiss...1 2 3 2 4 15 hList: 20 30 10 5moveToFront...1 2 3 2 2 35 hList: 20 5 30 10freqCount...1 2 3 2 4 25 hList: 30 20 5 10#2listSample02.txt420 30 10 40950 10 10 20 50 50 50 40 70appendIfMiss...4 3 3 1 5 5 5 4 57 hList: 20 30 10 40 50 70moveToFront...4 4 1 3 3 1 1 5 57 hList: 70 40 50 20 10 30freqCount...4 3 1 2 5 3 2 5 57 hList: 50 10 20 40 30 70#3listSample03.txt320 10 302010 20 30 10 6020 30 30 30 3040 40 40 40 5050 50 50 20 50appendIfMiss...2 1 3 2 3 1 3 3 3 3 4 5 5 5 5 6 6 6 1 617 hList: 20 10 30 60 40 50moveToFront...2 2 3 3 3 4 4 1 1 1 4 1 1 1 5 1 1 1 4 217 hList: 50 20 40 30 60 10freqCount...2 2 3 1 3 2 3 3 1 1 4 5 4 4 5 6 5 5 5 317 hList: 30 50 40 20 10 6042 Part 2: Distance Neighbourhood on Graphs (30%)Suppose we have an undirected graph to model facebook connection (or some other similar socialnetwork). There are n users, each represented by a vertex. If two users are friends of each other,then there is an edge between the two corresponding vertices. This forms a simple graph (atmost one edge between any two vertices) with no self-loop (a vertex has no edge to itself). Thisfriend-relationship can be represented by an adjacency matrix of size n × n. The entry (i, j) is 1if vertex i and j have an edge between them, and 0 otherwise.For any two vertices that are not immediate neighbour (i.e., no edge between them), we wantto know if they are “connected” via the same neighbour. In other words, they are distance-2 apart.We can generalise this concept to distance-d for d ≥ 1. For example, in the following graph, v0 isa distance-2 neighbour of v3 and v4 but not v5 while v0 is a distance-3 neighbour of v5.We can represent this distance-d neighbourhood relationship using a d-neighbourhood matrix.An entry between vertex i and j is d(i, j) if the closest distance between them is d(i, j) andd(i, j) is at most d. If the distance d(i, j) > d or there is no path between i and j, then the entry(i, j) is 0. With the above graph, the distance-1, distance-2 and distance-3 neighbourhood matrixare shown below in the left, middle, right, respectively.�In addition, we are interested to know the degree of separation which is the minimumdistance deg such that the deg-neighbourhood of every vertex covers every other vertices. In otherwords, we want to find the minimum deg such that the deg-neighbourhood matrix contains 0entries only along the diagonal. In the above example, the degree of separation is 3.In some cases, the given graph may not be connected, meaning that there is at least a pair ofvertices that is not connected by any path. For example, the following graph is not connected.The distance-1, distance-2, distance-3 neighbourhood matrix are also shown below (left, middle,right, respectively).2.1 The program A2Graph.javaThe program A2Graph.java can be downloaded from VITAL. A global 2-dimensional array variableadjMatrix[][] has been declared, which stores the adjacency matrix. A number of methodsalready written which you must NOT change, including public static void main(String[] args) static void input() which reads input. static void printSquareArray(int array[][], int size) which prints the content ofa 2-D size-by-size arrayThe main method first calls the method input() to get (i) the size of the graph, (ii) the adjacencymatrix, and then asks for (iii) a distance. (Notice that the input part has suppressed printingtext asking for input.) Then it calls the method neighbourhood to calculate the neighbourhoodmatrix, followed by the method degreeSeparation to find the degree of separation.2.2 Your tasks Task 2.1 (15%) Implement the method neighbourhood with the following header:static void neighbourhood(int distance, int result[][], int size)The method should calculate the distance-neighbourhood matrix and store the matrix inthe result[][] array which is of size-by-size. The main method will call the printSquareArraymethod so this method does not need to print anything. Task 2.2 (15%) Implement the method degreeSeparation to determine the degree ofseparation of the graph. The output should be: “Degree of separation is XX”, whereXX is the answer. If the graph is not connected, i.e., there is at least one pair of verticeswhich cannot be connected by a path, then the output should be: “The graph is notconnected”. You are expected to use the distance-neighbourhood matrix to achieve thistask.2.3 Test casesBelow are some sample test cases and the expected output. These test cases can be downloaded asgraphSample01.txt, graphSample02.txt, graphSample03.txt on VITAL. You can run the programeasier by typing java A2Graph input over and over again.Make sure you remove or comment all other print statements that you use for debugging beforesubmission. The order of output should be neighbourhood, degSeparation. Your program willbe tested in this order, therefore, do NOT change the order (you should not change the mainmethod anyway)! Your program will be marked by five other test cases that have not be revealed.6Test case Input Output#1graphSample01.txt60 1 1 0 0 01 0 0 1 0 01 0 0 1 1 00 1 1 0 0 10 0 1 0 0 10 0 0 1 1 020 1 1 2 2 01 0 2 1 0 21 2 0 1 1 22 1 1 0 2 12 0 1 2 0 10 2 2 1 1 0Degree of separation is 3#2graphSample02.txt60 1 1 0 0 01 0 0 1 0 01 0 0 0 0 00 1 0 0 0 00 0 0 0 0 10 0 0 0 1 030 1 1 2 0 01 0 2 1 0 01 2 0 3 0 02 1 3 0 0 00 0 0 0 0 10 0 0 0 1 0The graph is not connected#3graphSample03.txt50 1 0 0 01 0 1 0 00 1 0 1 00 0 1 0 10 0 0 1 040 1 2 3 41 0 1 2 32 1 0 1 23 2 1 0 14 3 2 1 0Degree of separation is 43 Additional information3.1 Time complexity analysis (15%) The time complexity has to match your implementation. Marks will NOT be awarded if the correspondingalgorithm has not been implemented. You are expected to write the time complexity and short justification in the comment section at the beginningof the two java files. For each algorithm, 2% is awarded to the time complexity and 1% to the justification.3.2 Programming Style (10%)? You should keep a good programming style. Marks will be awarded based on(i) 2% consistent and appropriate use of brackets(ii) 2% consistent and appropriate use of indentation(iii) 2% meaningful variable names(iv) 2% comments to explain the working of your programs(v) 2% your personal information at the beginning of the java files3.3 Penalties UoL standard penalty applies: Work submitted after 4:00pm on the deadline day is considered late. 5 marksshall be deducted for each 24 hour period after the deadline. Submissions submitted after 5 days past thedeadline will no longer be accepted. Any submission past the deadline will be considered at least one daylate. Penalty days include weekends. This penalty will not deduct the marks below the passing mark.7 If your code does not compile successfully, 5 marks will be deducted. If your code compile to classes ofdifferent names from A2List, A2Node, A2Graph, 5 marks will be deducted. If your output does not followthe same format as expected, 5 marks will be deducted. If your output does not follow the order of thealgorithms as expected, 5 marks will be deducted. These penalties will not deduct the marks below thepassing mark. You are required to implement the list and adjacency matrix yourself. It is NOT allowed to use built-inclasses or functions. Doing so would get all marks deducted (possibly below the passing mark).3.4 Plagiarism/CollusionThis assignment is an individual work and any work you submitted must be your own. You should not colludewith another student, or copy other’s work. Any plagiarism/collusion case will be handled following the Universityguidelines. Penalties range from mark deduction to suspension/termination of studies. Refer to University Codeof Practice on Assessment Appendix L — Academic Integrity Policy for more details.8本团队核心人员组成主要包括硅谷工程师、BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论