Syllabus for 3rd IA: Design and Analysis of Algorithms

Heapsort:

Sort the given list of elements 2, 9, 7, 6, 5, 8 by heapsort.

0/1 Knapsack problem:
Solve the knapsack problem using dynamic programming technique.
n=4,
w1,w2,w3,w4=(2,1,3,2)
v1,v2,v3,v4=(12,10,20,15)
W=5

Bellman Ford Algorithm:
Apply Bellman Ford algorithm to find shortest path from source vertex S to other vertices of a given graph. (As given in notes).

Multistage Graph Problem:
Solve the multistage graph problem using dynamic programming between node1 to node12 and also evaluate the cost of shortest path. (Refer notes for graph)

Warshall Algorithm:
Apply warshall algorithm for the given diagraph to find its transitive closure. (refer notes for graph)

Floyd's Algorithm:
Apply Floyd's algorithm for the given diagraph to find all pairs shortest paths for the given graph (refer notes for graph)

Optimal Binary Search Tree (BST)
Apply dynamic programming technique to constrcut optimal BST for the given keys and their probabilities. (refer table of values from notes)

n-Queens Problem:
Solve 4-Queens problem.