Calculate the output of a neuron

Assignment Help Data Structure & Algorithms
Reference no: EM131065957

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 model led 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

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

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.

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

Unit learning outcomes

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 ICTproducts and services;

3. analyse algorithms and code to determine the runtime(and space) complexity, and evaluate strengths and weaknesses of potential algorithms; 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.

Reference no: EM131065957

Questions Cloud

Weaknesses with measurement technique : Suppose that Australia's price level is 125, the British price level is 100, and the nominal exchange rate of pounds to the dollar is £0.60 = $1. Calculate the real exchange rate of pounds to the dollar. Show all workings. Explain how the CPI is c..
Compute the total, price and quantity variances for material : Wales Company purchased (at a cost of $11,680) and used 2,000 pounds of materials during May. Wales's standard cost of materials per unit produced is based on 2.70 pounds per unit at a cost $5.90 per pound. Production in May was 680 units.
How do we define economics as a social science : How do we define economics as a social science? How do we define the concept of opportunity cost? Provide a simple example. Define microeconomics, stating how it is different from macroeconomics. Provide an example for a microeconomic issue.
Determining the process of bankruptcy : The assets of the business raised £52,500, out of which £4,204 was paid in fees during the process of bankruptcy. (a) Calculate the ratio of assets, before fees, to liabilities, in its simplest terms
Calculate the output of a neuron : KIT205 Data Structures and Algorithms - 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 possibl..
Measure also the motor speed if it is necessary : I read about some parameters estimation toolbox in SIMULINK but I couldn't understand it well. I knew that it can find the parameters of a motor using measurements data. I watched also some videos explaining that. However, this is not enough to un..
Calculate the total cost of production per period : Calculate the level of output for which the total cost of production using Method X is equal to the total cost of production using Method Y. Calculate the total cost of production per period for Method Y at this output.
A nongovernmental nonprofit-account for money : How does a nongovernmental nonprofit, account for money, raised at a benefit auction that is restricted by the donors for capital improvements? 1. The balance sheet will report the donations as a part of permanently restricted net assets.
Do you see evidence of that wall within your life : Consider the following questions to guide you as you complete your posting: "Do you see evidence of that wall within your life?" "How does the misunderstanding about God's nature in this way pose a threat to home life?" my email Ministerjmoore@yah..

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Various search trees and numerous sorting techniques

This week we were introduced to various search trees and numerous sorting techniques. Taking into consideration what you have learned this week, discuss how you can help Bob with his problem.

  Convert the following expression in postfix

Convert the following expression in postfix (reverse Polish notation). Remember the rules of precedence for arithmetic operators. To get full credit, you need to show all work done. i.e. sample snapshot of the stack

  Analyze the time-space complexity of algorithms

How a vEB tree can be used to support these three operations and analyze the time/space complexity of your algorithms.

  Create list of major steps to follow to get input

Create a list of major steps to follow to get input, process, and output desired information (software requirements). Refine the list to include individual refined steps (algorithm).

  Your algorithm will keep track of a customers purchases at

your algorithm will keep track of a customers purchases at the local fireworks stand. customers will not know exactly

  Prepare a flowchart to solve any linear equation

Prepare a flowchart to solve any linear equation ax^2+bx+C=0

  Exhibit an algorithm that detects automation

Exhibit an algorithm that detects whether one finite automaton accepts a subset of the set accepted by another machine.

  Write a code fragment to find the hottest and coldest days

Declare an array of double of size 365 to store daily temperatures for one year. Using this data structure, write a code fragment to find the hottest and coldest days of the year. The average temperature of each month.

  Currency conversion developmentapplication-level

currency conversion developmentapplication-level requirements list1. the program will prompt the user for data input of

  Write a program to take n elements and insert them into heap

Write a program to take n elements and insert them into a heap one by one. Include a function to print out the elements in the heap.

  Write a class called beer

Write a class called Beer in which it given this format:- Intance variables, methodes, intoxicated Etc.

  Design a linear algorithm

The Russian flag problem is to rearrange an array of characters R, W, and B so that R is the first character, R is followed by a W, W is followed by a B, B is followed by another R, and the pattern repeats. Design a linear algorithm (pseudo code)..

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd