(print Review)

Review: week13

This is a Week13 | Review page, written Sun Apr 20 14:12:25 PDT 2008.

Describe iterative dicohomization. Your answer should include terms like "mixtures", "split", "recurse".
Using a formulae, define entrophy. What is the entrophy of a distribution of 8 "yes" and 4 "no" symbols (show all working).

Consider building the top layer of a decision tree using the following data. Using the entrophy equation, show how to decide between candidate attributes as being "best" for the root of the tree. Show all calculations.

@relation weather.symbolic

@attribute outlook {sunny, overcast, rainy}
@attribute temperature {hot, mild, cool}
@attribute humidity {high, normal}
@attribute windy {TRUE, FALSE}
@attribute play {yes, no}

@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no

Review: week 12

This is a Review | Week12 page, written Sun Apr 20 13:35:54 PDT 2008.

Explain, with examples, pattern movement
Explain the following, defining all terms. Flocking = seperation + alignment + cohesion.
Explain controlling flocks with leaders. Describe how to select leaders.
With the help of a diagram, explain way points. Describe path finding with ways points.

Draw the terrain represented by the adjacency matrix M2[u,v] where M1[u,v] is

M1=    A B C D E F G
     A . 1 . . . . . 
     B . . 1 . . . . 
     C . . . 1 1 . . 
     D . . . . . . . 
     E . . . . . 1 . 
     F . . . . . . 1 
     G . . . . . . .

Given a physical intepretaion to the terrain represented by the following M2[u,v] matrix. ALso, the point (B,G) is interesting: why?

M2=    A B C D E F G
     A . . . . 1 . . 
     B . . . . . 1 . 
     C . . . . . . . 
     D . . . . . . . 
     E 1 . . . . . . 
     F . 9 . . . . . 
     G . . 3 . . . .

What is the difference between a terrain map and an influence map? Describe the use of A-star and influence maps.
Draw a game tree for the next two moves in a tic-tac-toe game.
The above game tree is also called a min-max tree. Why?
Explain alpha-beta pruning using the following example:

Review: week 11

This is a Review | Week11 page, written Sun Apr 20 13:17:01 PDT 2008.

Explain, defining all terms: a JTMS is a serial world generator, the ATMS is a parallel world generator
Explain: the inventors of the ATMS claim that it solved the JTMS world thrashing problem
In the following diagram, explain what is going on here, defining all the graphical symbols:
Explain, defining all terms: LURCH is a stochastic serial world generator.
Explain my optimism for LURCH (i.e. it can miss thing and I don't care). Your explaination could use the following diagram (and it you use it, take care to explain all the features on this diagram):

Review: week10

This is a Week10 | Review page, written Sat Mar 15 15:21:25 PDT 2008.

Rule-based programming. Use this example for the following questions.
```
B3:
if	the step is pack-large-items
and	there is a large item to be packed
and	there is a large bottle to be packed
and	there is a bag with < 6 large items
then	put the bottle into the bag

B4:
if	the step is pack-large-items
and	there is a large item to be packed
and	there is a bag with < 6 large items
then	put the large item into the bag

B5:
if	the step is pack-large-items
then	the step is pack-medium-items
```
1. Define, with examples, rule conditions, and actions
2. Define, with an example, match/ select/ act for forward chaining
3. Define, with an example, Working memory, match, resolve, act
4. The above rules are used in a forward chaining method. Define backward chaining and explain why backward chaining supports how and why queries while forward chaining only supports how (note: an how query reports how a conclusion was reached while a why query can report, during the chaining, why the inference is exploring a particular literal. ).
5. With respect to the BAGGER rules described above, define with examples conflict resolution using:
  - Rule ordering
  - Data ordering
  - Specificity ordering
  - Size ordering (and your answer should explain why size ordering is faster than specificity ordering)
Large rule-based systems.
1. "The global and uniform nature of rule-based systems is both a blessing and a curse". Explain, with examples from the history of rule-based systems.
2. Define the RETE network, explaining its theoretical benefits.
3. The two most successful experiments in building and maintaining large rule-based systems were conducted by John McDermott and Paul Compton. These experiments took very difference stances about the nature of the rule maintenance problem:
  - McDermott: if can't use it, don't ask for it.
  - Compton: if it works, don't change it
  Explain these two stances using the following proposed definition of "diagnosis"
4. Compton's ripple down rules take the form
```
rule ID1 if condition THEN EXCEPT rule ID2 THEN conclusion because EXAMple
```
  Explain the use of this rule using the following example:
5. Using the above example, explain "difference list" generation.

Review: Week 9

This is a Week9 | Review page, written Thu Mar 6 09:25:48 PST 2008.

Note: This material is now not examinable

Graph-based abduction

Given "Goals"= {a,b} and "In"= {x,y,z}, what are the paths from goals back to the Ins?

if x then not_j
if not_j then d
if y then not_d
if not_d then j
if j  then e
if d then c
if e then c
if c then a
if e then k
if k then b

Your paths use terms such as "not d", a, etc. Let "Facts" = "In" + "Goals", and assumptions "A" be "Used - Facts". Some assumptions contract other assumptions. Assuming "inconsistent(X, not_X)", write down
- Used
- Facts
- Assumptions
- Controversial assumptions
Some controversial assumptions are "base", i.e. they depend on no upstream controversial assumption. Write down the base "B" for this example.
One world "W" exists for each maximal consistent subset of the base controversial assumptions. Write those subsets.
Worlds contain paths and, internally, each world is consistent. For each of the subsets from the last question, write down the paths in each world.
Using the above, propose a "probe"; i.e. the single most informative question that rules out the most worlds.
If this is some medical diagnosis domain, where further data collection is expensive, propose a monitoring strategy which, when data data becomes available, we can refer to our worlds to determine the remaining set of beliefs.

Review : week 6

This is a Review | Week6 page, written Sun Feb 17 13:27:37 PST 2008.

Distinguish between classical logic and fuzzy logic. Your answer should include "membership function", "crisp", "fuzzy" and "set".
Define with examples, fuzzification, rule evaluation, de-fuzzification
Write down the three Zadeh operators. Illustrate each with a diagram.
Here is the truth table for classical logic
```
A	B	A and B		A or B		not A
--	--	-----------	--------	-------
0	0	0		0		1
0	1	0		1		1
1	0	0		1		0
1	1	1		1		0
```
Reproduce this table using the Zadeh operators for (A B) = (0.3 0.7).
Define the extension principle and its implications for the connection of classical logic to fuzzy logic. Using the Zadeh operators, demonstrate the extension principle for row 2 or the above table. Show all calculations

Draw the following membership function for

(a b crisp)= ( -50,50,0.1) and
(a b crisp)= ( -50,50,1)

(defun crisp (x a b crisp)
  "Return a point in a sigmoid function centered at (a - b)/2"
  (labels ((as100 (x min max)
	     (+ -50 (* 100 (/ (- x min) (- max min))))))
    (/ 1 (+ 1 (exp (* -1 (as100 x a b) crisp))))))

Mark on the x-axis the key points of the function.

Draw the following membership function for (x a b c) = (x 10 20 30).
```
(defun fuzzy-fun1 (x a b c) 
  (max 0 (min (/ (- x a) (- b a))
	      (/ (- c x) (- c b)))))
```
Mark on the x-axis the key points of the function.
Draw the following membership function for (x a b c d) = (x 10 20 30 60).
```
(defun fuzzy-fun2 (x a b c d)
  (max 0 (min (/ (- x a) (- b a))
	      1
	      (/ (- d x) (- d c)))))
```
Mark on the x-axis the key points of the function.

On one plot, draw the following membership functions for (dist 'close) (dist 'medium) (dist 'far)

(defun dist (d what)  
  (case what
    (range    '(close medium far))
    (close     (fuzzy-triangle   d -30 0 30))
    (medium    (fuzzy-trapezoid  d 10 30  50 70))
    (far       (fuzzy-grade      d 0.3  50 100))
    (t         (warn "~a not known to dist" what))))

Mark on the x-axis the key points of these functions.

Review: week5

This is a Review | Week5 page, written Sun Feb 17 13:26:22 PST 2008.

DFID
1. Describe DFID
2. Contrast DFID with breadth-first and depth-first search. Your answer should define breath-first an depth-first search, and the maximum running time and memory of each method.
3. It can be shown that DFID visits all nodes with maximum frequency M(b,d) ≤ b^d*(1 - 1/b)^(-2) where b is the branching factor of the search space and d is the depth of the search, Here are some values from M(b,d)
  - When b=2, M(b,d) ≤ 4 * b^d
  - When b=3, M(b,d) ≤ 9/4 * b^d
  - When b=4, M(b,d) ≤ 16/9 * b^d
  - When b=5, M(b,d) ≤ 25/16 * b^d
  Using these values, describe when you would or would not recommend DFID. Make sure you explain your answers
ISSAMP
1. Write down the pseudo-code for ISSAMP Make sure your code has line numbers. (Note the pseudo code for ISSAMP includes a "unit propagation" step which is a black box to you. Just assume it means "see what can be quickly inferred from the current solution").
2. Explain the following using a paragraph or two of English and line numbers into your pseudo-code: ISSAMP search is
  - uniformed,
  - incomplete,
  - stochastic
  - does not use local search
  - uses restarts
  - and uses very little memory.
A* is a best-first search of graph with a *visited* list where states are sorted by "g+h". Explain all the terms in the prior sentence
MAXWALKSAT
1. Write down the pseudo-code for MAXWALKSAT Make sure your code has line numbers.
2. Explain the following using a paragraph or two of English and line numbers into your pseudo-code: MAXWALKSAT search is
  - sometimes uniformed,
  - incomplete,
  - stochastic
  - sometimes, uses local search
  - uses restarts
  - and uses very little memory.

Review: week 4

This is a Review | Week4 page, written Sun Feb 10 06:08:28 PST 2008.

For each of the following search methods: depth-first, breadth-first, best, beam:

Define them. Where possible, your definition should include terms like combiner, ranker, cost function, h(x).
Characterize their maximum memory and run time in terms of a search tree's branching factor "b" and search tree depth "d".
Comment on whether or not the algorithm s guaranteed to find an optimal solution.
Comment on under what conditions the the algorithm will not return an acceptable solution.

Review: week 3

This is a Review | Week3 page, written Fri Feb 1 12:01:17 PST 2008.

Functional programming and sorting
1. Read http://www.n-a-n-o.com/lisp/cmucl-tutorials/LISP-tutorial-21.html. Write an anonymous lambda function that returns t if the car one list is numerically less than the car of another.
2. Write an example of using the above to sort a list ((10 . a ) (5 . b ) (20 . c)) Do not use the :key argument.
3. Read http://www.delorie.com/gnu/docs/emacs/cl_50.html. Using string-lessp and :key, write the "words-sort" function needed for the following function. (defun sort-words-demo () (words-sort '(i have gone to seek a great perhaps)))
Search control
- Write an anonymous lambda function that returns true if some argument x equals the value 12.
- Write a successors function for a binary tree that returns a list containing "twice the passed argument" and "twice the argument plus one"
- Write a successor function of a finite tree that calls the above successor function and prunes any successors greater than some value n.
Search
- Give an example of an ordered search problem.
- Give an example of an unordered search problem.
- Consider the task of leaving the class and arriving at downtown Morgantown. How can this task be characterized in terms of [N,A,S,G], g(x), h(x), d and b.
- Consider this generic search function:
```
(defun tree-search (states goal-p  successors combiner)
	 (labels ((next  ()       (funcall successors (first states)))
	          (more-states () (funcall combiner   (next) (rest states))
	    (cond ((null states) nil)                              ; failure. boo!
	          ((funcall goal-p (first states)) (first states)) ; success!
			  (t  (tree-search                                 ; more to do
			       (more-states) goal-p successors combiner))))
```
- Starting a number "1", give an example of depth first search using "tree-search". Hints: 1) you may use the functions described in the above questions. 2) In DFS, new states are "combiner"-ed to the end of the current states./
- Starting a number "1", give an example of beam first search using "tree-search". Hints: 1) beam search is a breadth first search that sorts the list of states according to some predicate. 2) In BFS, new states are "combiner"-ed to the beginning of the current state.

Week 2 review questions

This is a Week2 | Review page, written Thu Jan 24 11:28:40 PST 2008.

(Note to CS472 students. While the quiz will be drawn from questions like the following, the precise details of the exam questions may be somewhat different to the following. So don't rote learn these- rather, strive to understand the principles behind these questions. )

Write a function to exponentiate , or raise a number to an integer power.
For example: (power 3 2)= 3*3 = 9
Do it three ways (and, for a hint, see here)
1. Do it using a looping construct (no recursion).
2. Do it using a recursive call to the same top-level function
3. Do it using a helper function defined inside the top-level function.
Write a function that counts the number of times an expression occurs anywhere within another expression. Example:
(count-anywhere 'a '(a ((a) b) a)) ==> 3
Hint: your function should recurse on all parts of the list.

Consider the following function:

what do apply, append, mapcar do?

(defun mappend (fn list)
  (apply #'append (mapcar fn list)))

What is the output of this code?

(defun numbers-and-negations (input)
    (mappend #'number-and-negation input))

(defun number-and-negation (x)
  "If x is a number, return a list of x and -x."
    (if (numberp x)
	     (list x (- x))
        nil))

Write grammars recording the steps required to achieve some goal:
1. For getting a university degree e.g.
```
(defparameter *education*
		'((graduate -> preschool high-school undergrad)
		  (high-school -> grade-school high-years)
		  (high-years -> hiyear1 hiyear2 hiyear3 hiyear4)
...)
```
2. Your grammar should support stochastic plan generation. Does it? Why?
3. Repeat the above for the task of assembling a car.
4. Augment the grammar with some benefit score in the head and some cost score in the tail (so when a goal is achieved, we add that to a "hooray!" score while adding the cost of the tail to some "boo!" score)

Week 1 : review

This is a Week1 | Review page, written Thu Jan 17 11:07:27 PST 2008.

Planes fly without flapping there wings. The Platonic beast walks using more than two legs.
1. In what sense do planes do/don't "really" fly?
2. In what sense does the Platonic beast does/does not "really" walk?
3. Offer a definition of flying that includes air planes and birds. What other things can this definition apply to?
4. Offer an abstract description of walking that includes humans and the Platonic Beast? What other things can the definition apply to?
The Knowledge level
1. What is Newell's abstract description of a intelligence (hint: knowledge-level agent, principle of rationality).
2. You want to get to downtown Morgantown. What are the states between here and there?
3. What operators are available to you to get to downtown?
4. What knowledge could you use to decide which operators to apply?
Simulated annealing
1. Write down the pseudo-code for simulated annealing. Make sure your code has line numbers.
2. Explain the following using a paragraph or two of English and line numbers into your pseudo-code: a simulator annealing search is
  - uniformed,
  - incomplete,
  - stochastic
  - local search
  - best suited to non-linear problems
  - uses no restarts
  - and uses very little memory.
3. Why was using very little memory very important when simulated annealing was invented (1953)?
4. What is local search and why might it be useful in a search problem?
5. What are restarts and why might restarts be useful in a search problem ?

(print *Review*)

Note: This material is now not examinable

(print Review)