CP3210 Content and Exam Style Questions

Content

• What is it?
  • Class definitions
  • Class performing intelligent actions
  • Some Handwaving Ideas [Russel & Norvig, pp.3-5]
  • Let us discuss - what is the class opinion?
• Turing Test [Luger & Stubblefield, pp.4-13]
• The Components of an Intelligent Agent
• Case Study: (1) Autonomous Delivery Robot, (2) The Diagnostic Assistant [Pool et al, pp.7-19]

Exam style questions

1. Draw a labelled diagram showing the four components of an intelligent agent. Give examples of the activities that take place in each component.
2. Describe the Turing test for determining if an AI system has succeeded.

Content

• The language [Sut98 p.1]
• Interpretation, and associated definitions [Sut98 p.2]
• Logical consequence using truth tables [Sut98 pp.3-4]
• Logical consequence using unsatisfiability
• Propositional resolution and its soundness
• Using resolution to show unsatisfiability

Exam style questions

1. Define the following terms used in classical logic:
   • Interpretation
   • Model
   • Satisfiable
   • Unsatisfiable
   • Logical consequence
2. Explain what meant by an inference rule being:
   • Sound
   • Complete
   • Refutation complete
3. Express the following axioms and conjecture in propositional logic
   
   1. All the dated letters in this room are written on blue paper.
   2. None of them are in black ink, except those that are written in the third person.
   3. I have not filed any of them that I can read.
   4. None of them that are written on one sheet are undated.
   5. All of them that are not crossed are in black ink.
   6. All of them written by Brown begin with "Dear Sir"
   7. All of them written on blue paper are filed.
   8. None of them written on more than one sheet are crossed.
   9. None of them that begin with "Dear Sir" are written in third person.
   10. Prove that letters by Brown cannot be read.
4. Use the definition of logical consequence and a truth table to show that
   

        (q => p) | ~(q => (p | r))
      

   is a logical consequence of the set:

      { p | q | r, 
        r => (p | q), 
        (q ^ r) => p, 
        ~p | q | r }
      

   .
5. Explain how "unsatisfiability" can be used to establish logical consequence in classical logic.
6. Use unsatisfiability and a truth table to show that
   

        ~rf
      

   is a logical consequence of the set:

      { ~rf | td,
        ~gc | td,
        ~td | ph,
        ~ph }
      

   .
7. Use resolution to show that
   

        p
      

   is a logical consequence of the set:

      { q v p,
        ~q v r,
        ~r v s,
        ~s v ~r v t,
        ~t v p }
      

   .
8. What are the two major limitations of propositional logic?

Content

• The language [Sut98 pp.5-6]
• Interpretation [Sut98 pp.6-7]
• Clause Normal Form [Sut98 pp.8-10]

Exam style questions

1. Describe the three components of a 1st order logic language.
2. Describe the three components of an interpretation of a 1st order logic language. Give an example for the language:

      V = { V : V starts with uppercase }
      F = { coke/0, pepsi/0, competitor/1 }
      P = { fizzy/1, sells_more/2 }
      
    Given the 1st order logic language:
      
      V = { V : V starts with uppercase }
      F = { holden/0, ford/0, honda/0 main_competitor/1 }
      P = { fast/1, faster/2 }
      
      and the interpretation:
      
      D = { commodore, laser, prelude }
      F = { holden -> commodore,
   	 ford -> laser,
   	 honda -> prelude,
   	 main_competitor(commodore) -> prelude,
   	 main_competitor(laser) -> prelude,
   	 main_competitor(prelude) -> commodore }
      R = { fast(commodore) -> TRUE,
   	 fast(laser) -> FALSE,
   	 fast(prelude) -> TRUE,
   	 faster(commodore,commodore) -> FALSE,
   	 faster(commodore,laser) -> TRUE,
   	 faster(commodore,prelude) -> TRUE,
   	 faster(laser,commodore) -> FALSE,
   	 faster(laser,laser) -> FALSE,
   	 faster(laser,prelude) -> FALSE,
   	 faster(prelude,commodore) -> FALSE,
   	 faster(prelude,laser) -> TRUE,
   	 faster(prelude,prelude) -> FALSE }
      
      Show the steps of the interpretation of:
      
      
   
      
    faster(main_competitor(ford),holden)
      
    fast(main_competitor(main_competitor(honda))
      
    forall X ( faster(main_competitor(X),ford) ^ fast(X) )
      
    exists X ( fast(main_competitor(main_competitor(X))) |
   		   forall Y ( faster(X,Y) ) )
      
      
    Explain why truth tables cannot be used to establish logical consequence 
      in 1st order logic.
    Express the following scenario and conclusion in 1st order logic
      
   
      No vegetarian likes either beef or pork.
      There are some vegetarians who like eggs.
      If someone doesn't like pork, then they don't like bacon.
      Therefore there is someone who likes eggs but not bacon.
      
   

Content

• Unification [Sut98 pp.11-12]
• Resolution operation [Sut98 pp.13-15]
• Resolution procedure [Sut98 pp.16-17]
• The search problem [Sut98 p.18]

Unification Algorithm

Input: Two atoms A=p(u1, ..., un) and B=p(v1, ..., vn).

Output: Substitution {x1=w1, ..., xk=wk}.

Procedure: Starting with a system of equations {u1=v1, ..., un=vn}, apply the following steps as long as they are applicable.

• Splitting: Replace equation of the form f(t_1, ..., t_m) = f(s_1, ..., s_m) by the equations, t_1 = s_1, ..., t_m = s_m.
• Failure: If there is an equation of the form f(t_1, ..., t_m) = g(s_1, ..., s_l), where f and g are different function symbols, halt with failure. We call equations of this form, Dis-equations.
• Delete: Delete the equations of the form t = t.
• Inversion: Replace the equation t = x by the equation x = t, if x is a variable and t is not a variable.
• Substitute: If there is an equation x = t such that x is a variable and it does not occur in t, then replace x by t in every other equation.
• Occur-check: If there is an equation x = t such that x is a variable and occurs in t, then halt with failure: OCCUR-CHECK.

Exam style questions

1. Use resolution to derive the empty clause from the following set of clauses (The Animals Puzzle).

      % The only animals in this house are cats.
      ~in_house(Cat) | cat(Cat)
   
      % Every animal is suitable for a pet, that loves to gaze at the moon.
      ~gazer(Gazer) | suitable_pet(Gazer)
   
      % When I detest an animal, I avoid it.
      ~detested(Detested) | avoided(Detested)
   
      % No animals are carnivorous, unless they  prowl at night.
      ~carnivore(Carnivore) | prowler(Carnivore)
   
      % No cat fails to kill mice.
      ~cat(Cat) | mouse_killer(Cat)
   
      % No animals ever take to me, except what are in this house.
      ~takes_to_me(Taken_animal) | in_house(Taken_animal)
   
      % Kangaroos are not suitable for pets.
      ~kangaroo(Kangaroo) | ~suitable_pet(Kangaroo)
   
      % None but carnivora kill mice.
      ~mouse_killer(Killer) | carnivore(Killer)
   
      % I detest animals that do not take to me.
      takes_to_me(Animal) | detested(Animal)
   
      % Animals that prowl at night always love to gaze at the moon.
      ~prowler(Prowler) | gazer(Prowler)
   
      % The problem is to prove that "I always avoid a kangaroo".
      kangaroo(the_kangaroo)
   
      ~avoided(the_kangaroo)
      

2. Use resolution to derive the empty clause from the following set of clauses (The Barber Puzzle).

   
      % There is a barbers' club that obeys the following three conditions: 
      % If any member has shaved any other member -- whether himself or 
      % another -- then all members have shaved him, though not necessarily 
      % at the same time.
      ~member(X) | ~member(Y) | ~shaved(X,Y) | shaved(members,X)
      ~shaved(members,X) | ~member(Y) | shaved(Y,X) 
   
      % Four of the members are named Guido, Lorenzo, Petrucio, and Cesare.
      member(guido)
      member(lorenzo)
      member(petruchio)
      member(cesare)
   
      % Guido has shaved Cesare
      shaved(guido,cesare)
   
      % Prove Petrucio has shaved Lorenzo
      ~shaved(petruchio,lorenzo)
      

3. Convert the following to CNF. Notation: & for AND, | for OR, ! for universal quantifier, ? for existential quantifier.

          ? [Y] :
          ! [X] :
   	 ( element(X,Y)
          <=> element(X,X) )
       => ~ ( ! [X1] :
   	   ? [Y1] :
   	   ! [Z] :
   	     ( element(Z,Y1)
   	   <=> ~ element(Z,X1) ) )
      

4. Convert the following to CNF (Axiom from Pelletier 41)

          ! [Z] :
          ? [Y] :
          ! [X] :
   	 ( element(X,Y)
          <=> ( element(X,Z)
   	   & ~ element(X,X) ) )
      

5. Convert the following to CNF (Axiom from Pelletier 43)

          ! [X,Y] :
   	 ( set_equal(X,Y)
          <=> ! [Z] :
   	     ( element(Z,X)
   	   <=> element(Z,Y) ) )
      

6. Explain, with examples, the difference between Horn and non-Horn clauses.
7. Explain, with examples, what is meant by "Kowalski form" for clauses. Why is Kowalski form important?
8. Use resolution to derive the empty clause from the set

      { p(X,Y),
        ~p(f(X,Y),g(X,Y)),
        ~p(X,h(Y)) v p(X,Y),
        ~p(X,h(Y)) v ~p(X,X),
        ~p(X,Y) v p(X,X) v p(X,h(Y)) }
      

9. Prove the following formula (Pelletier 20) (i.e., negate before converting to CNF, and then find a derivation of the empty clauses from the CNF).

          ! [X,Y] :
          ? [Z] :
          ! [W] :
   	 ( ( big_p(X)
   	   & big_q(Y) )
   	=> ( big_r(Z)
   	   & big_s(W) ) )
       => ? [X1,Y1] :
   	 ( ( big_p(X1)
   	   & big_q(Y1) )
   	=> ? [Z1] : big_r(Z1) )
      

10. Prove the following formula (Pelletier 23)

           ! [X] :
    	 ( p
    	 | big_f(X) )
       <=> ( p
           | ! [X1] : big_f(X1) )
       

11. Prove the last of these formulae is a logical consequence of the first three (Pelletier 37)

           ! [Z] :
           ? [W] :
           ! [X] :
           ? [Y] :
    	 ( big_p(X,Z)
    	=> ( ( big_p(Y,W)
    	     & big_p(Y,Z) )
    	   & ( big_p(Y,W)
    	    => ? [U] : big_q(U,W) ) ) )
       
           ! [X,Z] :
    	 ( ~ big_p(X,Z)
    	=> ? [Y] : big_q(Y,Z) )
    
    	  ? [X,Y] : big_q(X,Y)
           => ! [Z] : big_r(Z,Z)
       
           ! [X] :
           ? [Y] : big_r(X,Y)
       

12. Express the following scenario and conclusion in 1st order logic, in a form ready to be converted to clause normal form.

    There are some students who fail. If a student fails, then either there is a lecturer who has taught the student badly, or the student is stupid. No lecturer teaches any student badly. Therefore there is some student who is stupid.

    Now give a refutation proof of the conjecture.
13. Use linear-input resolution to derive the empty clause from the set

       S = { ~r(Y) v ~p(Y),
    	 p(b),
    	 r(a),
    	 p(S) v ~p(b) v ~r(S),
    	 r(c) }
       

14. Express the following scenario and conclusion in 1st order logic

    If you are a normal person, then you like at least one form of music and you dislike at least one form of music. There is a person who likes all music. Therefore there is a person who is not a normal person.

    Now convert it to CNF in a form ready for a refutation proof, and give a linear-input refutation proof of the conjecture.

Content

• Core of the language [Sut98 pp.3-14]
• More about terms [Sut98 pp.15-16]
• Debugging [Sut98 p.17]
• Arithmetic [Sut98 p.18]
• Lists [Sut98 pp.19-23]
• Manipulating expressions [Sut98 pp.24-25]
• Useful built0ins [Sut98 p.26]
• The Cut [Sut98 p.30-32]

Exam style questions

1. Write a Prolog program that counts the number of unique atoms in a list of atoms. The entry point to the program must be the clause unique/2. For example:

      ?-unique([cat,hat,cat,rat,mat,cat,hat],N).
      yes
      N = 4
      

2. Write Prolog programs for the following list manipulation procedures: Reverse, Permutation.
3. Write Prolog programs for the following list manipulation procedures: Delete, Insert.
4. Write Prolog programs for the following sorting procedures: Insertion-sort, Quick-sort and Merge-sort.
5. Write a Prolog program for computing derivatives.

Content

• Why search ?
• Generic Search Program
• Blind Search strategies: Depth-first, Breadth-first, Branch-and-Bound (also called, Lowest-cost-first)
• Informed Search strategies: Heuristic Depth-first, Best-first and A*
• Refinements: Cycle checking, Iterative deepening, Bidirectional search, Island-driven search and Dynamic Programming.

Exam style questions

1. Write Generic Search Program/algorithm and explain how to modify it to obtain specific Search strategies like DFS, BFS, Branch-and-Bound, Heuristic DFS, Best-first and A*.
2. Compare and contrast the above Search strategies by giving a table of advantages and disadvantages.
3. Compare and contrast Breadth-first and Depth-first search strategies.
4. Compare and contrast Breadth-first and Branch-and-Bound.
5. Compare and contrast Best-first and Branch-and-Bound.
6. Compare and contrast A*, Best-first and Branch-and-Bound.
7. Show the running of DFS, BFS and Branch-and-Bound on the following graph.
8. Show the running of Best-first and A* on the following graph.
9. Show the running of one blind search algorithm and one informed search algorithm on the following graph.
10. Show the running of your favorite search algorithm by taking the node "name" as an island through which your path from start to goal should pass.

Content

• What is knowledge and knowledge representation?
• Knowledge Representation Framework
• Defining a solution and its quality
• Hierarchy of Representations
• Choosing a level of abstraction
• Object-attribute-value Representation, PROP
• Semantic nets
• Frames

Exam style questions

1. Give a definition of "knowledge representation", based on appropriate definitions of "knowledge" and "representation".
2. Explain Optimal/Satisfying/Probable/Approximately-optimal solutions.
3. Represent the following knowledge using PROP.
4. Represent the following knowledge using a semantic net.
5. Design a representation scheme to represent any state in the Tic-tac-toe game and write a program for x-can-win(State) to decide whether X can win in the next move from `State'.

Content

• Knowledge-based system architecture
• Base language and Metalanguage
• Implementing the base language
• Vanilla Meta-interpreters
• Querying the user
• Explanations and Debugging

Exam style questions

1. Give a schematic diagram of the Knowledge based system architecture, showing the roles of various people and subsystems.
2. Write a vanilla meta-interpreter for pure Prolog.
3. Write a vanilla meta-interpreter that handles built-in predicate "is" and both disjunctive and conjunctive goals.
4. Write a vanilla meta-interpreter for depth-bounded proofs.
5. Explain "How" and "Why" questions.
6. Explain how to come-up with answers to "How" and "Why" questions.

Content

• Uncertain knowledge
• Probability theory
  • Axioms of probability
  • Prior probability
  • Conditional probability
  • Bayes' rule
• Representing uncertainty -- Belief Nets

Exam style questions

1. State the axioms of probability.
2. Explain the difference between prior probability and conditional probability. Give the formula for computing conditional probability from prior probabilities.
3. State the Chain rule.
4. State and explain Bayes' Theorem.
5. Explain conditional independence and give some examples.
6. Define belief networks, explain their use and construction.

Content

• Why learn ? -- New capabilities, better performance and skills.
• Learning architecture
• Supervised/Unsupervised learning
• Reinforcement learning (trail and error)
• Bias
• Noise
• Learning Decision Trees (ID3 Algorithm)
• Case based reasoning

Exam style questions

1. Explain the following terms in learning: (a) supervised learning, (b) unsupervised learning, (c) reinforcement learning, (d) bias (e) noise.
2. Define decision trees, give an example and explain their use.
3. Explain the ID3 algorithm for learning decision trees, write a (rough) Prolog code for it and show its run on the following data.
4. Explain Case based reasoning and how to come-up with a kd-tree.

Content

• Static/dynamic relations
• Primitive/derived relations
• STRIPS representation
• Situation Calculus
• STRIPS Planner, its problems and possible solutions
• Regression Planner

Exam style questions

1. Explain Static/dynamic relations.
2. Explain primitive/derived relations.
3. Describe three components of a STRIPS representation of an action.
4. Describe how a state is represented in situation calculus.
5. Explain the STRIPS planner and write a (rough) Prolog code for it.
6. State the drawbacks of STRIPS planner and suggest possible solutions.
7. Explain regression planner and describe how it avoids the drawbacks of STRIPS planner.