Describe All-Pair Shortest Path problem and discuss O(n^3) algorithm to solve it.

Discuss the Floyd-Warshall algorithm.

What do you mean by Backtracking? Explain.

Explain the Hamiltonian circuit problem with an example.

Discuss the N-Queen Problem.

Explain the Subset-Sum Problem..

Describe travelling salesman problem(TSP). Show that a TSP can be solved using backtracking method in the exponential time.

What do you mean by “Greedy Algorithm”? Write its pseudo code and prove that the fractional knapsack problem has a greedy-choice property.

Write the difference between Backtracking and Branch and Bound approach.

Write Branch and Bound algorithm for Knapsack problem.

Write Branch and Bound algorithm for Travelling salesman problem.

What do you mean by graph coloring and graph coloring problem? What do you mean by optimal coloring of a graph? Show that every bipartite graph is 2-colorable.