18CSC305J-Artificial Intelligence

18CSC305J - Artificial Intelligence

Unit 2

MCQ QUESTIONS

# Question Answer
Which search is implemented with an empty first-in-first-out
queue?

1 A. Depth-first search B
B. Breadth-first search
C. Bidirectional search
D. None of the mentioned
What is the other name of informed search strategy?

2 A. Simple search B
B. Heuristic search
C. Online search
D. None of the mentioned
A* algorithm is based on

A. Breadth-First-Search
3 D
B. Depth-First-Search
C. Uniform Cost Search
D. Best-First-Search
Strategies that know whether one non-goal state is “more
promising” than another are called

4 A. Informed & Unformed Search D

B. Unformed Search

1
18CSC305J-Artificial Intelligence

C. Heuristic & Unformed Search

D. Informed & Heuristic Search

2
18CSC305J-Artificial Intelligence

Which of the following algorithms keeps track of ‘k’ states instead

of just one?

A. Hill-Climbing search
5 B
B. Local Beam search
C. Stochastic hill-climbing search
D. Random restart hill-climbing search
E. None of these
A common assumption about the players in a game is that

A. Neither player knows the payoff matrix.

6 D
B. The players have different information about the payoff matrix.
C. Only one of the players pursues a rational strategy.
D. The specific identity of the players is irrelevant to the play of
the game.
Which search implements stack operation for searching the
states?

7 A. Depth-limited search B
B. Depth-first search
C. Breadth-first search
D. None of the mentioned
Though local search algorithms are not systematic, key
advantages would include

8 A. Less memory D
B. More time
C. Finds a solution in large infinite space
D. Less memory & Finds a solution in large infinite space
Uninformed search strategies are better than informed search
strategies.

3
18CSC305J-Artificial Intelligence

9 A
A. True
B. False

4
18CSC305J-Artificial Intelligence

The is a touring problem in which each city must be

visited exactly once. The aim is to find the shortest tour.

A. Finding shortest path between a source and a destination

10 B
B. Travelling Salesman problem
C. Map coloring problem
D. Depth first search traversal on a given map represented as a
graph
When is breadth-first search optimal?

11 A. When there is less number of nodes B

B. When all step costs are equal
C. When all step costs are unequal
D. Both a & c
When will Hill-Climbing algorithm terminate?

12 A. Stopping criterion met C

B. Global Min/Max is achieved
C. No neighbor has higher value
D. All of the above
Is optimality and completeness exists in bidirectional search
algorithm?

13 A. Yes, Yes A
B. No, Yes
C. Yes, No
D. No, No
Best-First search is a type of informed search, which uses
to choose the best next node for expansion.

14 A. Evaluation function returning lowest evaluation A

5
18CSC305J-Artificial Intelligence

B. Evaluation function returning highest evaluation

C. Evaluation function returning lowest & highest evaluation
D. None of them is applicable

6
18CSC305J-Artificial Intelligence

Which search is equal to minimax search but eliminates the

branches that can’t influence the final decision?
15 C
A. Depth-first search
B. Breadth-first search
C. Alpha-beta pruning
D. None of the above
Which values are independent in minimax search algorithm?

16 A. Pruned leaves x and y A

B. Every states are dependent
C. Root is independent
D. None of the above
For general graph, how one can get rid of repeated states?

17 A. By maintaining a list of visited vertices A

B. By maintaining a list of traversed edges
C. By maintaining a list of non-visited vertices
D. By maintaining a list of non-traversed edges
DFS is efficient and BFS is efficient.

18 A. Space, Time A
B. Time, Space
C. Time, Time
D. Space, Space
Which of the following are the two key characteristics of the
Genetic Algorithm?

A. Crossover techniques and Fitness function

19 A
B. Random mutation and Crossover techniques

7
18CSC305J-Artificial Intelligence

C. Random mutation and Individuals among the population

D. Random mutation and Fitness function
E. None of these

8
18CSC305J-Artificial Intelligence

Hill-Climbing technique stuck for which of the following reasons?

A. Local maxima
20 D
B. Ridges
C. Plateaux
D. All of these
E. None of these
How many successors are generated in backtracking search?

21 A. 1 A
B. 2
C. 3
D. 4
Which value is assigned to alpha and beta in the alpha-beta
pruning?

22 A. alpha = max D
B. alpha = min
C. beta = min
D. Both A and C
Which of the mentioned properties of heuristic search
differentiates it from other searches?

A. It provides solution in a reasonable time frame

23 D
B. It provides the reasonably accurate direction to a goal
C. It considers both actual costs that it took to reach the current
state and approximate cost it would take to reach the goal from
the current state
D. All of the above
What is most important to be concerned with in the evolution of
repetitive
problems?
9
18CSC305J-Artificial Intelligence

A. Do multiple runs until a good solution is found

24 C
B. Execute one run until the solution is good enough
C. Get a reasonably good solution every time
D. Get a very good result just once

10
18CSC305J-Artificial Intelligence

General algorithm applied on game tree for making decision on

win/lose is

25 A. DFS/BFS search algorithm D

B. Heuristic search algorithm
C. Greedy search algorithm
D. Minmax algorithm
Which one of the following is a part of every game theory model?

26 A. Players. D
B. Payoffs
C. Probabilities
D. Strategies
Which of the following describes Nash equilibrium?

A. A firm chooses its dominant strategy, if one exists.

27 B
B. Every competing firm in an industry chooses a strategy that is
optimal given the choices of every other firm.
C. Market price results in neither a surplus nor a shortage.
D. All firms in an industry are earning zero economic profits.
A prisoners' dilemma is a game with all of the following
characteristics except one.

A. Players cooperate in arriving at their strategies.

28 A
B. Both players have a dominant strategy.
C. Both players would be better off if neither chose their
dominant strategy.
D. The payoff from a strategy depends on the choice made by the
other player.
The heuristic path algorithm is a best-first search in which the
evaluation function is
f(n) = (2 − w)g(n) + wh(n). What kind of search does this perform

11
18CSC305J-Artificial Intelligence

for w = 1?
29 B
A. Uniform cost search
B. A* search
C. Greedy best-first search

12
18CSC305J-Artificial Intelligence

D. None of the above

A genetic algorithm (or GA) is a variant of stochastic beam search

in which successor states are generated by combining two parent
states, rather than by modifying a single state.
30 A
A. True
B. False
Adversarial search problems uses

a) Competitive Environment
b) Cooperative Environment
31
c) Neither Competitive nor Cooperative Environment
d) Only Competitive and Cooperative Environment
Answer : a

Zero sum game has to be a game.

a) Single player
b) Two player
32 c) Multiplayer c
d) Three player

General algorithm applied on game tree for making decision of win/lose is

33 a) DFS/BFS Search Algorithms d

b) Heuristic Search Algorithms
c) Greedy Search Algorithms
d) MIN/MAX Algorithms

What is the complexity of minimax algorithm?

a) Same as of DFS
34 a
b) Space – bm and time – bm
c) Time – bm and space – bm
d) Same as BFS

13
18CSC305J-Artificial Intelligence

Which of the following for the game can be defined by the initial state and
the legal moves for each side?
(A). Search Tree
(B). Forest
35 (C). State Space Search D
(D). Game Tree
(E). Goal State

Sample Part-B Questions

1. Write the heuristic estimation function for A* search?

2. State the advantages of the local search algorithm.
3. Define Heuristic function, h (n).
4. When will Hill-Climbing algorithm terminate?
5. How a game formulated as a search problem?
6. List any two memory bounded algorithms.
7. Differentiate online search and offline search.
8. List some of the variants of hill-climbing.
9. Draw the State Space diagram for Hill Climbing search problem. Identify the problems in different
regions in Hill climbing. Give reason.
10. State the difference between heuristic and adversarial search
11. Differentiate Blind Search and Heuristic Search.
12. What are the disadvantages of Hill climbing Algorithm and how can you overcome it ?
13. What do you understand by adversarial search ?
14. What is pruning ?
15. Brief the elements of game playing search.
16. Define Maximin Strategy.
17. List the limitations of Minmax algorithm

Sample Part-C Questions

1. Explain Uniform Cost Search Algorithm with an example.

Brief Generate and Test Strategy.

2. Explain Travelling Salesman Problem with an example

14
18CSC305J-Artificial Intelligence

3. Brief the parameters for evaluating Search Algorithms .

4. Illustrate any local search algorithm.

5. Solve the following mixed strategy game.

Y1 Y2

X1 4 2
X2 0 10

6.A professional athlete , Biff Rhino , and his agent , Jim Fence , are
renegotiating Biff’s contract with the general manager of the Texas Buffaloes ,
Harry Sligo . The various outcomes of this game situation is organized into a
payoff table as shown below.

General Manager Strategy

Athlete/Agent
A B C
Strategy
1 $50,000 $35,000 $30,000
2 60,000 40,000 20,000

The athlete and agent want to maximize the athlete’s contract , and the general
manager hopes to minimize the athlete’s contract . Using maximin and minimax
strategies work out the optimal strategy for athlete as well as the general
manager . Does this game situation have a saddle point ? Substantiate your
answers with appropriate reasoning .
7.The Coloroid Camera Company (referred to as company I) is going to introduce
a new camera into its product line and hopes to capture as large an increase in
its market share as possible. In contrast, the Camco Camera Company
(referred to as company II) hopes to minimize Coloroid’s market share
increase. Coloroid and Camco dominate the camera market, and any gain in
market share for Coloroid will result in a subsequent identical loss in market

15
18CSC305J-Artificial Intelligence

share for Camco. The strategies for each company are based on their
promotional campaigns, packaging, and cosmetic differences between the
products. The payoff table, which includes the strategies and outcomes for
each company (I Coloroid and II Camco), is shown below. The values in the
table are the percentage increases or decreases in market share for company
I.

Company Company II Strategy

I
Strategy A B C
1 9 7 2
2 11 8 4
3 4 1 7

Apply Maximin decision criteria and Minimax criteria and check whether the two
strategies result in an equilibrium point . Identify dominant strategies and eliminate
them .

16