img
img
All Q&A
1

Write short notes on

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

 

 3 December, 2024
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.

 3 December, 2024
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.

 3 December, 2024
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. 

 3 December, 2024
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.
5

Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.

 3 December, 2024
Deadlines and profits are mentioned as follows:
6

Write short notes on

  • Kruskal’s algorithm for finding MST
  • Graph coloring problem
 3 December, 2024
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.

 3 December, 2024
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
Computer Graphics and Multimedia Data Structures & Algorithm Software Engineering Database Management System C Programming and Practices Compiler Design
Browse Streams
img
Computer Science & Engineering
img
Electrical Engineering
img
Electronics & Communication Engineering
img
Civil Engineering
About
MindStudy is a preparation hub for all the students. The goal is to make it easier for pupils to get better grades on exams. We have a list of questions with the best answer for each. Professors, Teachers, and Faculty members from a variety of universities, schools, and institutions throughout the world prepare the Q&A.
Contacts
Shunya Intelliware Solution
Kolkata, WB
Mail us at: info@mindstudy.in

Follow us on:
Streams
Top Subjects
Data Structures & Algorithm Database Management System Software Engineering Compiler Design Mobile computing Design and Analysis of Algorithm C Programming and Practices Computer Graphics and Multimedia Basic Electrical Engineering Radio Frequency and Microwave Engineering Analog Communication Electrical Engineering Management Concrete Technology Design of Reinforced Concrete Structures Power Electronics Irrigation Engineering surveying
MindStudy © Copyright 2022, All rights reserved.
Home About Contact