##
CSCE 421/821: Fall 2016, Glossary 7

**Assigned: Monday, Oct 24.**

**Due: Monday, Oct 31.**

**Note: **Glossaries are optional but they allow you improve
your grade. Also, you are responsible for knowing the exact
definition of the terms in a glossary at any point in time, including
during a quiz.
You may need to check the following document:
- Dechter Section 1.3.2
- Dechter Chapter 4

Perfect elimination ordering
**Complexity**
- Efficient algorithm
- Steps of proof of NP-completeness
- Tractable problem

**Ordering Algorithms**
For each of the following algorithms, please explain:
(1) The goal of the algorithm and (2) How it operates (informally and in words):
- Max Cardinality ordering algorithm (Dechter Fig 4.3)
- Min-Fill algorithm (Dechter Fig 4.4)
- Width algorithm of Freuder (Dechter 4.2)

**Relations**
- Composition (of relations)
- Conjunctive decomposition
- Difference (of relations)
- Intersection (of relations)
- Join of relations (natural join).
- Projection (of relation)
- Selection (of relation)
- Union (of relation)

Do not forget to list your references.

Berthe Y. Choueiry