Data Structures Pattern Matching Algorithms MCQ
1. Stable marriage problem is an example of?
a) Branch and bound algorithm
b) Backtracking algorithm
c) Greedy algorithm
d) Divide and conquer algorithm
Answer: b
The stable marriage problem is an example of a recursive algorithm because it recursively uses a backtracking algorithm to find an optimal solution.
2. Which of the following algorithms does the Stable marriage problem uses?
a) Gale-Shapley algorithm
b) Dijkstra’s algorithm
c) Ford-Fulkerson algorithm
d) Prim’s algorithm
Answer: a
A stable marriage problem uses the Gale-Shapley algorithm. The maximum flow problem uses the Ford-Fulkerson algorithm. Prim’s algorithm involves a minimum spanning tree.
3. An optimal solution satisfying men’s preferences is said to be?
a) Man optimal
b) Woman’s optimal
c) Pair optimal
d) Best optimal
Answer: a
An optimal solution satisfying men’s preferences are said to be man optimal. An optimal solution satisfying a woman’s preferences is said to be woman optimal.
4. When a free man proposes to an available woman, which of the following happens?
a) She will think and decide
b) She will reject
c) She will replace her current mate
d) She will accept
Answer: d
When a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list.
5. If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.
a) True
b) False
Answer: a
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.
6. How many 2*2 matrices are used in this problem?
a) 1
b) 2
c) 3
d) 4
Answer: b
Two 2*2 matrices are used. One for men representing corresponding women and ranking and the other for women.
7. What happens when a free man approaches a married woman?
a) She simply rejects him
b) She simply replaces her mate with him
c) She goes through her preference list and accordingly, she replaces her current mate with him
d) She accepts his proposal
Answer: c
If the preference of the man is greater, she replaces her current mate with him, leaving her current mate free.
8. In the case of stability, how many symmetric possibilities of trouble can occur?
a) 1
b) 2
c) 4
d) 3
Answer: b
In the case of stability, there are 2 symmetric possibilities of trouble that can occur.
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.
9. Consider the following ranking matrix. Assume that M1 and W2 are married. Now, M2 approaches W2. Which of the following happens?
a) W2 replaces M1 with M2
b) W2 rejects M2
c) W2 accepts both M1 and M2
d) W2 rejects both M1 and M2
Answer: a
W2 is married to M1. But the preference for W2 has M2 before M1. Hence, W2 replaces M1 with M2.
10. Consider the following ranking matrix. Assume that M1 and W1 are married and M2 and W3 are married. Now, whom will M3 approach first?
a) W1
b) W2
c) W3
d) All three
Answer: c
M3 will approach W3 first. Since W3 is married and since her preference list has her current mate before M3, she rejects his proposal.
11. Who formulated a straight forward backtracking scheme for the stable marriage problem?
a) McVitie and Wilson
b) Gale
c) Ford and Fulkerson
d) Dinitz
Answer: a
McVitie and Wilson formulated a much faster straight forward backtracking scheme for stable marriage problems. Ford and Fulkerson formulated a Maximum flow problem.
12. Can stable marriage can solved using a branch and bound algorithm?
a) True
b) False
Answer: a
A stable marriage problem can be solved using the branch and bound approach because branch and bound follows a backtracking scheme with a limitation factor.
13. What is the prime task of the stable marriage problem?
a) To provide an optimal solution
b) To provide women with optimal solution
c) To determine the stability of marriage
d) To use a backtracking approach
Answer: c
The prime task of a stable marriage problem is to determine the stability of marriage (i.e) finding a man and a woman who prefer each other to others.
14. Which of the following problems is related to the stable marriage problem?
a) Choice of school by students
b) N-queen problem
c) Arranging data in a database
d) Knapsack problem
Answer: a
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.
15. What is the efficiency of the Gale-Shapley algorithm used in stable marriage problems?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
Answer: c
The time efficiency of the Gale-Shapley algorithm is mathematically found to be O(N2) where N denotes a stable marriage problem.
1. _____________ is a matching with the largest number of edges.
a) Maximum bipartite matching
b) Non-bipartite matching
c) Stable marriage
d) Simplex
Answer: a
Maximum bipartite matching is matching with the largest number of edges.
Maximum bipartite matching matches two elements with a property that no two edges share a vertex.
2. Maximum matching is also called maximum cardinality matching.
a) True
b) False
Answer: a
A maximum matching is also called maximum cardinality matching (i.e.) matching with the largest number of edges.
3. How many colors are used in a bipartite graph?
a) 1
b) 2
c) 3
d) 4
Answer: b
A bipartite graph is said to be two-colorable so that every edge has its vertices colored in different colors.
4. What is the simplest method to prove that a graph is bipartite?
a) It has a cycle of an odd length
b) It does not have cycles
c) It does not have a cycle of an odd length
d) Both odd and even cycles are formed
Answer: c
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.
5. A matching that matches all the vertices of a graph is called?
a) Perfect matching
b) Cardinality matching
c) Good matching
d) Simplex matching
Answer: a
A matching that matches all the vertices of a graph is called perfect matching.
6. What is the length of an augmenting path?
a) Even
b) Odd
c) Depends on the graph
d) 1
Answer: b
The length of an augmenting path in a bipartite graph is always said to be always odd.
7. In a bipartite graph G=(V, U, E), the matching of a free vertex in V to a free vertex in U is called?
a) Bipartite matching
b) Cardinality matching
c) Augmenting
d) Weight matching
Answer: c
A simple path from a free vertex in V to a free vertex in U whose edges alternate between edges not in M and edges in M is called an augmenting path.
8. A matching M is maximal if and only if there exists no augmenting path with respect to M.
a) True
b) False
Answer: a
According to the theorem discovered by the French mathematician Claude Berge, it means that the current matching is maximal if there is no augmenting path.
9. Which one of the following is an application for matching?
a) Proposal of marriage
b) Pairing boys and girls for a dance
c) Arranging elements in a set
d) Finding the shortest traversal path
Answer: b
Pairing boys and girls for a dance is a traditional example of matching. The proposal of marriage is an application to stable marriage problems.
10. Which is the correct technique for finding a maximum matching in a graph?
a) DFS traversal
b) BFS traversal
c) Shortest path traversal
d) Heap order traversal
Answer: b
The correct technique for finding a maximum matching in a bipartite graph is by using a Breadth First Search(BFS).
11. The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
a) Maximum-mass matching
b) Maximum bipartite matching
c) Maximum weight matching
d) Maximum node matching
Answer: c
The problem is called maximum weight matching which is similar to bipartite matching. It is also called an assignment problem.
12. What is the total number of iterations used in a maximum-matching algorithm?
a) [n/2]
b) [n/3]
c) [n/2]+n
d) [n/2]+1
Answer: d
The total number of iterations cannot exceed [n/2]+1 where n=|V|+|U| denoting the number of vertices in the graph.
13. What is the efficiency of the algorithm designed by Hopcroft and Karp?
a) O(n+m)
b) O(n(n+m)
c) O(√n(n+m))
d) O(n+2)
Answer: c
The efficiency of the algorithm designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).
14. Who was the first person to solve the maximum matching problem?
a) Jack Edmonds
b) Hopcroft
c) Karp
d) Claude Berge
Answer: a
Jack Edmonds was the first person to solve the maximum matching problem in 1965.
15. From the given graph, how many vertices can be matched using maximum matching in the bipartite graph algorithm?
a) 5
b) 4
c) 3
d) 2
Answer: a
One of the solutions of the matching problem is given by a-w,b-v,c-x,d-y,e-z. Hence the answer is 5.
