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
    • Complexity
    1. Efficient algorithm
    2. Steps of proof of NP-completeness
    3. 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):
    1. Max Cardinality ordering algorithm (Dechter Fig 4.3)
    2. Min-Fill algorithm (Dechter Fig 4.4)
    3. Width algorithm of Freuder (Dechter 4.2)
    Relations
    1. Composition (of relations)
    2. Conjunctive decomposition
    3. Difference (of relations)
    4. Intersection (of relations)
    5. Join of relations (natural join).
    6. Projection (of relation)
    7. Selection (of relation)
    8. Union (of relation)
    Do not forget to list your references.
    Berthe Y. Choueiry