Midterm review

Turing Test

Understand what the Turing Test is testing, and what is required to pass it. Be able to explain how to run a proper Turing Test. Be able to explain the significance of a computer program that passes the Turing Test.

Given a particular initial state, fully-specified possible transitions for all states, goal criteria, action cost for every state transition, and heuristic function, be able to list the order that states are visited in a breadth-first or depth-first or best-first or A* search. (Assume the heuristic is “admissible,” i.e., an underestimate, and assume that breadth-first and depth-first follow children in alphabetical order.) Also be able to list the sequence of transitions (“path”) that each algorithm finds from the intial state to the goal.

For example, here is a graphical representation of possible transitions and action costs. The initial and goal states are also indicated. The heuristic value for each state is also shown in the state as “h = value”. The starting state is shown as a box (node “A”), and the goal state is shown as a double circle (node “G”).



Be able to write a PDDL file to represent a planning problem given in English.

For example, consider this planning problem:

The goal is to wash and dry a load of laundry. There is one washer and one dryer. The clothes must be washed before they can be dried. In order to wash clothes, the clothes have to be loaded into the washer, soap added, and the washer turned on. There can’t be clothes already in the washer. Likewise, the clothes cannot be moved to the dryer if there are already clothes in the dryer. The initial state is that the washer is empty, the dryer is empty, and we have a basket of dirty clothes. Ultimately, we want both the washer and dryer to be unloaded, and the basket to have clean clothes.

Given some starting tic-tac-toe board, be able draw and label a tic-tac-toe search tree, like the one below, with min/max labels on downward arrows, and utility values (1 or 0 or -1) on upward arrows.

For example, start with this board:

Tic-tac-toe start

The answer is available on the Midterm review solutions.

Genetic algorithms

Be able to define a genetic representation, fitness function, crossover function, and mutation function for a scenario specified in English. Be specific: indicate exactly how the representation and functions work. You will lose points if it is unclear to me exactly how they work.

For example, consider the following problem:

Suppose we have six surveillance cameras and need to install them in the ceiling of a grocery store in order to view and record as much floor area as possible. Suppose the store is rectangular but some aisles are taller than others, blocking a camera’s view from certain angles. Assume the cameras cannot pan, tilt, or zoom once they are positioned. We want to find an optimal or near-optimal placement of cameras so that the most area is covered.

Rules engine

Given a set of rules described in English, be able to write Drools rules that represent the same logic. The Drools file must have the correct syntax, but you do not need to provide the rest of the Java program to run the rules.

For example, consider the following logic about an issue tracking (ticketing) system:

A ticket is either open or closed, every ticket has an integer priority, as well as a “newCustomer” boolean field. Whenever a customer creates a ticket, the ticket gets added to the database. If the customer has never issued a ticket before, the ticket should have its “newCustomer” field set to “true”. Each ticket starts at priority 0. If the description of the ticket matches an existing open ticket (assume a matching function exists), then its priority is changed to the priority of the existing ticket plus 1; the priority of the existing tickets are left unchanged. If the customer has submitted more than 2 tickets with the same description, the priority of the new ticket is increased by 1. If the resulting priority of the ticket is greater than 3, an email is sent to the customer stating that “we are working hard on this problem.” If the description of the ticket matches a closed ticket, this ticket is closed as well (and priority is set to -1).


Know how to write Prolog code that represents a given set of facts and rules, stated in English.

Here are some examples:

  • Familial relations: mother, father, aunt, uncle, niece, nephew, cousin, half-brother, half-sister, etc.
  • Or, from Monty Python: “A witch is a female who burns. Witches burn - because they’re made of wood. Wood floats. What else floats on water? A duck; if something has the same weight as a duck it must float.” (quoted from this Prolog tutorial) The resulting Prolog code should be able to prove that witches float.

CSCI 431 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.