​​ ​​MKIT205 Data Structures and Algorithms Assignment 2 Due: Tuesday, 24th May, 11:55pm Introduction You are a computational neuroscientist working on simulations of neural networks. You have data representing a very large feed-forward network and wish to create a computer simulation for further study. The network can be modelled as a graph with vertices representing neurons and directed edges representing connections between them. In order to calculate the output of a neuron, you need to first calculate the output of all neurons that connect to it (note: this particular feed-forward network has no cycles). So a topological sort will give a possible evaluation order for the network. Assignment Specification – Part A (80%) For this part of the assignment, you will be given a network and a starting state. Your program will then calculate the subsequent state of the network. For neurons that have no inputs, the new state will be the same as the current state. For other neurons, a very simple neuron model will be used: for each neuron v: input = 0 for each edge uv: input += weight(uv)*state(u) if input>0: state(v) = 1 else: state(v) = 0 You must use the following data structures to represent the graph as an adjacency list: typedef struct edge{ int toVertex; int weight; } Edge; typedef struct edgeNode{ Edge edge; struct edgeNode *next; } *EdgeList; typedef struct graph{ int V; int *state; EdgeList *edges; } Graph; For testing purposes you will input the graph data from the keyboard and/or using input redirection (as for assignment 1). The input format is as follows:  The first line will contain the number of vertices (neurons) in the graph  Then for each vertex: o The first line contains the initial state of that vertex o The second line contains the number of edges from that vertex o The third line contains a list of toVertex,weight pairs separated by spaces (if there are no edges, this line is omitted) For example, the following text would define a 7 vertex graph: 7 1 2 6,1 3,-2 0 1 4,4 1 3 4,-2 3,1 0,3 1 0 1 1 3,2 0 4 6,2 3,-4 2,1 0,-3 1 3 5,2 4,-1 3,4 The edge weights will be in the range -100 to +100; states will be either 0 or 1. Your program should use the queue based topological sort method based on in-degrees to determine an evaluation order for the graph. Then working through the vertices in this topologically sorted order to calculate the next state of each neuron. The output should be the new state of all neurons after this calculation (on a single line). So the initial state of the vertex above would be printed as: 1011101 Assignment Specification – Part B (20%) You find that the topological sort can take a long time for some graphs, and you would also like to be able to detect cycles. So you decide to test whether a depth first search based topological sort gives better performance. For this part of the assignment, you will implement DFS for the input graph, and use the post- order numbering of the DFS spanning tree to determine if there are any cycles. [Note: you don't have to actually build a separate DFS spanning tree to calculated the post-order numbering] If there are no cycles, you should then use the post-order numbering to calculate a topological sort and calculate and print the new state of the graph as for part A. Otherwise, the program should print an error message: "this graph contains at least one cycle". There is however, a slight complication. The procedure for DFS described in lectures assumes a single known starting vertex. That is not the case for this data, where in general we will have many "input" neurons. In this situation, we usually build a DFS forest by repeated application of the algorithm. For this assignment, two solutions to this problem will be allowed: 1. Implement an algorithm that builds a DFS spanning forest. You will find examples of this approach online. 2. Use the previously calculated in-degrees to identify "input" neurons (the ones with in-degree 0). Then (conceptually) add a new vertex to the graph with edges to each of these inputs. Make this new vertex the starting point for your DFS. [Note: you don't have to actually add the vertex to the graph, just proceed as though it does exist] The first approach has the advantage that it is the standard way to deal with this problem,so you will find more help online. The second approach has the advantage that it matches what was discuss in lectures more closely and may be a little simpler to understand. Assignment Submission Assignments will be submitted via MyLO (an Assignment 2dropbox will be created). You should use the following procedure to prepare yoursubmission:  Make sure that you project has been thoroughly tested using the School's lab computers  Choose "Clean Solution" from the "Build" menu in Visual Studio. This step is very important as it ensures that the version that the marker runs will be the same as the version that you believe the marker is running.  Quit Visual Studio and zip your entire project folder along with a completed assignment cover sheet  Upload a copy of the zip file to the MyLO dropbox History tells us that mistakes frequently happen when following this process, so you should then:  Unzip the folder to a new location  Open the project and confirm that it still compiles and runs as expected o If not, repeatthe process from the start KIT205 Data Structures and Algorithms: Assignment 2 Synopsis of the task and its context This is an individual assignmentmaking up 12% of the overall unit assessment. The assessment criteria for this task are: 1. Implement code to create a graph using the correct input format 2. Implement topological sort using the queue-based in-degree method 3. Implement the network update step 4. Implement the DFS-based topological sort Match between learning outcomes and criteria for the task: Unit learning outcomes On successful completion ofthis unit... Task criteria: You will be an ICT professional with the abilities and skills to: 1. adapt and apply algorithms and data structures for storing, managing and analysing data, information and knowledge; 2. select and effectively apply algorithms and data structures to develop ICT products and services; 3. analyse algorithms and code to determine the runtime (and space) complexity, and evaluate strengths and 4. use algorithm design techniques to develop new algorithms for a given problem. You will acquire attitudes needed by an ICT professional to: 5. take initiative and work independently; 6. communicate effectively using appropriate terminology; 7. use abstraction and computational, creative and critical thinking to problem solve; 8. continue lifelong learning; 9. act in accordance with best practice and industry standards. weaknesses of potential algorithms; and Criteria HD (High Distinction) DN (Distinction) CR (Credit) PP (Pass) NN (Fail) 1. Implement code to create a graph using the correct input format Weighting 25% 2. Implement topological sort using the queue- based in-degree method Weighting 30% 3. Implement the network update step Weighting 25% 4. Implement the DFS- based topological sort Weighting 20% You have: You have: You have: You have: You have: Correctly read graph from input, placing nodes and edges in the correct order. Correct data structures used. Queue-based topological sort is implemented as described in lectures with no errors. Correct data structures used. Correctly implemented pseudo-code to update the network states in topologically sorted order. Correct data structures used. DFS-based topological sort is implemented as described in lectures with no errors. DFS is based on recursion. Correctly identified cycles. Correct data structures used. Read graph, but edges not ordered correctly. Correct data structures used. Queue-based topological sort is implemented correctly, but order differs from lecture description. Correct data structures used. Correctly implemented pseudo-code to update the network states but does not use the calculated topologically sorted order. Correct data structures used. DFS-based topological sort is implemented correctly, but order differs from lecture description (e.g. DFS not based on recursion) Correctly identified cycles. Correct data structures used.