These have been collected from books, other courses, and actual interview questions. Any starred question will not be asked in the exam. Unless otherwise stated, assume a graph G is simple, undirected, and unweighted. Assume the graph is represented as an adjacency list. For any question, give a clear algorithm as pseudocode, and give a running time analysis

1)Consider a game of snakes and ladders. Determine the minimum number of throws required to win the game.

.2) A triangle is a set of edges {(u, v),(v, w),(w, u)}. (Equivalently, a triangle is a cycle of length 3.) Given a vertex s, we wish to count the number of distinct triangles in G that involve s. Get a solution with O(n) space

3)The diameter of a graph G is the largest shortest path distance in G (meaning, it is maxu,vV dist(u, v), where dist(u, v) is the shortest path distance). Give an algorithm to compute the diameter of a undirected graph G. Give a more efficient algorithm to determine the diameter of an undirected tree T.