Design& Analysis of Algorithms (CY-502) - Important Questions

Define an algorithm and explain time and space complexity and the concept of time-space tradeoff.

Define time complexity and explain the asymptotic notations O, Omega and Theta with examples.

Explain recurrence relations and methods to solve them.

Solve the recurrence T(n)=2T(n/2) + n using Master's method.

Write and solve the recurrence relation for Strassen's matrix multiplication.

Describe the job sequencing with deadlines problem and find the optimal sequence for given profits and deadlines.

Compute the optimal solution for the fractional knapsack problem using the greedy method given number of items, capacity, profits and weights.

Define spanning tree and construct a minimum spanning tree for a given graph using Kruskal's algorithm.

What is the multistage graph problem and how is it solved using the dynamic programming approach, including algorithm and computing time?

Solve the 0/1 knapsack problem using dynamic programming with N=3, profits/values (1,2,5) and weights (2,3,4) for capacity 5.

Explain the 8-queens problem and the concept of backtracking with reference to it, including the state space tree.

Describe the graph coloring / m-coloring problem and give an algorithm for it, including application to an example graph.

Explain the method of reduction to solve the travelling salesperson problem using branch and bound.

Explain the different uses and applications of lower bound theory.

Compare and contrast NP-hard vs NP-complete classes.

Explain what is a data stream algorithm, how it is used, with an example.