Design And Analysis Of Algorithms Set 15

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 15

Q1 | Find the maximum flow from the following graph.
  • 22
  • 17
  • 15
  • 20
Answer: 15
Explaination:
initially, zero flow is computed. then, computing flow= 7+1+5+2=15. hence, maximum flow=15.
Q2 | A simple acyclic path between source and sink which pass through only positive weighted edges is called?
  • augmenting path
  • critical path
  • residual path
  • maximum path
Answer: augmenting path
Explaination:
augmenting path between source and sink is a simple path without cycles. path consisting of zero slack edges is called critical path.
Q3 | Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.
  • true
  • false
Answer: true
Explaination:
dinic’s algorithm includes construction of level graphs and reslidual graphs and finding of augmenting paths along with blocking flow and is faster than the
Q4 | Who is the formulator of Maximum flow problem?
  • lester r. ford and delbert r. fulkerson
  • t.e. harris and f.s. ross
  • y.a. dinitz
  • kruskal
Answer: t.e. harris and f.s. ross
Explaination:
the first ever people to
Q5 | How many constraints does flow have?
  • one
  • three
  • two
  • four
Answer: two
Explaination:
a flow is a mapping which follows two constraints- conservation of flows and capacity constraints.
Q6 | Stable marriage problem is an example of?
  • branch and bound algorithm
  • backtracking algorithm
  • greedy algorithm
  • divide and conquer algorithm
Answer: backtracking algorithm
Explaination:
stable marriage problem is an example for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution.
Q7 | Which of the following algorithms does Stable marriage problem uses?
  • gale-shapley algorithm
  • dijkstra’s algorithm
  • ford-fulkerson algorithm
  • prim’s algorithm
Answer: gale-shapley algorithm
Explaination:
stable marriage problem uses gale-shapley algorithm. maximum flow problem uses ford-fulkerson algorithm.
Q8 | An optimal solution satisfying men’s preferences is said to be?
  • man optimal
  • woman optimal
  • pair optimal
  • best optimal
Answer: man optimal
Explaination:
an optimal solution satisfying men’s preferences are said to be man optimal. an optimal solution satisfying woman’s preferences are said to be woman optimal.
Q9 | When a free man proposes to an available woman, which of the following happens?
  • she will think and decide
  • she will reject
  • she will replace her current mate
  • she will accept
Answer: she will accept
Explaination:
when a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list.
Q10 | If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.
  • true
  • false
Answer: true
Explaination:
if there are n couples such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable.
Q11 | How many 2*2 matrices are used in this problem?
  • 1
  • 2
  • 3
  • 4
Answer: 2
Explaination:
two 2*2 matrices are used. one for men representing corresponding woman and ranking and the other for women.
Q12 | What happens when a free man approaches a married woman?
  • she simply rejects him
  • she simply replaces her mate with him
  • she goes through her preference list and accordingly, she replaces her current mate with him
  • she accepts his proposal
Answer: she goes through her preference list and accordingly, she replaces her current mate with him
Explaination:
if the preference of the man is greater, she replaces her current mate with him, leaving her current mate free.
Q13 | In case of stability, how many symmetric possibilities of trouble can occur?
  • 1
  • 2
  • 4
  • 3
Answer: 2
Explaination:
possibilities- there might be a woman pw, preferred to w by m, who herself prefers m to be her husband and the same applies to man as well.
Q14 | Which of the following happens?
  • w2 replaces m1 with m2
  • w2 rejects m2
  • w2 accepts both m1 and m2
  • w2 rejects both m1 and m2
Answer: w2 replaces m1 with m2
Explaination:
w2 is married to m1. but the preference of w2 has m2 before m1. hence, w2 replaces m1 with m2.
Q15 | Who formulated a straight forward backtracking scheme for stable marriage problem?
  • mcvitie and wilson
  • gale
  • ford and fulkerson
  • dinitz
Answer: mcvitie and wilson
Explaination:
mcvitie and wilson formulated a much faster straight forward backtracking scheme for stable marriage problem. ford and fulkerson formulated maximum flow problem.
Q16 | Can stable marriage cannot be solved using branch and bound algorithm.
  • true
  • false
Answer: false
Explaination:
stable marriage problem can be solved using branch and bound approach because branch and bound follows backtracking scheme with a limitation factor.
Q17 | What is the prime task of the stable marriage problem?
  • to provide man optimal solution
  • to provide woman optimal solution
  • to determine stability of marriage
  • to use backtracking approach
Answer: to determine stability of marriage
Explaination:
the prime task of stable marriage problem is to determine stability of marriage (i.e) finding a man and a woman who prefer each other to others.
Q18 | Which of the following problems is related to stable marriage problem?
  • choice of school by students
  • n-queen problem
  • arranging data in a database
  • knapsack problem
Answer: choice of school by students
Explaination:
choice of school by students is the most related example in the given set of options since both school and students will have a preference list.
Q19 | What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?
  • o(n)
  • o(n log n)
  • o(n2)
  • o(log n)
Answer: o(n2)
Explaination:
the time efficiency of gale- shapley algorithm is mathematically found to be o(n2) where n denotes stable marriage problem.
Q20 |                            is a matching with the largest number of edges.
  • maximum bipartite matching
  • non-bipartite matching
  • stable marriage
  • simplex
Answer: maximum bipartite matching
Explaination:
maximum bipartite matching matches two elements with a property that no two edges share a vertex.
Q21 | Maximum matching is also called as maximum cardinality matching.
  • true
  • false
Answer: true
Explaination:
maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges.
Q22 | How many colours are used in a bipartite graph?
  • 1
  • 2
  • 3
  • 4
Answer: 2
Explaination:
a bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours.
Q23 | What is the simplest method to prove that a graph is bipartite?
  • it has a cycle of an odd length
  • it does not have cycles
  • it does not have a cycle of an odd length
  • both odd and even cycles are formed
Answer: it does not have a cycle of an odd length
Explaination:
it is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length.
Q24 | A matching that matches all the vertices of a graph is called?
  • perfect matching
  • cardinality matching
  • good matching
  • simplex matching
Answer: perfect matching
Explaination:
a matching that matches all the vertices of a graph is called perfect matching.
Q25 | What is the length of an augmenting path?
  • even
  • odd
  • depends on graph
  • 1
Answer: odd
Explaination:
the length of an augmenting path in a bipartite graph is always said to be always odd.
Previous Next