27/07/2020 AI:Constraint Satisfaction - - Unit 4 - Week 2: Projection Networks, Constraint Propagation, Generalized AC

reviewer2@nptel.iitm.ac.in ▼

Courses » AI:Constraint Satisfaction Announcements Course Ask a Question Progress

Unit 4 - Week 2: Projection Networks, Constraint

Propagation, Generalized AC

Course
outline Week 2 - Assignment 1
The due date for submitting this assignment has passed. Due on 2018-02-21, 23:59 IST.
Week 0 As per our records you have not submitted this assignment.

How to access 1) Given a network R the solution relation ρ is 1 point

the portal
the set of all solutions of R.
Week 1: the set of all constraints in R.
Introduction to relation between the input and the output variables.
CSP and
Constraint none of the above.
Networks
No, the answer is incorrect.
Score: 0
Week 2:
Projection Accepted Answers:
Networks, the set of all solutions of R.
Constraint
Propagation, 2) Which of the following are necessary conditions for two constraint networks to be equivalent? 1 point
Generalized AC
both networks must have the same set of variables
Lecture 1:
the sets of variables in both networks must have the same domains
Projection
Networks both networks must have the same set of solutions
both networks must have the same set of constraints
Lecture 2:
Constraint if a constraint with the same scope is present in both networks, the relations in the constraint in
Propagation both networks must be the same
Lecture 3: No, the answer is incorrect.
Algorithms AC1
Score: 0
and AC3
Accepted Answers:
Lecture 4: Can
both networks must have the same set of variables
we do better
than AC3?
both networks must have the same set of solutions

Lecture 5: 3) 1 point
Algorithm AC4
Identify which of them are equivalent:
Lecture 6:
Generalized
Z and X
AC, Path
Consistency Z and Y
X and Y
Quiz : Week 2 -
Assignment 1 All are equivalent

Week 2 No, the answer is incorrect.

Feedback Score: 0

Week 3: i- Accepted Answers:

consistency. X and Y
Directional

https://onlinecourses-archive.nptel.ac.in/noc18_cs19/unit?unit=15&assessment=81 1/5
27/07/2020 AI:Constraint Satisfaction - - Unit 4 - Week 2: Projection Networks, Constraint Propagation, Generalized AC
consistency, 4)
Graph orderings
The number of constraints in the projection network P(ρ) for the above network is ________ .
Week 4:
Backtrack free
search, Adaptive
consistency, No, the answer is incorrect.
Search methods Score: 0
for solving CSPs,
Lookahead Accepted Answers:
methods (Type: Numeric) 3

Week 5: 1 point
Combining
5) 1 point
search and
reasoning,
(1,1,3)
Lookback
methods and (2,1,3)
Gaschnig's (1,2,3)
backjumping
(2,1,2)
Week 6: Graph No, the answer is incorrect.
based
Score: 0
backjumping,
Conflict directed Accepted Answers:
backjumpipng, (2,1,3)
Combining (2,1,2)
lookahead with
lookback,
Learning
6) 1 point
Week 7: Model
based systems,
Model based What are the colours in the domain of region A after arc consistency has been achieved on the
diagnosis, Truth
maintenance corresponding CSP? Mark all colours in the domain of A.
systems
red
Week 8: Planning blue
as CSP, Planning green
as SAT,
none of the above
Wrapping up
No, the answer is incorrect.
Download Score: 0
Accepted Answers:
Lecture slides
blue
green
Solutions
7) What are the colours in the domain of region B after arc consistency has been achieved on 1 point
Interactive the corresponding CSP? Mark all colours in the domain of B.
Session
red
blue
green
none of the above

No, the answer is incorrect.

Score: 0
Accepted Answers:
red

8) What are the colours in the domain of region C after arc consistency has been achieved on 1 point
the corresponding CSP? Mark all colours in the domain of C.

red
blue
green
none of the above

https://onlinecourses-archive.nptel.ac.in/noc18_cs19/unit?unit=15&assessment=81 2/5
27/07/2020 AI:Constraint Satisfaction - - Unit 4 - Week 2: Projection Networks, Constraint Propagation, Generalized AC
No, the answer is incorrect.
Score: 0
Accepted Answers:
blue

9) What are the colours in the domain of region D after arc consistency has been achieved on 1 point
the corresponding CSP? Mark all colours in the domain of D.

red
blue
green
none of the above

No, the answer is incorrect.

Score: 0
Accepted Answers:
green

10)What are the colours in the domain of region E after arc consistency has been achieved on 1 point
the corresponding CSP? Mark all colours in the domain of E.

red
blue
green
none of the above

No, the answer is incorrect.

Score: 0
Accepted Answers:
red

11) 1 point

Each edge (x,y) in the constraint graph is visited exactly once.

In every cycle of the algorithm every edge (x,y) is visited exactly once.
In some cycle of the algorithm some edges may not be visited.
Whenever an edge (x,y) is visited in a cycle so is edge (y,x).
Whenever any edge is visited in a cycle so is every other edge.

No, the answer is incorrect.

Score: 0
Accepted Answers:
In every cycle of the algorithm every edge (x,y) is visited exactly once.
Whenever an edge (x,y) is visited in a cycle so is edge (y,x).
Whenever any edge is visited in a cycle so is every other edge.

12) 1 point

Each edge (x,y) in the constraint graph is visited exactly once.

In every cycle of the algorithm every edge (x,y) is visited exactly once.
In some cycle of the algorithm some edges may not be visited.
Whenever an edge (x,y) is visited in a cycle so is edge (y,x).
Whenever any edge is visited in a cycle so is every other edge.

No, the answer is incorrect.

Score: 0
Accepted Answers:
In some cycle of the algorithm some edges may not be visited.

13) 1 point

In the first cycle of the algorithm every edge (x,y) is visited exactly once.
In every cycle of the algorithm some edges may not be visited.
Whenever an edge (x,y) is visited in a cycle so is edge (y,x).

https://onlinecourses-archive.nptel.ac.in/noc18_cs19/unit?unit=15&assessment=81 3/5
27/07/2020 AI:Constraint Satisfaction - - Unit 4 - Week 2: Projection Networks, Constraint Propagation, Generalized AC

Whenever Dx changes while visiting edge (x,y), the edge (y,x) is enqueued for a visit.
Whenever Dx changes while visiting edge (x,y), every edge (z,x) z≠y is enqueued for a visit.

No, the answer is incorrect.

Score: 0
Accepted Answers:
In the first cycle of the algorithm every edge (x,y) is visited exactly once.
Whenever Dx changes while visiting edge (x,y), every edge (z,x) z≠y is enqueued for a visit.

14)Algorithm AC-3 is more efficient than AC-1 because 1 point

AC-3 only propagates any change happening in a domain via a connected edge.
AC-3 uses an efficient hashing technique which AC-1 does not.
AC-3 propagates change at the level of values in the matching diagram. AC-1 does not.
AC-1 visits edges in a brute force manner in every cycle. AC-3 does not.

No, the answer is incorrect.

Score: 0
Accepted Answers:
AC-3 only propagates any change happening in a domain via a connected edge.
AC-1 visits edges in a brute force manner in every cycle. AC-3 does not.

15)The algorithm AC-4 (mark all correct options) 1 point

Uses a double ended queue which AC-3 does not.

Uses the Revise(Dx, Dy, Rxy) procedure selectively.
Does not use the Revise(Dx, Dy, Rxy) procedure.
Keeps track of the number of edges emanating from each value in every domain.

No, the answer is incorrect.

Score: 0
Accepted Answers:
Does not use the Revise(Dx, Dy, Rxy) procedure.
Keeps track of the number of edges emanating from each value in every domain.

Previous Page End

© 2014 NPTEL - Privacy & Terms - Honor Code - FAQs -

A project of In association with

Funded by

Powered by

https://onlinecourses-archive.nptel.ac.in/noc18_cs19/unit?unit=15&assessment=81 4/5
27/07/2020 AI:Constraint Satisfaction - - Unit 4 - Week 2: Projection Networks, Constraint Propagation, Generalized AC

https://onlinecourses-archive.nptel.ac.in/noc18_cs19/unit?unit=15&assessment=81 5/5