Design and Analysis of Algorithm

All Q&A

Write short notes on

Vertex cover problem
Strassen’s matrix multiplication
Approximation algorithm and its uses

9 December, 2023

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.

9 December, 2023

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.

State the Max-flow min cut theorem for network flow analysis. Trace the execution of Ford-Fulkerson algorithm for finding the maximum flow in the graph.

9 December, 2023

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:

Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.

9 December, 2023

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.

9 December, 2023

Deadlines and profits are mentioned as follows:

Write short notes on

Kruskal’s algorithm for finding MST
Graph coloring problem

9 December, 2023

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.

9 December, 2023

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.

Subjects

Mobile computing Data Structures & Algorithm Software Engineering Database Management System Compiler Design Computer Graphics and Multimedia

Browse Streams