- Show how to explicitly solve the recurrence equation below (that is, do not simply quote the Master theorem).
- Find the Shortest path start at node “a” to every other node in the following graph.
- Find a Minimum-Spanning Tree for the following graph. What is the time complexity of your algorithm?
- The depth-first search algorithm is a fundamental algorithm for graphs. It can be used to design an algorithm that decides if a graph G contains a cycle. Describe the cycle-finding algorithm. What is the time complexity of your algorithm?
- Let Graph G be connected. Combine DFS and BFS in the following way: Start at a vertex, u, find a neighbor, v, that refers the minimum weight on the edge that links these two vertices. Then move to the new vertex (v) and put this edge in a bucket. When you reach the vertex that is visited you will return to the entering vertex, and so on. If you have visited all vertices, the edges in the bucket will form a spanning tree.
- Is this tree a minimum spanning tree? Verify your answer.
- This method is called the Best Search in AI. The strategy used is the greedy algorithm. Use your own words to explain your finding in (1).
Last Updated on April 21, 2019
