Test #1
Answers
CIS447 – February 16, 2006
Name ___KEY_____________________
The answers to #1 to #54 are found in the Answer Bank. Give the letter of the correct answer. All answers go on the Answer Sheet.
CIS447
For all questions use the Word Bank (below) and write the of the correct answer.
(1-22) Identify the following people who made major contributions of ideas leading to current work in Artificial Intelligence. [Note: Multiple numbers denote multiple answers].
1. Greek philosopher who did foundational work in logic and science.
Aristotle
2. Co-founded decision theory; proposed the stored program concept of computer architecture.
John von Neumann
3-4. Proposed the idea of modeling the human brain via networks of “neurons”.
Warren McCulloch
Walter Pitts
5. Foundational work in information theory; developed chess playing program.
Claude Shannon
6-7. Developed the Logic Theorist, a theorem-proving program, and the General Problem Solver (GPS).
Alan Newell
Herbert Simon
8. Developed resolution method of theorem proving.
John Robinson
9. An unabashed promoter of the expert systems approach; helped develop DENDRAL and MYCIN.
Edward Feigenbaum
10. His ELIZA program was designed to show how easy it is to create the illusion of intelligence in computer programs.
Joseph Weizenabum
11. Wrote The Laws of Thought.
George Boole
12-13. Wrote the Principia Mathematica
Bertrand Russell
Alfred North Whitehead
14-15. Their dispute over the foundations of mathematics sparked many significant developments in the theory of computation.
David Hilbert
Luitzen Brouwer
16. Initiated the search for effective proof procedures
David Hilbert
17. The Incompleteness Theorem
Kurt Goedel
18. Turned the Lambda Caluculus into the language Lisp.
John McCarthy
19-20. Established the foundations for the field of computational complexity theory.
Juris Hartmanis
Richard Stearns
21-22. Developed the theory of NP-completeness
Richard Karp
Stephen Cook
(23-25) Identify these men who formulated models of computation.
23. His model is a “machine” that bears his name; he also developed a chess playing program and worked on code breaking during World War II.
Alan Turing
24. Developed the Lambda Calculus, which is the basis for Lisp.
Alonzo Church
25. Developed production systems which bear his name and which are the basis for the forward chaining paradigm in expert systems.
Emil Post
EC1. How many of the men named above have been recipients of the Turing Award?
8
(26-34) Identify the following periods in the development of AI. For each period name one person, program or significant development.
26. 1943-55: The gestation of A.I.
Seeds of ideas developed
27. 1956: The birth of A.I.
First major milestone
28. 1952-69: Early enthusiasm; great expectations
Rapid development of early idea amid unbridled optimism
29. 1966-73: A dose of reality
Problems encountered; simple approaches do not scale up
30. 1969-79: Knowledge-based systems: The key to power?
Wide spread use of expert systems
31. 1980-present: A.I. becomes an industry
Specialized A.I. hardware & software companies sprout
32. 1986 - present :: The return of neural networks
Revival of McCulloch & Pitts’ model of computation
33. 1987 - present :: A.I becomes a science
Rigorous theorems, hard evidence, real-world applications
34. 1995 - present :: The emergence of intelligent agents
Various A.I. work is tied together under a unifying concept
(35-37) Identify the significance to computer science and/or A.I. resulting from the work described below.
35. Alan Turing’s Turing machine.
Theoretical model of the computer
36. Alonzo Church’s lambda calculus.
The basis for the language Lisp
37. Emil Post’s production system.
Forward chaining expert systems
(38-40) Identify these difficulties with early work in AI.
38. Early programs contained little or no _____ of their subject matter.
knowledge
39. Many problems attacked were inherently _____.
intractable
40. And there were fundamental limitations in the _____ used to generate intelligent behavior.
strategies
(41-42) Identify these events in the history of AI.
41. A report in Britain critical of AI which formed the basis for a decision by the British government to end support for AI research in all but two universities.
Lighthill Report
42. A period of time when AI fell out of favor, especially with respect to funding agencies.
A.I. Winter
43. The basic execution unit in Lisp is the _____.
form
44. For our purposes, _____ function in Lisp returns some value.
every
Non: some, no,
45-46. The basic data units in Lisp programs are the _____ and the _____.
atom
list
47. Lists are _____ sequences of elements.
ordered
Non: unordered
48-50. Meaningful Lisp forms may be divided into three categories. These are:
self-evaluating forms
symbols
lists
51. When a list is to be evaluated, the Lisp interpreter expects the first element of the list to be _____.
the name of a function
52-53. Except in special circumstances, the remaining elements of the list are taken to be _____ and are _____.
arguments
evaluated
54. Lisp runs in a . . .
Read-Eval-Print loop
Non: Fetch-Execute cycle
b. Recognize-Act cycle
Short Answer
(55-58) Russell and Norvig divide A.I. research into 4 categories. Name the research approach that matches each of the categories listed below.
55. Acting humanly.
Turing Test approach
56. Thinking humanly.
Cognitive modeling approach
57. Thinking rationally.
Laws of thought approach
58. Acting rationally.
Rational agent approach
(59-67) What will Lisp return when the following forms are typed at the top level?
59. (cons '(a b) '(a b))
==> ((a b) a b)
60. (append '(a b) '(a b))
==> (a b a b)
61. (list 'a '(b c))
==> (a (b c))
62. (first '((a b)(c d))
==> (a b)
63. (rest '(((((a) b) c) d) e))
==> ( e )
64. (if (= 2 3) (+ 2 3) (* 5 7))
==> 35
65. (cond
((> 3 2)(+ 5 6)(* 2 5)(/ 6 2))
(5 6))
==> 3
66. (eq 'a 'a)
==> T
67. (eq '(a) '(a))
==> NIL
(68-70) Write a sequence of firsts and rests to pick out the atom pear.
68. (apple orange pear grapefruit)
first – rest – rest
69. (apple (orange) ((pear)) (((grapefruit))))
first – first – first – rest – rest
70. (((apple) (orange) (pear) (grapefruit)))
first – first – rest – rest – first
(71-76) Write any 3 of the functions described below [value of each function = 2]:
A. Define: setu
Input: set1, set2 (two sets with no duplication of elements)
Returns: Union of set1 and set2.
(defun setu (set1 set2)
(cond ((endp set1) set2)
((member (first set1) set2)(setu (rest set1) set2))
(t (cons (first set1)(setu (rest set1) set2)))
))
B. Define: setint
Input: set1, set2
Returns: Intersection of set1 and set2.
(defun setint (set1 set2)
(cond ((endp set1) nil)
((member (first set1) set2)
(cons (first set1)(setint (rest set1) set2)))
(t (setint (rest set1) set2))
))
C. Define: setdf
Input: set1, set2
Returns: Set difference of set1 and set2.
(defun setdf (set1 set2)
(cond ((endp set1) nil)
((member (first set1) set2)(setdf (rest set1) set2))
(t (cons (first set1)(setdf (rest set1) set2)))
))
D. Define: clean
Input: list (a list, containing no sublists)
Returns: that same list with on duplication of elements
(defun clean (list)
(cond ((endp list) nil)
((member (first list)(rest list))(clean (rest list)))
(t (cons (first list)(clean (rest list))))
))
E. Define: flatten
Input: list (a list)
Returns: a list of the atomic elements of list and all its sublists.
E.g.: (flatten '(a (b c) d)) ̃ (a b c d)
(defun flatten (list)
(cond ((endp list) nil)
((consp (first list))
(append (flatten (first list))(flatten (rest list))))
(t (cons (first list)(flatten (rest list))))
))
F. Define: countatoms
Input: list (a list)
Returns: the number of atomic elements found in list and all its sublists.
E.g.: (countatoms '(a (b (c d) (e f) g)) ̃7
(defun countatoms (lst)
(cond ((endp lst) 0)
((atom (first lst))(1+ (countatoms (rest lst))))
(t (+ (countatoms (first lst))
(countatoms (rest lst))))
))
Some useful Lisp functions illustrated:
(last ‘(a b c d)) ̃ (d)
(butlast ‘(a b c d)) ̃ (a b c)
(length ‘(a b c d)) ̃4
(oddp 5) ̃ t; (oddp 6) ̃ nil
(nthcdr 3 ‘(1 2 3 4 5 6 7)) ̃ (4 5 6 7)
(reverse ‘(1 2 3 4 5 6 7)) ̃ (7 6 5 4 3 2 1)
(77-82) Write any 3 of the functions described below [value of each function = 2]. You may use any of the Lisp functions shown immediately above.
A. Define: rotate-left
Input: list (a list)
Returns: the same list with all elements rotated to the left.
E.g.: (rotate-left '(a b c d)) ̃ (b c d a)
(defun rl (list)
(append
(rest list)
(list (first list))
))
B. Define: rotate-right
Input: list (a list)
Returns: the same list with all elements rotated to the right.
E.g.: (rotate-right '(a b c d)) ̃ (d a b c)
(defun rr (list)
(append
(butlast list)
(last list)
))
C. Define: countodds
Input: list (a list of integers, which contains no sublists)
Returns: the number of odd integers in the list
E.g.: (countodds '(1 2 3 4 5)) ̃ 3
(defun count-odds (list)
(cond ((endp list) 0)
((oddp (first list)) (1+ (count-odds (rest list))))
((count-odds (rest list)))
D. Define: fib
Input: n, a positive integer
Returns: the nth Fibonacci number
Recall: the 1st two Fibonacci numbers are 1 & 1; after that each Fibonacci number is
the sum of the previous two.
E.g.: (fib 6) ̃ 8
(defun fib (n)
(if (<= n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))
))
E. Define: firstn
Input: n, list
Returns: the 1st n elements of the list;
unless n < (length list), in which case it returns nil.
E.g.: (firstn 3 '(1 2 3 4 5 6 7) ̃ (1 2 3)
(firstn 7 '(1 2 3) ̃ nil
(defun firstn (n list)
(let ((len (length list)))
(if (> n len) nil (reverse (nthcdr (- len n) (reverse list)))
)))
F. Define: pow, a function that takes a 2 positive integers, say base & expt, as argument and returns baseexpt, i.e., the 1st number raised to the power of the 2nd number.
(defun pow (base expt)
(if (zerop expt)
1
(* base (pow base (1- expt)))
))
Extra Credit:
Write any of the functions described below [value of each function = 3]. If you need any helper functions, you must show their definition also.
EC-1. Define: fclean
Input: list (a list which may contain sublists)
Returns: that same list with no duplication of elements
(defun same (x y)
(cond ((or (atom x)(atom y))(eq x y))
((and (subset x y)(subset y x)))
))
(defun subset (x y)
(cond ((null x) t)
((member (first x) y :test #'same)
(subset (rest x) y))))
(defun fclean (x)
(if (atom x)
x
(let ((cleancar (fclean (first x)))
(cleancdr (fclean (rest x))))
(if (member cleancar cleancdr :test #'same)
cleancdr
(cons cleancar cleancdr))
)))
EC-2. Define: rs
Input: n, a positive integer
Returns: As per sample output below:
Input Return
1 ( 1 )
2 ( 1 2 1 )
3 ( 1 2 1 3 1 2 1 )
4 ( 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 )
5 ( 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 )
(defun rs (n)
(if (= n 1) (list n) (append (rs (1- n)) (list n) (rs (1- n)))))
EC-3. Define: periodicity
Input: a list of integers
Returns: an integer indicating the periodicity of the list; i.e., the length of
the list’s repetitive sequence.
Examples:
(periodicity ‘(1 2 3 1 2 3)) ̃ 3
(periodicity ‘(1 2 1 1 1 2 1 1 1 2 1 1)) ̃ 4
(periodicity ‘(1 2 3)) ̃ 0
(periodicity ‘(1 1 1)) ̃ 1
ANSWER
Periodicty
CIS447 & related functions
Specification:
Define: periodicity
Input: a list
Returns: an integer indicating the periodicity of the list; i.e., the length of
the list’s repetitive sequence.
Examples:
(periodicity ‘(1 2 3 1 2 3)) ̃ 3
(periodicity ‘(1 2 1 1 1 2 1 1 1 2 1 1)) ̃ 4
(periodicity ‘(1 2 3)) ̃ 0
(periodicity ‘(1 1 1)) ̃ 1
(periodicity ‘(a b c a b c a b c)) ̃ 3
(periodicity ‘(a b a a a b a a a b a a)) ̃ 4
(periodicity ‘(a b c)) ̃ 0
(periodicity ‘(b b b)) ̃ 1
Discussion:
1. For length(list) < 2, periodicity = 0.
2. The periodicity of any list ≤ length(list) / 2.
3. If rotate(list,n) = list, then the periodicity of the list is n.
4. Since a list with a periodicity of n will also exhibit periodicities of m*n as long as m* n < length(list)/2, it is most efficient to test periodicity with smaller integers first.
(defun periodicity (list)
(if (< (length list) 2)
0
(p2 list 1 (div (length list) 2))
))
(defun p2 (list lo hi)
(cond ((> lo hi) 0)
((equal list (rotaten lo list)) lo)
(t (p2 list (1+ lo) hi))
))
(defun rotaten (n list)
(append (nthcdr n list)(firstn n list)))
(defun div (dvd dvzr) (let ((x (floor (/ dvd dvzr)))) x))
(defun firstn (n list)
(let ((len (length list)))
(if (> n len)
nil
(reverse (nthcdr (- len n) (reverse list)))
)))
EC-4. The NCAA basketball tournament begins with 64 teams. Suppose the tournament were played by the following rules. At the outset of the tournament each team has 8 players. After each game, the best 5 players from the winning team and the best 3 players from the losing team are selected to advance to the next level. Is it possible for any member of the championship team to have lost every game but one? If we added the number of losses each player incurred during the course of the tournament, and added that to get a team total, what is the maximum number of losses the championship team could have? What is the minimum?
yes
{3 x 5 = 15} + {3 x 4 = 12} + {2 x 3 = 6} ==> 33
3 x 1 = 3