Consider a Bayesian network with a large number of variables. Which of the following techniques is most likely to improve the efficiency of exact inference?
Using a junction tree algorithm
Approximating the network with a smaller one
Applying belief propagation
All of the above
Correct Answer
Option 4
Solution
All of these techniques can improve the efficiency of exact inference in a large Bayesian network. Junction trees can reduce the size of intermediate factors, approximation can simplify the network, and belief propagation can exploit conditional independence relationships.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
In variable elimination, the order in which variables are eliminated can significantly affect the computational complexity. Which of the following heuristics is commonly used to choose the elimination order?
Minimum Fill
Maximum Likelihood
Minimum Degree
Maximum Entropy
Correct Answer
Option 3
Solution
Minimum Degree aims to minimize the size of the factors created during elimination, reducing computational cost.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Which of the following is a disadvantage of variable elimination for exact inference in Bayesian networks?
It can be computationally expensive for large networks.
It cannot handle cyclic graphs.
It requires storing the entire joint probability distribution.
It cannot handle continuous variables.
Correct Answer
Option 1
Solution
Variable elimination can be inefficient for large networks due to the exponential growth of intermediate factors.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The Viterbi algorithm is used to:
Find the most likely sequence of hidden states given an observed sequence.
Estimate the transition probabilities in an HMM.
Find the steady-state distribution of a Markov chain.
Calculate the likelihood of an observed sequence given an HMM.
Correct Answer
Option 1
Solution
The Viterbi algorithm is a dynamic programming algorithm that finds the most probable sequence of hidden states that could have generated a given observed sequence.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Hidden Markov Models (HMMs) are used for
Modeling sequential data with hidden states
Modeling static data
Modeling continuous data
Modeling deterministic systems
Correct Answer
Option 1
Solution
HMMs are powerful tools for modeling sequential data where the underlying state is not directly observable.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
A Markov chain is said to be ergodic if:
It has a single steady-state distribution
It has multiple steady-state distributions
It does not have a steady-state distribution
It is always periodic
Correct Answer
Option 1
Solution
An ergodic Markov chain eventually reaches a stable state, regardless of its initial state. This stable state is represented by a unique steady-state distribution.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following:
“The result of the toss is head if and only if I am telling the truth.”
Which of the following options is correct?
The result is head
The result is tail
If the person is of Type 2, then the result is tail
If the person is of Type 1, then the result is tail
Correct Answer
Option 1
Solution
If the person is of Type 1 who always tell truth, then result must be head.
If the person is of Type 2 who always tell lie, then result must be head.
Negation of a sentence of the form "X is true if and only if Y is true" is
"Either X is true and Y is false, or X is false and Y is true."
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Which one of these first-order logic formula is valid?
∀x(P(x) => Q(x)) => (∀xP(x) => ∀xQ(x))
∃x(P(x) ∨ Q(x)) => (∃xP(x) => ∃xQ(x))
∃x(P(x) ∧ Q(x)) <=> (∃xP(x) ∧ ∃xQ(x))
∀x∃y P(x, y) => ∃y∀x P(x, y)
Correct Answer
Option 1
Solution
LHS: For every x (if P holds then Q holds)
RHS: If P(x) holds for all x, then Q(x) holds for all x.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Which of the following is false? Read ∧ as AND, ∨ as OR, ∼ as NOT, → as one way implication and ↔ as two way implication.
((x→y) ∧ x)→ y
((∼x→y) ∧ (∼x→∼y))→ x
(x→ (x ∨ y))
((x ∨ y) ↔ (∼x→∼y))
Correct Answer
Option 4
Solution
((x ∨ y) ↔ (∼x→∼y))
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Let P and Q be two propositions, ¬ (P ↔ Q) is equivalent to: (I) P ↔ ¬ Q (II) ¬ P ↔ Q (III) ¬ P ↔ ¬ Q (IV) Q → P
Only (I) and (II)
Only (II) and (III)
Only (III) and (IV)
None of the above
Correct Answer
Option 1
Solution
We know that ¬(P ↔ Q) = (¬P ↔ Q) = (P ↔ ¬Q) = ¬(¬P ↔ ¬Q) Only statement (I) and (II) are correct. So, option (A) is correct.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The proposition (P⇒Q)⋀(Q⇒P) is a
tautology
contradiction
contingency
Absurdity
Correct Answer
Option 3
Solution
(P⇒Q)⋀(Q⇒P) = (¬P+Q)(¬Q+P) = (¬P¬Q + ¬PP + ¬QQ + PQ) = (¬P¬Q + PQ) Therefore it is a contingency.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Let P, Q, R and S be Propositions. Assume that the equivalences P ⇔ (Q ∨ ¬ Q) and Q ⇔ R hold. Then the truth value of the formula (P ∧ Q) ⇒ ((P ∧ R) ∨ S) is always:
True
False
Same as truth table of Q
Same as truth table of S
Correct Answer
Option 1
Solution
True
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Which one of the following Boolean expressions is NOT a tautology?
((a → b) ∧ (b → c)) → (a → c)
(a ↔ c) →( ¬b → (a ∧ c))
(a ∧ b ∧ c) → (c ∨ a)
a → (b → a)
Correct Answer
Option 2
Solution
a <-> c is true if both ‘a’ and ‘c’ have same values.
Let ‘a’, ‘b’ and c’ be false.
Expression \'a and b\' is false and expression \'not b\' is true.
RHS of the given equation should be true. But it evaluates to be false. Therefore, contradiction is there.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The Boolean function [~(~p ∧ q) ∧ ~( ~p ∧ ~q)] ∨ (p ∧ r)] is equal to the Boolean function:
Consider the compound propositions given below as: (a)p ∨ ~(p ∧ q) (b)(p ∧ ~q) ∨ ~(p ∧ q) (c)p ∧ (q ∨ r) Which of the above propositions are tautologies?
(a) and (c)
(b) and (c)
(a) and (b)
only (a)
Correct Answer
Option 4
Solution
p ∨ ~(p ∧ q) = p + (pq)` = p + p` + q` = 1 + q` = 1.This is a tautology.
(p ∧ ~q) ∨ ~(p ∧ q) = pq` + (pq)` = pq` + p` + q` = p` + q`. This is not a tautology.
p ∧ (q ∨ r) = pq + pr. This is not a tautology.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
In propositional logic P ↔ Q is equivalent to (Where ~ denotes NOT):
~( P ∨ Q ) ∧ ~ ( Q ∨ P )
( ~P ∨ Q ) ∧ (~ Q ∨ P )
( P ∨ Q ) ∧ ( Q ∨ P )
~( P ∨ Q ) → ~ ( Q ∨ P )
Correct Answer
Option 2
Solution
P ↔ Q = (P → Q) ∧ (Q → P) P ↔ Q = (~P ∨ Q) ∧ (~Q v P)
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: taller (x, y) is true if x is taller than y
(∃x)(boy(x) → (∀y)(girl(y) ∧ taller(x, y)))
(∃x)(boy(x) ∧ (∀y)(girl(y) ∧ taller(x, y)))
(∃x)(boy(x) → (∀y)(girl(y) → taller(x, y)))
(∃x)(boy(x) ∧ (∀y)(girl(y) → taller(x, y)))
Correct Answer
Option 4
Solution
We use ∧ when we want to say that the both predicates in this statement are always true, no matter what the value of x is.
We use → when we want to say that although there is no need for left predicate to be true always, but whenever it becomes true, right predicate must also be true.
D means there exist some boys x which taller than all girls y.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which one of the following predicate formulae is NOT logically valid ? Note that W is a predicate formula without any free occurrence of x.
∀x(p(x) ∨ W) ≡ ∀x(px) ∨ W
∃x(p(x) ∧ W) ≡ ∃xp(x) ∧ W
∀x(p(x) → W) ≡ ∀xp(x) → W
∃x(p(x) → W) ≡ ∀xp(x) → W
Correct Answer
Option 3
Solution
∀x (p(x) → W) ≡ ∀x p(x) → W is wrong. Since ∀x [p(x) → W]
≡ ∀x [¬p(x) ∨ W]
≡ ∀x (¬p(x) ∨ W
≡ ¬(∃x p(x)) ∨ W
≡ ∃x p(x) → W
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Match List-I with List-II
List-I List-II
(a) p → q (i) ¬(q → ¬p)
(b) p v q (ii) p ∧ ¬q
(c) p ∧ q (iii) ¬p → q
(d) ¬(p → q) (iv) ¬p v q
Choose the correct option from those given below:
a-ii,b-iii,c-i,d-iv
a-ii,b-i,c-iii,d-iv
a-iv,b-i,c-iii,d-ii
a-iv,b-iii,c-i,d-ii
Correct Answer
Option 4
Solution
a-iv,b-iii,c-i,d-ii
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following graph in which we are searching from start state A to the goal state J. What is the number of nodes generated by Iterative Deepening Search? Assume that nodes are explored in right-to-left order and all edge costs are 1. Note: Exploration of the goal state J should be added to the count.
19
Correct Answer
Option 1
Solution
Depth 0: (Limit 0) - A (1 node)
Depth 1: (Limit 1) - A, C, B (3 nodes)
Depth 2: (Limit 2) - A, C, G, F, B, E, D (7 nodes)
Depth 3: (Limit 3) - A, C, G, F, B, E, I, H (8 nodes - we stop once we reach J since it's the goal and the end of this level)
Now, let's add them up:
Depth 0: 1 node
Depth 1: 3 nodes
Depth 2: 7 nodes
Depth 3: 8 nodes (since we stop after reaching J)
1 + 3 + 7 + 8 = 19 nodes.
The total number of nodes generated during the search is 19, including the final generation of the goal state J.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
2
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
No student is either clever or ambitious
No student is both clever and ambitious
No ambitious person is a clever student
None of the above
Correct Answer
Option 2
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which of the following scenarios is most suitable for using an uninformed search algorithm over an informed search algorithm?
A robot vacuum cleaner cleaning a mapped room, where the layout and obstacles are known
A person in a known city trying to find the shortest path to a specific destination, where GPS and maps are available
A hiker lost in an unknown forest with no map, GPS, or clear direction to find the exit.
A puzzle game where the goal state and rules are clearly defined
Correct Answer
Option 3
Solution
The hiker has no clear information about the environment or the location of the goal (the exit of the forest). Therefore, it would be difficult to design an effective heuristic function for an informed search algorithm. An uninformed search algorithm, which doesn't rely on a heuristic, would be more appropriate in this situation.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following statements
S1: A heuristic is admissible if it never overestimates the cost to reach the goal.
S2: A heuristic is monotonic if it follows the triangle inequality property.
Which one of the following is true referencing the above statements?
Statement S1 is true but statement S2 is false
Statement S1 is false but statement S2 is true
Neither of the statements S1 and S2 are true
Both the statements S1 and S2 are true
Correct Answer
Option 1
Solution
Statement S1 is true but statement S2 is false
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which of the following is an example of an uninformed search strategy?
A* search
Breadth-first search
Greedy best-first search
Hill climbing
Correct Answer
Option 2
Solution
Breadth-first search is an uninformed search strategy that explores all nodes at the present depth level before moving on to nodes at the next depth level
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
In A* search algorithm, what does the evaluation function f(n) = g(n) + h(n) represent?
Cost from start node to goal node
Estimated cost from start node to goal node through n
Cost from start node to n
Heuristic cost from n to goal node
Correct Answer
Option 2
Solution
Estimated cost from start node to goal node through n
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which of the following is true about the Uniform Cost Search algorithm?
It is a type of depth-first search
It expands the node with the lowest path cost
It uses a heuristic to guide the search
It is not complete
Correct Answer
Option 2
Solution
Uniform Cost Search is a variant of Dijkstra’s algorithm that expands the node with the lowest path cost, ensuring that the shortest path is found
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
What is the main characteristic of informed search strategies?
They use problem-specific knowledge
They do not use any additional information
They are also known as brute-force search
They are used in adversarial environments
Correct Answer
Option 1
Solution
Informed search strategies, also known as heuristic searches, use problem-specific knowledge to find solutions more efficiently than uninformed search strategies.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which search strategy is also known as blind search?
Informed search
Uninformed search
Adversarial search
Heuristic search
Correct Answer
Option 2
Solution
Uninformed search strategies do not have additional information about states beyond that provided in the problem definition. They are also called blind searches because they do not use any domain-specific knowledge.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Let ℎ1and ℎ2 be two admissible heuristics used in A∗ search.Which ONE of the following expressions is always an admissible heuristic?
ℎ1 + ℎ2
ℎ1 × ℎ2
ℎ1/ℎ2, (ℎ2 ≠ 0)
|ℎ1 − ℎ2|
Correct Answer
Option 4
Solution
For h1 and h2 to be admissible heuristics, they must never overestimate the true cost to reach the goal. The absolute difference |h1 - h2| will not overestimate the true cost, thus it is always admissible
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which type of Search is typically used in a game where you have to predict your opponent's move?
Uninforced Search
Inforced Search
Adversarial Search
Heuristic Search
Correct Answer
Option 3
Solution
Adversarial Search is used when there is an opponent who can influence the outcome of the game or problem. In this case, predicting your opponent's move requires using adversarial techniques to anticipate their actions.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
A company is trying to optimize its production process by finding the most efficient way to manufacture a product. Which type of search is being used in this problem?
Uninformed search
Informed search
Adversarial search
Heuristic search
Correct Answer
Option 2
Solution
The company has some knowledge about the production process and the factors that affect efficiency, making it an informed search problem. The company can use this information to guide the optimization process towards the most efficient solution.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider an A* search algorithm that uses a heuristic function that is not admissible. What is the guaranteed result of this algorithm?
It will always find the optimal solution
It may find a suboptimal solution
It may not find a solution
It will always get stuck in an infinite loop
Correct Answer
Option 3
Solution
If an A* search algorithm uses a heuristic function that is not admissible, it may not find a solution because it may choose paths that are longer than necessary or even get stuck in an infinite loop.
