Computer Science 220S1C (2019)Assignment 3 (hashing and basic graph algorithms)Due date May 21, 2018, 10pm100 Marks in totalThis assignment requires you to submit programs in Python that you have written yourselfto the automarker, http://www.cs.auckland.ac.nz/automated-marker. Your implementationmust be from first principles and cannot use an existing library methods thatmight solve the problem (eg hashes, performs graph operations etc).The automarker runs on a Linux box. Read the automarker help and FAQ for moredetails.Please submit only Python source code named a3qX.py where X is 1, 2 or 3 correspondingto the problems below.1. Hashing 30 marksYou are given an input file with multiple lines. On each line there is:(a) the size, m, of the hash table which is a prime(b) a second prime number, p (c) a sequence of integer keysYour program will create a hash table of size m and insert each key into the table.Use the primary hash functionh(x) = x mod mand the secondary hash function for collision resolutionδ(x) = (x mod p) + 1.We use the convention that probes are made to the left of the initial probe.It will output(a) the total number of keys that are out of place in the table,1(b) the number of probes required to look up the final item inserted in the hashtable, and(c) the expected number of probes to find a random item, Tss(λ) = 1rounded to 3 decimal places.Input format: On each line is a sequence of at least 3 comma separated integerswhere the first integer is m, the second is p and the remaining integers are keys.For example:11,3,2,14,37,2,1,2Output format: For each line of input, the output should have a line with thethree values described in (a)-(c) above, in that order, separated by commas. Thelast number should have exactly 3 decimal places. Use Python str.format roundingbehaviour.For the example input above,代做220S1C作业、代写graph algorithms作业、Python语言作业代做、Python程序语言作业调试output would be:1,3,1.1680,1,1.1782. Reverse of a digraph 30 MarksFor a given set of digraphs, write a program that prints out the reverse of eachdigraph.Input format: described below under the heading “Digraph input format”. Notethat adjacency lists are sorted.Output format: use the input format to output your result ensuring that the outputadjacency lists are sorted.For the example input shown below, the output would be23. Tree and back arcs in a DFS 40 MarksFor a given set of digraphs, write a program that performs DFS on each digraphstarting at node 0 and prints out the total number of tree arcs and back arcs resultingfrom the traversal. Use our standard convention that when there is a choice of whiteor grey nodes, the one with the lowest index should be chosen.Input format: described below under the heading, “Digraph input format”.Output format: For each input digraph, print out a line with the number of treearcs and the number of back arcs separated by a comma.For the example input shown below, the output would beDigraph input formatA sequence of one or more digraphs is taken from the keyboard (System.in). Each graphis represented by an adjacency list. The first line is an integer n indicating the order of thegraph. This is followed by n white space separated lists of adjacencies for nodes labeled0 to n - 1. The input will be terminated by a line consisting of one zero (0). This lineshould not be processed. The sample input below shows two digraphs, the first has nodeset {0, 1, 2, 3} and arc set {(0, 1),(0, 3),(1, 2),(1, 3),(2, 0)}, the second has node set {0, 1, 2}and arc set {(0, 1),(0, 2),(2, 1)}.MarkingThe maximum number of submissions for each problem is fixed at 10.Each problem has five test cases associated with it worth one fifth of the marks for thatproblem. Some of the test cases will be large to test for speed. You get full marks if youpass all test cases.3转自：http://www.7daixie.com/2019052140782233.html
网友评论