Quiznetik

Design and Analysis of Algorithms | Set 4

1. Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?

A. number of vertices in u = number of vertices in v

B. sum of degrees of vertices in u = sum of degrees of vertices in v

C. number of vertices in u > number of vertices in v

D. nothing can be said

Correct : B. sum of degrees of vertices in u = sum of degrees of vertices in v

2. A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?

A. number of vertices in u=number of vertices in v

B. number of vertices in u not equal to number of vertices in v

C. number of vertices in u always greater than the number of vertices in v

D. nothing can be said

Correct : A. number of vertices in u=number of vertices in v

3. A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?

A. n

B. n/2

C. n/4

D. data insufficient

Correct : B. n/2

4. When is a graph said to be bipartite?

A. if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b

B. if the graph is connected and it has odd number of vertices

C. if the graph is disconnected

D. if the graph has at least n/2 vertices whose degree is greater than n/2

Correct : A. if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b

5. Are trees bipartite?

A. yes

B. no

C. yes if it has even number of vertices

D. no if it has odd number of vertices

Correct : A. yes

6. A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)

A. 100

B. 140

C. 80

D. 20

Correct : A. 100

7. Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite?

A. yes

B. no

Correct : A. yes

8. Can there exist a graph which is both eulerian and is bipartite?

A. yes

B. no

C. yes if it has even number of edges

D. nothing can be said

Correct : A. yes

9. A graph is found to be 2 colorable. What can be said about that graph?

A. the given graph is eulerian

B. the given graph is bipartite

C. the given graph is hamiltonian

D. the given graph is planar

Correct : B. the given graph is bipartite

10. Which type of graph has no odd cycle in it?

A. bipartite

B. histogram

C. cartesian

D. pie

Correct : A. bipartite

11. What type of graph has chromatic number less than or equal to 2?

A. histogram

B. bipartite

C. cartesian

D. tree

Correct : B. bipartite

12. Which of the following is the correct type of spectrum of the bipartite graph?

A. symmetric

B. anti – symmetric

C. circular

D. exponential

Correct : A. symmetric

13. Which of the following is not a property of the bipartite graph?

A. no odd cycle

B. symmetric spectrum

C. chromatic number is less than or equal to 2

D. asymmetric spectrum

Correct : D. asymmetric spectrum

14. Which one of the following is the chromatic number of bipartite graph?

A. 1

B. 4

C. 3

D. 5

Correct : A. 1

15. Which graph has a size of minimum vertex cover equal to maximum matching?

A. cartesian

B. tree

C. heap

D. bipartite

Correct : D. bipartite

16. Which theorem gives the relation between the minimum vertex cover and maximum matching?

A. konig’s theorem

B. kirchhoff’s theorem

C. kuratowski’s theorem

D. kelmans theorem

Correct : A. konig’s theorem

17. Which of the following is not a property of perfect graph?

A. compliment of line graph of bipartite graph

B. compliment of bipartite graph

C. line graph of bipartite graph

D. line graph

Correct : D. line graph

18. Which of the following has maximum clique size 2?

A. perfect graph

B. tree

C. histogram

D. cartesian

Correct : A. perfect graph

19. What is the chromatic number of compliment of line graph of bipartite graph?

A. 0

B. 1

C. 2

D. 3

Correct : C. 2

20. What is the clique size of the line graph of bipartite graph?

A. 0

B. 1

C. 2

D. 3

Correct : C. 2

21. It is possible to have a negative chromatic number of bipartite graph.

A. true

B. false

Correct : B. false

22. Every Perfect graph has forbidden graph characterization.

A. true

B. false

Correct : A. true

23. Which structure can be modelled by using Bipartite graph?

A. hypergraph

B. perfect graph

C. hetero graph

D. directed graph

Correct : A. hypergraph

24. Which type of graph has all the vertex of the first set connected to all the vertex of the second set?

A. bipartite

B. complete bipartite

C. cartesian

D. pie

Correct : B. complete bipartite

25. Which graph is also known as biclique?

A. histogram

B. complete bipartite

C. cartesian

D. tree

Correct : B. complete bipartite

26. Which term defines all the complete bipartite graph that are trees?

A. symmetric

B. anti – symmetric

C. circular

D. stars

Correct : D. stars

27. How many edges does a n vertex triangle free graph contains?

A. n2

B. n2 + 2

C. n2 / 4

D. n3

Correct : C. n2 / 4

28. Which graph is used to define the claw free graph?

A. bipartite graph

B. claw graph

C. star graph

D. cartesian graph

Correct : B. claw graph

29. What is testing of a complete bipartite subgraph in a bipartite graph problem called?

A. p problem

B. p-complete problem

C. np problem

D. np-complete problem

Correct : D. np-complete problem

30. Which graph cannot contain K3, 3 as a minor of graph?

A. planar graph

B. outer planar graph

C. non planar graph

D. inner planar graph

Correct : A. planar graph

31. Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?

A. (nm)1/2

B. (-nm)1/2

C. 0

D. nm

Correct : D. nm

32. Which complete graph is not present in minor of Outer Planar Graph?

A. k3, 3

B. k3, 1

C. k3, 2

D. k1, 1

Correct : C. k3, 2

33. Is every complete bipartite graph a Moore Graph.

A. true

B. false

Correct : A. true

34. What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?

A. 1

B. n + m – 2

C. 0

D. 2

Correct : B. n + m – 2

35. Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?

A. n + m

B. n

C. 0

D. n*m

Correct : D. n*m

36. What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value?

A. 1

B. m-1

C. n-1

D. 0

Correct : B. m-1

37. Is it true that every complete bipartite graph is a modular graph.

A. true

B. false

Correct : A. true

38. How many spanning trees does a complete bipartite graph contain?

A. nm

B. mn-1 * nn-1

C. 1

D. 0

Correct : B. mn-1 * nn-1

39. What does Maximum flow problem involve?

A. finding a flow between source and sink that is maximum

B. finding a flow between source and sink that is minimum

C. finding the shortest path between source and sink

D. computing a minimum spanning tree

Correct : A. finding a flow between source and sink that is maximum

40. A network can have only one source and one sink.

A. false

B. true

Correct : B. true

41. What is the source?

A. vertex with no incoming edges

B. vertex with no leaving edges

C. centre vertex

D. vertex with the least weight

Correct : A. vertex with no incoming edges

42. Which algorithm is used to solve a maximum flow problem?

A. prim’s algorithm

B. kruskal’s algorithm

C. dijkstra’s algorithm

D. ford-fulkerson algorithm

Correct : D. ford-fulkerson algorithm

43. Does Ford- Fulkerson algorithm use the idea of?

A. naïve greedy algorithm approach

B. residual graphs

C. minimum cut

D. minimum spanning tree

Correct : B. residual graphs

44. The first step in the naïve greedy algorithm is?

A. analysing the zero flow

B. calculating the maximum flow using trial and error

C. adding flows with higher values

D. reversing flow if required

Correct : A. analysing the zero flow

45. Under what condition can a vertex combine and distribute flow in any manner?

A. it may violate edge capacities

B. it should maintain flow conservation

C. the vertex should be a source vertex

D. the vertex should be a sink vertex

Correct : B. it should maintain flow conservation

46. Find the maximum flow from the following graph.

A. 22

B. 17

C. 15

D. 20

Correct : C. 15

47. A simple acyclic path between source and sink which pass through only positive weighted edges is called?

A. augmenting path

B. critical path

C. residual path

D. maximum path

Correct : A. augmenting path

48. Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.

A. true

B. false

Correct : A. true

49. Who is the formulator of Maximum flow problem?

A. lester r. ford and delbert r. fulkerson

B. t.e. harris and f.s. ross

C. y.a. dinitz

D. kruskal

Correct : B. t.e. harris and f.s. ross

50. How many constraints does flow have?

A. one

B. three

C. two

D. four

Correct : C. two

51. Stable marriage problem is an example of?

A. branch and bound algorithm

B. backtracking algorithm

C. greedy algorithm

D. divide and conquer algorithm

Correct : B. backtracking algorithm

52. Which of the following algorithms does Stable marriage problem uses?

A. gale-shapley algorithm

B. dijkstra’s algorithm

C. ford-fulkerson algorithm

D. prim’s algorithm

Correct : A. gale-shapley algorithm

53. An optimal solution satisfying men’s preferences is said to be?

A. man optimal

B. woman optimal

C. pair optimal

D. best optimal

Correct : A. man optimal

54. 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

Correct : D. she will accept

55. 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

Correct : A. true

56. How many 2*2 matrices are used in this problem?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

57. 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

Correct : C. she goes through her preference list and accordingly, she replaces her current mate with him

58. In case of stability, how many symmetric possibilities of trouble can occur?

A. 1

B. 2

C. 4

D. 3

Correct : B. 2

59. 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

Correct : A. w2 replaces m1 with m2

60. Who formulated a straight forward backtracking scheme for stable marriage problem?

A. mcvitie and wilson

B. gale

C. ford and fulkerson

D. dinitz

Correct : A. mcvitie and wilson

61. Can stable marriage cannot be solved using branch and bound algorithm.

A. true

B. false

Correct : B. false

62. What is the prime task of the stable marriage problem?

A. to provide man optimal solution

B. to provide woman optimal solution

C. to determine stability of marriage

D. to use backtracking approach

Correct : C. to determine stability of marriage

63. Which of the following problems is related to stable marriage problem?

A. choice of school by students

B. n-queen problem

C. arranging data in a database

D. knapsack problem

Correct : A. choice of school by students

64. What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(log n)

Correct : C. o(n2)

65. is a matching with the largest number of edges.

A. maximum bipartite matching

B. non-bipartite matching

C. stable marriage

D. simplex

Correct : A. maximum bipartite matching

66. Maximum matching is also called as maximum cardinality matching.

A. true

B. false

Correct : A. true

67. How many colours are used in a bipartite graph?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

68. 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

Correct : C. it does not have a cycle of an odd length

69. A matching that matches all the vertices of a graph is called?

A. perfect matching

B. cardinality matching

C. good matching

D. simplex matching

Correct : A. perfect matching

70. What is the length of an augmenting path?

A. even

B. odd

C. depends on graph

D. 1

Correct : B. odd

71. 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

Correct : C. augmenting

72. A matching M is maximal if and only if there exists no augmenting path with respect to M.

A. true

B. false

Correct : A. true

73. 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

Correct : B. pairing boys and girls for a dance

74. 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

Correct : B. bfs traversal

75. 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

Correct : C. maximum weight matching

76. Who was the first person to solve the maximum matching problem?

A. jack edmonds

B. hopcroft

C. karp

D. claude berge

Correct : A. jack edmonds

77. From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?

A. 5

B. 4

C. 3

D. 2

Correct : A. 5

78. The worst-case efficiency of solving a problem in polynomial time is?

A. o(p(n))

B. o(p( n log n))

C. o(p(n2))

D. o(p(m log n))

Correct : A. o(p(n))

79. Problems that can be solved in polynomial time are known as?

A. intractable

B. tractable

C. decision

D. complete

Correct : B. tractable

80. The sum and composition of two polynomials are always polynomials.

A. true

B. false

Correct : A. true

81. is the class of decision problems that can be solved by non- deterministic polynomial algorithms?

A. np

B. p

C. hard

D. complete

Correct : A. np

82. Problems that cannot be solved by any algorithm are called?

A. tractable problems

B. intractable problems

C. undecidable problems

D. decidable problems

Correct : C. undecidable problems

83. The Euler’s circuit problem can be solved in?

A. o(n)

B. o( n log n)

C. o(log n)

D. o(n2)

Correct : D. o(n2)

84. To which class does the Euler’s circuit problem belong?

A. p class

B. np class

C. partition class

D. complete class

Correct : A. p class

85. Halting problem is an example for?

A. decidable problem

B. undecidable problem

C. complete problem

D. trackable problem

Correct : B. undecidable problem

86. How many stages of procedure does a non- deterministic algorithm consist of?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

87. A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial.

A. true

B. false

Correct : A. true

88. How many conditions have to be met if an NP- complete problem is polynomially reducible?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

89. To which of the following class does a CNF-satisfiability problem belong?

A. np class

B. p class

C. np complete

D. np hard

Correct : C. np complete

90. How many steps are required to prove that a decision problem is NP complete?

A. 1

B. 2

C. 3

D. 4

Correct : B. 2

91. Which of the following problems is not NP complete?

A. hamiltonian circuit

B. bin packing

C. partition problem

D. halting problem

Correct : D. halting problem

92. The choice of polynomial class has led to the development of an extensive theory called

A. computational complexity

B. time complexity

C. problem complexity

D. decision complexity

Correct : A. computational complexity

93. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?

A. branch and bound

B. iterative improvement

C. divide and conquer

D. greedy algorithm

Correct : A. branch and bound

94. The problem of finding a path in a graph that visits every vertex exactly once is called?

A. hamiltonian path problem

B. hamiltonian cycle problem

C. subset sum problem

D. turnpike reconstruction problem

Correct : A. hamiltonian path problem

95. Hamiltonian path problem is

A. np problem

B. n class problem

C. p class problem

D. np complete problem

Correct : D. np complete problem

96. There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.

A. true

B. false

Correct : B. false

97. Which of the following problems is similar to that of a Hamiltonian path problem?

A. knapsack problem

B. closest pair problem

C. travelling salesman problem

D. assignment problem

Correct : C. travelling salesman problem

98. Who formulated the first ever algorithm for solving the Hamiltonian path problem?

A. martello

B. monte carlo

C. leonard

D. bellman

Correct : A. martello

99. In what time can the Hamiltonian path problem can be solved using dynamic programming?

A. o(n)

B. o(n log n)

C. o(n2)

D. o(n2 2n)

Correct : D. o(n2 2n)

100. In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.

A. true

B. false

Correct : A. true