辅导案例-CS 353-Assignment 3
CS 353: Programming Assignment 3 Due on: Nov 6th, 11:59 p.m. --------------------------------------------------------------------------------------------------- Introduction The aim of this assignment is to give you hands-on experience writing graph algorithms that are used in Computer Networks to calculate the routing table. In this assignment, you will implement Dijkstra’s Algorithm in part 1 and the Minimum Spanning Tree Algorithm in part 2. This assignment must be implemented in Python 3.5+ and executable directly from the command line. --------------------------------------------------------------------------------------------------- Input Your program should be able to parse input files in the following format. The first line will be an integer representing the number of lines in the graph, N. The following N lines will be a dictionary such that keys will be a char between ‘A’ and ‘Z’ representing a source node, followed by a ‘:’ and a list of comma-separated destination nodes along with the weights of their path. Finally, the last 2 lines will be the source node and the destination node. Your input.txt will look like this: 3 A : [B,1], [C,2], [D,3] B : [C,10] C : [D,2], [E,3] A E Explanation The first line, 3, represents the number of lines for the graph and the last two lines represent source node and destination node respectively. You may assume that the source node and destination node will be present in N lines, though not necessarily as key in any of the N lines. There will not be any duplicate keys or conflicting paths. (Eg. A:[B,1] and B:[A:2]) Constraints: - All nodes have a unique char key - number of nodes is between [0, 26] - value of weights is between [0, 100] NOTE: ● The graph is directional ● Use the lexicographical index of node name in order to break ties, if any, for ex: ‘A’ is preferred over ‘B’ and ‘B’ is preferred over ‘C’ and so on. ● Not all nodes will be keys to the dictionary. Eg: D and E are the sink nodes such that no arrow points out of them i.e. their out-degree is 0. --------------------------------------------------------------------------------------------------- Part 1- Dijkstra’s Algorithm In this part, you should find the shortest distance between the source node and destination using Dijkstra’s algorithm. You may use the following links to help understand the Dijkstra algorithm: https://people.ok.ubc.ca/ylucet/DS/Dijkstra.html Your program must be runnable with the following command(For macOS): >python3 dijkstra.py -i inputFile Command Line Argument: -i: the name of input file Your program must write to ‘output_dijkstra.txt’ in the form of “SN –(W1)-> IN1 –(W2)-> IN2 –(W3)-> DN Total Weight” where SN is the source node, IN(x) are intermediary nodes, and DN is the destination node. W(x) values are the weights of the edge between nodes. On the last line, output the total weight of the path. Expected Output: Your output_dijkstra.txt should look like this: A -2-> C -3-> E 5 Your source code must be in dijkstra.py. To get started, you may use dijkstra_helper_code.py. You must keep the structure of start_dijkstra() as it is, however you may choose to rename variables and add your custom functions. You can assume there will always be a valid path between source and destination --------------------------------------------------------------------------------------------------- Part 2- Minimum spanning Tree(MST) In this part, you must treat edges as non-directional rather than directional. The input will remain the same as in part 1. You may use the following link to help understand the Kruskal’s algorithm: https://people.ok.ubc.ca/ylucet/DS/Kruskal.html YOU MUST USE KRUSKAL’S ALGORITHM TO FIND THE MINIMUM SPANNING TREE. Using any other algorithm may cause your output to differ from the expected output. Your program should write to ‘output_mst.txt’ in the form of : E1 IN1 IN2 E2 IN3 IN4 E3 IN2 IN3 Sort edges by length(ascending order) such that E1 < E2 < E3 and so on. Sort the name of nodes such that IN1 < IN2 and IN3 < IN4. All nodes must be included and no cycles should exist. Expected Output: Your output_mst.txt should look like this: 1 A B 2 A C 3 C D 3 C E Additionally, break ties with the following rules: - If you have to choose between say two edges of the same weight say B – C/C - B and E – F/F - E, choose B – C . First, sort edges such that left node is smaller than right node so after sorting you will get B – C v/s E – F now since B < E so select edge B – C - If you have to choose between edges B – C/C – B and B – E/ E – B. First, sort edges such that left node is smaller than right node so after sorting you will get B – C v/s B – E, now since C < E therefore select B – C edge. Your source code must be in mst.py. To get started, you may use mst_helper_code.py. You must keep the structure of start_dijkstra() as it is, however you may choose to rename variables and add your custom functions. --------------------------------------------------------------------------------------------------- Grading You will be graded solely on the content of ‘output_dijkstra.txt’ and ‘output_mst.txt’. One sample input and the two outputs will be provided. Your code will be run on a suite of test cases and scored on the number of matched outputs. Both parts of the assignment are weighted equally. Please try to ensure your code can unzip properly and run without needing to install additional packages. Submissions that cannot be unzipped or do not compile will receive a 0. --------------------------------------------------------------------------------------------------- Code and Collaboration Policy You can discuss the assignment and coding strategies with your classmates. However, your solution must be coded and written by yourself. Please refer to the plagiarism policy in the course syllabus. The submissions will be run through code similarity tests. Any flagged submissions will result in a failing score. Keeping your code private is your responsibility. You are strongly encouraged to pair and test your code implementations with your peers in class. --------------------------------------------------------------------------------------------------- Submission You can develop and test your code on your own machines. Create a compressed tar file that includes a README, dijkstra.py, and mst.py. To submit, create a folder called LASTNAME_FIRSTNAME with the above files. Tar the folder LASTNAME_FIRSTNAME. Submit the tar file on the blackboard. The README must contain USCID, email address and/or additional notes on usage if needed. Python: Make sure you add the directives to support direct execution. You must use Python 3.5+. Make separate files for part1 and part2 namely dijkstra.py and mst.py. The directory structure should look like this LASTNAME_FIRSTNAME: ● dijkstra.py ● mst.py ● README.txt We will then run your programs using a suite of test inputs. After running the program, we will grade your work based on the output written to the corresponding text files.
