Write an algorithm to compute an by left to right binary exponentiation method and illustrate through an example.

Do the complexity analysis of the above algorithm.

Put the following classes of algorithm in the increasing order of growth: O(n log2 0(1og2

Using the definition of Big Oh, show that 20

What is the difference between a graph and a tree Draw four spanning trees of the following graph:

<img src='./qimages/15197-1e.jpg'>

2. Apply Kruskal's algorithm to find a minimum cost spanning tree of the following graph:

<img src='./qimages/15197-2.jpg'>

Apply the Merge Sort algorithm to sort the following list:

15 5 8 7 4 20 25

Describe any two methods of solving the recurrence relation.

4. Explain the following terms with examples:

Complete graph

Combinatorial problems

Branch and bound technique

Loose bound

Average case

Find the optimal solution to the knapsack instance (fractional)

n M =10

24, 32, 18,20)

What is a single source shortest path problem? What are the proposed solutions