UIT2201: CS & the IT Revolution
Tutorial Set 10 (Spring 2013)

(D-Problems discussed on Wednesday, 03-Apr-2013)
(Q-Problems due on Friday, 05-Apr-2013)

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


T10-D1: (Eight-puzzle)
Consider the state graph for the eight-puzzle with the following starting state:

                    1   3 
                    4 2 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.)


T10-D2: (Pick Up Sticks -- Game Strategy)
In this 2-player game, we start with 30 sticks. The players take turns picking up sticks. On each turn, a player must pick up 1, 2, or 3 sticks. The player who picks up the last stick loses.
Devise a winning strategy for this game.

[Note: Before doing the problems below, read lecture notes on Knowledge-based Systems.]


T10-D3: (PROLOG and Knowledge-Based System)
(a) Read Ch.9.4.2, pp. 452-457 of [SG3] on "Logic Programming and PROLOG for rule-based system".
(b) Practice Problem 1,2,3 of Ch.9.4.2 of [SG].


T10-D4: (Rule-based System for Road Network)

Assume you are given a road network, where the set of road junctions are denoted by A, B, C, D, E and the connecting roads by AB, BA, AD, BC, CB, BD, DE, ED, EC as shown below. (In the example, roads with arrows indicate one way streets.)

Assume that you have an automated vehicle and you want to go from a road junction A to road junction E.

Explain how you will model the above using a rule-based system so that you can find a route from any junction P to another junction Q for the automated vehicle. (Specifically, what location representation and rules would be needed to achieve this. State any assumptions made.)


T10-D5: [For fun. Only if you like it. Simple Neural networks] Prob 4 on Chapter 14 of [SG3].


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

T10-Q1: (10 points) (Eight-puzzle)
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.)


T10-Q2: (5 points) (Are Vending Machine Smart?)
Vending machine appear to be very smart and is able to dispense various products depending on which button is pressed.
(a) Would you say that such a machine is "aware" of which button is pressed and hence send out the correct product?
(b) Think of a simple test you can do to justify your answer.
(Limit your answer to one paragraph (6-10 lines). Long-winded answers will receive a grade of 0.)


T10-Q3: (10 points) (Rule-based Systems)
Question 5 of Spring 2010 Exam. -- [here]

A-Problems: OPTIONAL Challenging Problems for Further Exploration

A9-2013: (Something on AI, maybe later...)

UIT2201: CS & IT Revolution; (Spring 2013); A/P Leong HW