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:
Perfect elimination ordering
- Dechter Section 1.3.2
- Dechter Chapter 4
For each of the following algorithms, please explain:
(1) The goal of the algorithm and (2) How it operates (informally and in words):
- Efficient algorithm
- Steps of proof of NP-completeness
- Tractable problem
- Max Cardinality ordering algorithm (Dechter Fig 4.3)
- Min-Fill algorithm (Dechter Fig 4.4)
- Width algorithm of Freuder (Dechter 4.2)
Do not forget to list your references.
- 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)
Berthe Y. Choueiry