Design and Analysis of Algorithms is a fundamental area of computer science focused on creating efficient solutions to computational problems and evaluating their performance. It involves designing algorithms (step-by-step procedures) to solve problems and analyzing their time and space complexity to ensure optimal resource usage. Key topics include sorting, searching, graph algorithms, dynamic programming, and divide-and-conquer strategies. The goal is to develop algorithms that are both correct and efficient, enabling faster and scalable solutions for real-world applications.
12 questions and answers
Write short notes on
A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover. Although the name is Vertex Cover, the set covers all edges of the given graph.
Define classes P,NP,NP hard and NP-complete and also explain their relationship diagrammatically. What is nondeterministic algorithm? Explain with example. Define circuit satisfiability problem and prove that circuit SAT is in NP class.
P- P is the set of decision (or optimization) problems that can be solved by a deterministic algorithm in polynomial time, i.e. O(nk) time where n is the input size and K is non negative value independent of n.
Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Knuth,Moris and Pratt algorithm scan the text array T[1……n] to find that whether a pattern array P[1………..n] appears in the text array by using the auxiliary function П which is called the prefix function.
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Deadlines and profits are mentioned as follows:
Write short notes on
A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges. A single graph can have many different spanning trees.
Write a short note on Asymptotic Notations.
Asymptotic Notations are languages that allow us to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. It is used to describe the asymptotic behaviour of complexities of algorithms.
Why Recursion tree method is best than the Substitution method for solving a recurrence relation? Find the asymptotic upper bound of the following recurrence relation with the help of recursion tree method.
T(n)=T(n/4)+T(n/2)+Θ(n2)
Recursion tree method is best than the Substitution method for solving a recurrence relation because in recursion tree method, we draw a recurrence tree and calculate the time taken by every level of tree.
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
It is a problem solving technique like divide and conquer where problems are divided into subproblems. Dynamic programming is used when the subproblems are not independent.
MindStudy - a preparation hub for all the students. The goal is to make it easier for pupils to get better grades on exams.
Copyright © 2025 MindStudy
A product by Shunya Intelliware Solution
(Registered under MSME Uddyam)
Max-flow min cut theorem for network flow analysis:
If f is a flow in a flow network G(V,E) with source s and sink t, then the following conditions are equivalent: