CS156 Fall 2022Practice Final

If you did well on the midterm, the same approach to studying should work for the final. If not, if adjust the amount of studying you do for the final and experiment with how the way you are studying helps you remember the material and how it affects your ability to use the material flexibly.

Here are some facts about the actual final:

1. It is comprehensive covering all the material of the semester.
2. It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test.
3. You should bring photo ID.
4. There will be more than one version of the test. Each version will be of comparable difficulty.
5. It is 10 problems, 6 problems will be on material since the midterm, four problems will come from the topics covered prior to the midterm.
6. Two problems will be exactly (less typos) off of the practice final, and one will be off of practice midterm.

The practice final is below:

1. Give an example of each of the following: (a) a valid formula, (b) a satisfiable formula that is not valid, (c) an unsatisfiable formula.
2. Give a resolution refutation for the set of clauses `{{A}, {bar{C}}, {bar{A}, B, C},{bar{B}, C} }`.
3. Mod2(x_1, ..., x_n) is the propositional formula which returns true if the number of variables `x_i` which are true in a truth assignment is exactly 0 mod 2. Write down a CNF formula for Mod2 in the case where `n=5`.
4. Explain step-by-step through the code how the DPLL algorithm would work on the set of clauses `{{A}, {bar{A}, B}, {bar{B}, C} }`.
5. Suppose `x:= [g(v,h(a)), f(g(z))]` and `y:= [g(f(w),b), f(w)]`. Explain how the unification algorithm from class would work on these inputs.
6. Consider the problem where you have two pairs of different color socks and two shoes all of which are on the ground. You also have two feet. Your goal is to put on your shoes over matching socks. Your feet can wear socks, but not shoes directly. Your available actions are to put on matching socks (they can't be different colors) and put on shoes. Formulate this problem reasonably in PDDL. Then give an example plan solving it.
7. Express the sentence "Bipeds can walk a mile in 10 minutes" using our category and object approach to knowledge engineering together with the event calculus.
8. Explain how we might be able to calculate `\vec(P)(Cavity |t\o\othache)`, given only knowledge of `\vec(P)(Cavity, T\o\othache)`.
9. Draw a square in the plane of edge length 10. Centered around each vertex replace draw a square of edge length 2. Using all of the vertices you drew, explain how the hierarchal clustering algorithm would cluster these points down to 10 clusters.
10. Consider the following training set of 4-tuples.

    (T,T,T, F)
    (T,T,F, F)
    (T,F,T, T)
    (T,F,F, F)
    (F,T,T, T)
    

    Here `T` is short for true, `F` is short for false. The first three columns correspond to the variables `x_1`, `x_2`, `x_3`, the last column is the output of some function `f`. Calculate `Gai\n(x_i)` for `i=1,2,3`. Which variable should we use as the top of a decision tree for `f`?