haimadrian / internetprogramming-graphalgorithms Goto Github PK

Write some unit tests that test the algorithm implemented at #3 , with various inputs, to make sure the output of the algorithm is correct.
Use at least:
Graph with no path
Graph with a single path
Graph with 3 shortest paths
Graph with one shortest path, but having more than 1 path

Make sure the paths might contain circles, and that they are ignored.

Write some unit tests that test the game implemented at #5 , with various inputs, to make sure the output of the algorithm is correct.
Use at least:
Graph with no submarines
Graph with a single submarine
Graph with illegal submarine (length = 1)
Graph with illegal submarine (cross)
Graph with 3 submarines, according to Nathan's example

Make sure the submarines are not simple. (use some with width and height bigger than 1.)
For example:
[ 1, 1, 0, 1, 1 ]
[ 1, 1, 0, 1, 1 ]
[ 0, 0, 0, 1, 1 ]
[ 1, 1, 0, 1, 1 ]

Write some unit tests that test the algorithm implemented at #1 , with various inputs, to make sure the output of the algorithm is correct.
Use at least:
Graph with no 1's
Graph with a single connected component
Graph with 3 connected components

Make sure the connected components are not simple.
For example: (Two connected components)
[ 1, 1, 0, 1, 1 ]
[ 1, 0, 0, 1, 1 ]
[ 1, 1, 0, 1, 1 ]
[ 1, 0, 0, 1, 1 ]

Algorithm 4
Implement an algorithm such that given a graph and two indices (source and destination) the algorithm will find all shortest paths from source index to second index.
In this algorithm, we use a weighted graph, so the algorithm should find the paths with the minimum total weight.

(Dijkstra and BFS are not working here. Find Dijkstra that works with negative numbers: Bellman-Ford Algorithm)

Algorithm 2
Implement an algorithm such that given a graph and two indices (source and destination) the algorithm will find all shortest paths from source index to seconds index.
This task is limited to use a single thread only.

Algorithm 3

• A submarine must be of length 2 at least. (vertical or horizontal, but not cross)
• Minimum distance between two submarines is 1 cell. e.g. [ 1, 1, 0, 1, 1]
• A submarine might be wider than 1 cell. e.g.
  [ 1, 1, 0 ]
  [ 1, 1, 0 ]

Output of the game is the amount of legal submarines on a board. (matrix/graph)

Algorithm 1
In this algorithm we need to find all connected components (standard and cross) in a graph, and return them.
Check if multiple threads can be used in order to make the search operation faster. For example, assume a 500x500 matrix, multiple threads can scan it faster. Though for a 10x10 matrix, spawning threads might be redundant overhead.