Question 2
For this question, you should write a short report that explains how your program works and give some execution examples.
Given a graph G and two nodes A and Z in G, write a program in Prolog or Lisp that finds an acyclic path P between A and Z. The path should be represented as an ordered list of nodes from the start node to the goal node. Since the path must be acyclic, a node can appear in the path only once.
Question 3
For this question, you should write a short report that explains how your program works and give some execution examples.
Consider the following graph that has costs attached to its edges:
Write a program in Prolog or Lisp that given two nodes X and Y in the graph above will find the minimum-cost path from node X to node Y and display the found path and its cost. All data about the graph should be declared in the program.
Example: the minimum path between a and d is [a,b,c,d] with cost = 6.
Question 4
For this question, you should write a short report that explains how your program works and give some execution examples.
Write a Prolog/Lisp program that teaches children how to pronounce multisyllable words by dividing them into syllables. Limit your program to deal only with syllables of the following two sequences:
- vowel–consonant–vowel: divide the word after the second vowel.
Example: analog —> ana-log
- vowel–consonant–consonant–vowel: divide the word between the two consonants.
Example: bumper —> bum-per
Question 5
Consider the famous problem of a farmer having a goat, a wolf, and a cabbage. The farmer wants to cross the river from the east shore to the west shore, but his boat is small. The boat has space for only the farmer with one of the items: cabbage, wolf, or goat. The farmer cannot leave the wolf alone with the goat or the goat alone with the cabbage.
The state space for this problem can be represented by the different situations of the four subjects that can be at any time either on the east or the west shore, but when moving from one state to another the items are subject to the conditions specified in the previous paragraph.
We can represent a state space by the relation s(X, Y), which is true only if there is a legal move from state X to state Y within the specified conditions.
Each state can be represented by the tuple (FP, GP, WP, CP), where the variables FP, GP, WP, CP can have only two values (e, w), which indicate the position east or west of the farmer, goat, wolf, and cabbage.
The initial state of the system can be represented by (e, e, e, e), where all subjects are on the east side.
The goal state of the system can be represented by (w, w, w, w), where all subjects have been moved to the west side.
Other intermediate states will be represented using combinations of these positions (e,w).
Write a depth-first search program with cycle detection to find and display different solution paths for the farmer problem. (20 marks)
Write a breadth-first search program with cycle detection to find and display different solution paths for the farmer problem. (20 marks)