NPTEL An Introduction to Artificial Intelligence Week 4 Assignment Answers
Q1. Which of the following algorithms is asymptotically complete?
a. Random sampling of states
b. Local beam search
c. Random walk
d. Hill climbing with random restarts
Answer: a. Random sampling of states
c. Random walk
Q2. Genetic algorithms are said to jump from one hill to another. Which of the following is responsible for such behavior?
a. Mutation
b. Cross over
c. Fitness function
d. Natural Selection
Answer: b. Cross over
Q3. Mona was doing a Hill Climbing procedure to solve a problem. She observed that her procedure often gets stuck in plateaus.. Which of the following additions to the procedure would you recommend to her?
a. Allow indefinite sideway moves
b. Allow sideway moves but upto a certain limit (say, 100)
c. Keep a tabu list of recently visited nodes
d. Perform a bfs to find the next node with a better objective function when the state is stuck in a plateau
Answer: b. Allow sideway moves but upto a certain limit (say, 100)
Q4. Which of the following is/are true about local search algorithms?
a. They are guaranteed to always terminate with a correct solution
b. They are highly memory efficient compared to tree/graph search methods
c. They can only solve a certain variety of optimization functions
d. They don’t make any assumptions on the structure of optimization function
Answer: b. They are highly memory efficient compared to tree/graph search methods
d. They don’t make any assumptions on the structure of optimization function
Q5. Fischl wishes to solve the 8-queens problem using Hill climbing with random restarts and with no sideway moves allowed. It is known that the probability of a successful run of the hill climb algorithm on this problem is 0.14. On average, how many restarts should she expect? (Round off your answer to the closest integer)
Answer: 7
Q6. The famous FF planner uses which of the following algorithms?
a. Heuristic Search
b. Enforced hill climbing
c. Iterative Deepening Search
d. Greedy hill Climbing with random restart
Answer: b. Enforced hill climbing
Q7. Gradient descent is guaranteed to converge for strictly convex functions assuming the step size λ is sufficiently small. Assume that we have the function y = x2. For what values of λ, will gradient descent converge?
a. 0.1
b. 0.5
c. 1.0
d. 2.5
Answer: We are not sure about the answer so, do it yourself.
For Questions 8 and 9
In Simulated Annealing, generally, the temperature is reduced from a positive value to a low value in successive iterations. Assume the following 3 step temperature schedule:
[20, 10, 0]
Assume that we have three states s1, s2, and s3 such that V(s1) = 5, V(s2) = 0, and V(s3) = 10. Successors of a state are chosen uniformly randomly. The successor states are defined as: next(s1) = {s2}, next(s2) = {s1, s3}, next(s3) = {s2}. Assume that s3 is the start state.
Answer the next 2 questions based on this setting.
Q8. After the first iteration of simulated annealing, what is the probability that the current state would be s2. Round the answer to three digits after the decimal point.
Answer: We are not sure about the answer so, do it yourself.
Q9. What is the probability that when the algorithm ends, we are at the state with the highest value?Round the answer to three digits after the decimal point.
Answer: We are not sure about the answer so, do it yourself.
Q10. What are the difference(s) between Simulated Annealing (SA) and Genetic Algorithms (GA)
a. GA maintains multiple candidate solutions while SA does not.
b. SA is used for minimization problems while GA is used for maximization problems
c. SA has no parameters to set whereas GA requires you to set multiple parameters such as crossover rate.
d. GA will always converge to an optimal solution faster than SA on any given problem.
Answer: a. GA maintains multiple candidate solutions while SA does not.
Disclaimer: These answers are provided only for the purpose to help students to take references. This website does not claim any surety of 100% correct answers. So, this website urges you to complete your assignment yourself.
Also Available:
NPTEL An Introduction to Artificial Intelligence Week 5 Assignment Answers
NPTEL An Introduction to Artificial Intelligence Week 1 Assignment Answers
