img
All Q&A
1

Write short notes on

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

 

28 November, 2022
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.
2

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.

28 November, 2022
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.
3

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.

28 November, 2022
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:
4

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

28 November, 2022
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.
6

Write short notes on

  • Kruskal’s algorithm for finding MST
  • Graph coloring problem
28 November, 2022
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.
7

Write a short note on Asymptotic Notations.

28 November, 2022
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.