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

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

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

Write short notes on time complexity, graphs and trees.

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

Define algorithm and explain its characteristics with a suitable example.

Explain Strassen's matrix multiplication algorithm and find its time complexity.

Explain recurrence relations and methods to solve them.

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

Explain the divide and conquer technique with reference to merge sort.

Apply binary search to find a target element in a given sorted array, showing the steps.

Trace the execution of merge sort on a given list of elements.

Explain data transfer optimization with example.

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

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

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

Explain the greedy method. Discuss its strategy and characteristics.

Explain single source shortest path problem with suitable example.

Explain Prim's algorithm and find its time complexity.

Explain optimal merge (pattern) in brief.

Write an algorithm for Huffman code. How does it work? Explain with a example.

Construct minimum cost spanning tree using both Prim's algorithm and Kruskal's algorithm.

How do you prove the Correctness proof of Greedy algorithm? Explain.

What is dynamic programming? Explain its characteristics / features.

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

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

Explain the multistage graph concept with reference to a given graph.

Differentiate between dynamic programming and divide and conquer.

Explain Floyd Warshall algorithm problem with the graph given in figure.

What is a graph and a multistage graph, and what are the applications of a multistage graph?

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

Explain the graph coloring problem with a suitable example.

Explain the different uses and applications of lower bound theory.

Apply the branch and bound algorithm to solve the travelling salesperson problem for a given graph.

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.

Write short notes on any two of: Parallel Algorithm, Huffman Coding, Space Complexity, Traveling Sales Person Problem

Explain the 8-queens problem and write a backtracking algorithm to solve it.

Explain the general method of branch and bound.

Design Horner's algorithm for polynomial evaluation.

Write short notes on any two of: Parallel Algorithms, Data Stream Algorithms, Logic Optimization, Optimal Merge Patterns

Explain how lower bound theory is used to solve algebraic problems.

Explain NP-hard and NP-complete problems with suitable examples.

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

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

What are approximation algorithms? Explain their need and applications.

Discuss advanced tree and graph algorithms. Explain the importance of shortest path algorithms.

Write short notes on data stream algorithms and parallel algorithms.

What are B-trees? How are they created? Give its advantages.