Algorithms AssignmentInstitutionNameDate Pouring Water:(a)Let P = (V, E) represent our directed graph. We then have to model the nodes as a triple of numbers (a_0,a_(1,) a_2) where, S_0 =10, S_1 = 7, S_2 = 4 are the sizes of the containers. a_i will correspond with the real contents of the ith container.It must be also true that 0

In addition, an edge between two nodes (a_0,a_(1,) a_2)) and (b_0,b_(1,) b_2)) exists if the below conditions are satisfied: The given two nodes differ in exactly two coordinates, and the third is equal in both.When i,j are the coordinates which they differ in, then a_i=0 or a_j=0 or a_i=S_i or a_j= S_i.The specific question that need to be addressed is whether there is an existence of a path between the nodes (0, 7, 4) and (*, 2, *) or (*, *, 2).

And * represents any allowed value of the corresponding coordinate.(b). x y ab c z(c). It is recommended that a DFS algorithm need to be applied on the graph beginning from node (0, 7, 4) having an extra line of code which ends and gives a YES answer whenever on on of the desired nodes is reached. It will also answer NO when a connected component of the starting node is finished and there is no desired vertex that can be reached.(d).YES there is a sequence of pouring.

This is because it is pretty easy to see that after a few steps of the algorithm, the node (2, 7, 2) is reached.2.(a). The issue with negative edges is that the change to negative weights when we modify the edge weights and the outcome might not become an exact tree. So a simple solution for this is that when we have negative routes, we multiply them with a large constant number.Now, having a graph of negative edges, we cannot be sure that the spanning tree we get is a tree. We could get a minimum spanning graph and not a minimum spanning tree.

Therefore, whenever we are provided with negative edges, it is never a tree but rather a graph.(b). We can solve this using Kruskal’s algorithm. Minimum spanning tree concept allows weights having arbitrary signs. Here all negative edges can be added a big and constant positive number in order to avoid a clash between remaining positive edges. In the end, the tree will remain as a minimum spanning tree.3.

An Euler path visits every edge on a graph exactly once. On the other hand, a Eulerian cycle in a Euler path that begins and closes on a similar vertex.Finding whether a graph is Eulerian or notGraphs are termed as Eulerian if they contain a Euler cycle and are termed as Semi-Euler in the event that they contain a Euler path. It is great, we can discover whether a given chart has an Euler Path or not in polynomial time, we can discover it by O (V+E) timeEuler CycleAn undirected graph has Euler cycle when these statements are valid.

a) Every vertices having non-zero degree are connected. We couldn’t care less about vertices with zero degree since they don’t have a place with Euler Cycle or Path (we just consider all edges).b) Entire vertices have even degrees.Euler PathUndirected graphs contain Euler Paths whenever the below two statements are true.a) Similar as condition (a) for Euler Cycleb) if zero or twin vertices have odd degree and all different vertices have even degree. Note that just a single vertex with odd degree isn’t conceivable in an undirected diagram (aggregate of all degrees is constantly even in an undirected chart)The Algorithm to determine whether a graph has an Euler path or not.

Choose a random vertex from your graph as a starting point. Moving from vertex to vertex, mark your path. Travel along any edges you want but not the edges that are bridges for the graph, unless you have to.

Do these until you come back to your starting point?Why does the algorithm work?Whenever we visit vertex v, we step by step go through two unvisited edges with one end point as v. For this reason, all center vertices in Euler Path needs to an even degree. For Euler Cycle, any vertex can be center vertex, hence all vertices must have even degree.Complexity of this algorithmIt has a time complexity of O (|E|^2).This time complexity can however be improved into O (|E| (log |E|) ^3 log log |E|).(b) This general game of N toothpicks is pretty complex.

However, if N is divisible by 3 plus 2, player 1 is able to force a win. If N is divisible by 3 plus 2, then player 2 can also force a win. This is to say that the winning strategy for player 1 is: In the event that the toothpicks number is a multiple of 3, pick 2 toothpicks.In the event that the toothpicks number is a multiple of 3 plus 2, pick just one toothpick.(c). Repeating (a) and (b) where player taking the last toothpick loses. (a) Model of the game#include