Complete Table Of Contents

[ToniRV]

@sharanraja

I have updated the table of contents in the notebook with details on what we should have (copied below for convenience).

How do you want to divide the work?

• I would suggest that one of us works on:

  • Constraint Propagation in CSPs (let's say you do that).
  • while the other works on Search in CSPs for now (I do this).

• Then, for part 2.3 Elimination for Constraints in CSPs:

  • you could go for Bucket Elimination,
  • and I will explain Variable Elimination.

• For part 3. Appendix:

  • I can do 3.1 Constraint Optimization Problem where I will do a map-coloring visual demo.
  • You could work on 3.2, think of an example, I think that we can do it with NQueens.
  • Concerning 3.3, I think I can do it myself by re-using explanations of Search in CSPs.

For all parts, think of interactive ways to demonstrate the concepts, not just saying this works like this and that... Nikhil emphasized this part quite a bit.

In terms of work development
Checkout the projects tab to see what is to be done and to log what has been done.
In general:

1. I add issues in the issues tab for something that has to be done.
2. then I add it as a card in the projects tab
3. once I am tackling an issue I put it in progress in the Projects tab (you can see that this issue is actually in the "in progress" column of the current project "CSP todo list" (see on the right panel under Projects)
4. Once I have an issue done, you can close the issue, and it will move automatically to Done in the Projects tab.

Feel free to use this workflow, it works great for collaboration.

CONTENTS

1. Introduction to Constraint Propagation Problems (L13 & L14):

   1. Definition
   2. Examples

2. Solving CSPs (L14 & L 15):

   1. Constraint Propagation in CSPs:

      1. Arc-Consistency:

         1. Directed arc consistency
         2. Full arc consistency

      2. Propagation:

         1. AC-1:
            • Definition
            • Example: solving Sudoku with AC-1
            • Complexity Analysis
            • Soundness and Completeness
         2. AC-3:
            • Definition
            • Example: solving Sudoku with AC-3
            • Complexity Analysis
            • Soundness and Completeness

      3. Numerical constraints:

         1. Propagation for Integer Domains
         2. Pruning Integer Domains

      4. Global constraints:

         1. AllDiff
         2. Example: global vs local constraints NQueens

   2. Search in CSPs:

      1. Generic Search:
         • Formulating CSPs as a state space search problem
         • Complexity
         • Example: NQueens with generic search (5 Queens)
      2. Backtracking Search (BT):
         • Definition
         • Complexity
         • Example: solving NQueens (15 Queens)
      3. Backtracking Search with Forward Checking (BT-FC):
         • Definition
         • Complexity
         • Example: solving NQueens (30 Queens)
      4. Backtracking while Maintaining Arc Consistency (BT-MAC):
         • Definition
         • Complexity
         • Example: solving NQueens (X Queens)
      5. BT-DC with Dynamic Variable Ordering:
         • Definition
         • Complexity
         • Example: solving NQueens (1000 Queens)

   3. Elimination for Constraints in CSPs:

      1. Variable Elimination for Constraints:
         • Definition: join and project
         • Example
      2. Bucket elimination (Adaptive Consistency):
         • Definition
         • Example

3. Appendix:

   1. Constraint Optimization Problem:
      1. Branch-and-Bound
   2. Conflict-directed Back Jumping (CBJ)
      • Definition
      • Example
   3. Incremental Repair / Iterative Repair / Min-Conflict Heuristic
      • Definition
      • Example

[ToniRV]

As commented today, we should decide what to do with the things in the appendix.
For now, let's remove Conflict-directed Back Jumping as Nikhil said.
The rest I don't know, Min-Conflict Heuristic would be quite interesting and easy to implement.
Constraint optimization problem would be easy as well by using a map coloring problem.