NPTEL : NOC:AI:Constraint Satisfaction (Computer Science and Engineering)

Co-ordinators : Prof. Deepak Khemani


Lecture 1 - Constraint Satisfaction Problems

Lecture 2 - CSP Examples: Map colouring, N-Queens, Classroom scheduling

Lecture 3 - CSP Examples: Huffman-Clowes Labelling, Waltz Algorithm, Crosswords

Lecture 4 - Model Based Diagnosis - An application of CSP

Lecture 5 - Constraint Networks - An Introduction

Lecture 6 - Binary Constraint Networks (BCN), Equivalent Networks

Lecture 7 - Projection Networks

Lecture 8 - Constraint Propagation

Lecture 9 - Algorithms AC1 and AC3

Lecture 10 - Can we do better than AC3?

Lecture 11 - Algorithm AC4

Lecture 12 - Generalized AC, Path-Consistency

Lecture 13 - i-Consistency, Algorithm PC1

Lecture 14 - Algorithm PC2, Strong i-Consistency

Lecture 15 - Directional Consistency and Graph Ordering

Lecture 16 - Min-Width and Min-Induced-Width Ordering

Lecture 17 - Directional Arc-Consistency and Tree CSPs

Lecture 18 - Directional Path-Consistency and Directional i-Consistency

Lecture 19 - Backtrack-Free search and Adaptive Consistency

Lecture 20 - Adaptive Consistency: Bucket Elimination

Lecture 21 - Search Methods for Solving CSPs

Lecture 22 - Algorithm Backtracking

Lecture 23 - Look-Ahead Methods in Search

Lecture 24 - Look-Ahead Search: Examples

Lecture 25 - Combining Search with Reasoning: Algorithm DPLL

Lecture 26 - Algorithm Backmarking

Lecture 27 - Dynamic Value Ordering, Dynamic Variable Ordering

Lecture 28 - Look-Back Methods - Definitions

Lecture 29 - Gaschnig’s Backjumping: The Culprit Variable

Lecture 30 - Gaschnig’s Backjumping, Graph-Based Backjumping

Lecture 31 - Graph-Based Backjumping: Internal and Relevant Dead-Ends

Lecture 32 - Conflict-Directed Backjumping: Definitions

Lecture 33 - Algorithm Conflict-Directed Backjumping

Lecture 34 - Combining Look-Ahead and Look-Back: FC-CBJ

Lecture 35 - Learning During Search

Lecture 36 - Model Based Systems

Lecture 37 - Model Based Diagnosis

Lecture 38 - Truth Maintenance Systems

Lecture 39 - Planning as Constraint Satisfaction

Lecture 40 - Planning as Constraint Satisfaction (Continued...)

Lecture 41 - Planning as Satisfiability

Lecture 42 - Wrapping Up and Further Study