UIT2201: CS & the IT Revolution
Tutorial Set 12 (Fall 2016)

(D-Problems discussed on Friday, 04-Oct-2016)
(Q-Problems (Updated!) due on Tuesday, 08-Nov-2016)
(Updated on 04-Nov (Fri), after tutorials!)

Discussion Problems: -- Prepare (individually) for tutorial discussion.

T12-D1: (Upgrading Eliza to do Useful Tasks)
In the lectures, we learnt about how Eliza is not a real psycho-therapist. In fact, is it not intelligent at all. Yet, we also mention that Eliza-like chat bots (aka chatterbots) are now used to handle questions in call centers.
Put on your ITeM thinking hat and think about the changes and enhancements that need to be made to Eliza to turn it into seemingly intelligent call centre service staff.
[Note: As usual, list out the capabilities that Eliza will need to have and if you can, briefly describe how each capability might be achieved, using the knowledge you have acquired so far in this course and in your project.]

T12-D2: (Eight-puzzle) [State Space Search]
Consider the state graph for the eight-puzzle with the following starting state:

                    1   2 
                    4 5 3
                    7 8 6
(a) Draw all states that are within 3 moves of the above starting state.
(b) Give a shortest path from the starting state to the goal state.
(NOTE: A given state is represented only once in a state diagram. Do NOT duplicate states.)

T12-D3: (PROLOG and Knowledge-Based System)
(a) Read Lecture notes or Ch.9.4.2, pp. 452-457 of [SG3] on "Logic Programming and PROLOG".
(Esp UPDATED lecture notes on PROLOG, with worked examples of rule-expansions!)
(b) (Practice Problem 1,2,3 of Ch.9.4.2 of [SG].)
Using the Prolog program of Figure 9.10, what is the result of each of the following queries?
PP1. ?-before(jefferson, kennedy).
PP2. ?-president(X, lewis_and_clark).
PP3. ?-precedes(jefferson, X). (Show sequence of rule-expansions to get the answer.)

Problems to be Handed in for Grading by the Deadline:
(Note: Please submit hard copy to me. Not just soft copy via email.)

T12-Q1: (10 points) (Eight-puzzle)
Consider the state graph for the eight-puzzle with the following starting state:

                    1 2 3 
                      4 6
                    7 5 8
(a) Draw all states that are within 3 moves of the above starting state.
(b) Give a shortest path from the starting state to the goal state.
(NOTE: A given state is represented only once in a state diagram. DO NOT duplicate states.)


T12-Q2: (5 points) (Pancake Flipping) Question 5(b) of Fall 2014 Exam. -- [here]


T12-Q3: (15 points) (PROLOG and Knowledge-Based System)
Note: Read lecture notes (on Prolog) or Ch.9.4.2, pp. 452-457 of [SG3] on "Logic Programming and PROLOG for rule-based system".

(a) Using the Prolog program of Figure 9.10, what is the result of each of the following queries? Here, U is a "variable" in Prolog.

  1. ?-before(U, kennedy).
  2. ?-precedes(kennedy, nixon). (Show sequence of rule-expansions to get the answer.)
  3. ?-precedes(S, fdr). (Show sequence of rule-expansions to get the answer.)
(b) Suppose we add the following additional facts to the fact-base of the Prolog program of Figure 9.10, Now, give the result of each of the following queries? Here, T is a "variable" in Prolog.
  1. ?-precedes(carter, T). (Show sequence of rule-expansions to get the answer.)
  2. ?-precedes(kennedy, reagan). (Show sequence of rule-expansions to get the answer.)
    3.



UIT2201: CS & IT Revolution; (Fall 2016); A/P Leong HW