Title
CSC 447 :: MidTerm Study Sheet
In addition to what is below – look over examples of tests from previous semesters.
Topics, concepts, facts, ideas covered
Python
1 – in Python, write a recursive function to compute factorial
def fact(n):
if n > 0:
return n*fact(n-1)
else:
return 1
2 – let L be a list of integers; use map & lambda to write a line of code which produces a list of those integers squared.
>>> L = [3,44,5,66,31]
>>> map((lambda x: x*x),L)
[9, 1936, 25, 4356, 961]
>>>
3 – write the generator function gensym which yields a new, unique symbol each time it is invoked; show how it is set up and called.
>>> def gensym():
count = -1
while True:
count += 1
yield 'node'+str(count)
>>> g = gensym()
>>> g.next()
'node0'
>>> g.next()
'node1'
>>>
4 – given, L, a list of pairs of integers, write a line of code to sort that list by the first elements of the list; then by the second elements.
>>> L.sort(sort1s)
>>> L
[[2, 3], [6, 1], [55, 77], [99, 44]]
>>> def sort2s(pair1,pair2):
return cmp(pair1[1],pair2[1])
>>> L.sort(sort2s)
>>> L
[[6, 1], [2, 3], [99, 44], [55, 77]]
>>>
5 – from the CDR project, write the function getDistances which takes a list of buildings as argument, opens a file containing a 2d matrix of distances and returns a dictionary object indexed by buildings and giving the distances between them.
def getDistances(bldgs):
dtable = open('distanceTable.txt','r')
dist = {}
for frm in bldgs:
dist[frm] = {}
rowList = readIntegers(dtable)
index = 0
for to in bldgs:
dist[frm][to] = rowList[index]
index += 1
return dist
>>> bldgs = readBuildings()
>>> dist = getDistances(bldgs)
>>> dist['OM']['LY']
31
>>> type(dist)
>>>
6 – write Python code to find the minimum & maximum item in a list and to obtain the sum of all elements of a list.
>>> L = [55,87,23,11,98,121,4]
>>> min(L)
4
>>> max(L)
121
>>> sum(L)
399
>>>
Myro
1 – what does the following Myro code do (approximately)?
forward(1, 1)
turnLeft(1, .3)
forward(1, 1)
turnLeft(1, .3)
forward(1, 1)
turnLeft(1, .3)
forward(1, 1)
turnLeft(1, .3)
go in a square
2 – write a Myro program to do a little dance routine
Here's an example:
def yomama(times):
for i in range(times):
forward(.5)
wait(.5)
backward(.5)
wait(.5)
stop()
def wigout(speed,waitt):
rotate(-speed)
wait(waitt)
rotate(speed)
wait(waitt)
stop()
def yowig(x,y,z):
yomama(x)
wigout(y,z)
yomama(x)
wigout(y,z)
beep(.5,400)
stop()
3 – write a line of code to have Myro give you a greeting
Here's an example:
speak('good morning')
4 – write Myro code to take a picture storing it in a variable; then show it. Take the picture first in color, then in grayscale.
>>> pColor = takePicture()
OR: pColor = takePicture("color")
>>> show(pColor)
>>> type(pColor)
>>> pGray = takePicture("gray")
>>> show(pGray)
5 – write Myro code to take a picture storing it in a variable; then show it and store the red, green, blue values of some pixel from that picture. Finally, save the picture on the hard drive for later use.
>>> pColor = takePicture()
>>> show(pColor)
>>> p00 = getPixel(pColor,0,0)
>>> p00
>>> type(p00)
>>> getRGB(p00)
(15, 12, 43)
>>> r,g,b = getRGB(p00)
>>> r
15
>>> g
12
>>> b
43
OR::
r,g,b = getRGB(getPixel(pColor,0,0)
savePicture(pColor, "savedPColor.jpg")
5 – write Myro code to retrieve a picture from the disk for processing. Assume that the function allReds returns a list of all R values in the picture. Write code to find the average value of the R component of the picture.
>>> p = makePicture("savedPColor.jpg")
>>> show(p)
rr = allReds(p)
avRed = sum(rr)/len(rr)
CDR Problem
Analysis of genPerms
– Big O of space
– Big O of time
– number of calls to function Perm
Exhaustive search solution of CDR
– basic algorithm
generate all permutations of tasks
compute total time for each permutation
identify optimal sequence of tasks
A* applied to CDR
– a heuristic function for A*
is the heuristic admissible?
– contents of a node
name
path
current dropoff location
deliveries (tasks) remaining
endpoint
g-value
h-value
f-value
– role of nodelist
store all unexpanded nodes
keep nodes ordered by f-value
– expanding a node
create children, one for each delivery remaining
for each child node created
move delivery chosen from deliveries remaining to path
compute g-value
(add cost of delivery to previous g-value)
compute h-value
compute f-value
remove expanded node from nodelist
add all children to nodelist, keeping list sorted by f-value
– recognizing solution
when node at head of nodelist has a completed path, that is a
solution
Note: completed path has all tasks completed & Dieter has
reached endpoint
No node remaining on nodelist could be a better solution, because heuristic is admissible
Improving A* applied to CDR
– compute an upper bound to final path cost
– when expanding, discard any child nodes with f-value greater than
upper bound
– upper bound algorithm
arrange dropoff and pickup points as 2d matrix
basic idea:: any solution must have exactly one entry from each
row and one from each column
choose the minimum value in the matrix
add that value to SUM
remove the row and the column in which it is found
continue this process until matrix is empty
– alternate upper bound algorithm
find maximum value in the matrix
choose the smallest value in either the row or the column of that value
AI History & Theory
Questions from previous tests & exams:
State space search:
(1-4) Identify these criteria for evaluating search strategies:
1. Is the strategy guaranteed to find a solution if there is one?
completeness
2. How long does it take to find a solution?
time complexity
3. How much memory does it need to do the search?
space complexity
4. If there are several solutions, does it find the best one?
optimality
(5-8) Identify the two basic categories of search.
5. Has no information about the search space.
uninformed search
6. also known as . . .
blind search
7. Makes use of information about the search space.
informed search
8. often also called . . .
heuristic search
(9-12) Identify the search strategies described below:
9. Tries successively deeper depth limits.
iterative deepening search
10. Finish one branch before starting on another.
depth-first search
11. All nodes at depth d are expanded before any nodes at depth d+1.
breadth-first search
12. Imposes cutoff on maximum depth of search.
depth-limited search
(13-32) Give the requested information about each search strategy listed below.
Depth-first search:
13. Complete?
no
14. Time complexity?
bm, where m is the maximum depth of the search tree
15. Space complexity?
bm, where m is the maximum depth of the search tree
16. Optimal?
no
Breadth-first search:
17. Complete?
yes
18. Time complexity?
bd+1, where d is the depth of the shallowest goal state
19. Space complexity?
bd+1, where d is the depth of the shallowest goal state
20. Optimal?
Yes, if path cost is a non-decreasing function of the depth of the node.
Bidirectional search:
21. Complete?
yes
22. Time complexity?
bd/2,where d is the depth of the shallowest goal state
23. Space complexity?
bd/2, where d is the depth of the shallowest goal state
24. Optimal?
Yes
Depth-limited search:
25. Complete?
Yes/no – only if d ≤ L
26. Time complexity?
bL, where L is the search depth limit
27. Space complexity?
bL, where L is the search depth limit
28. Optimal?
no
Iterative deepening search:
29. Complete?
yes
30. Time complexity?
bd, where d is the depth of the shallowest goal state
31. Space complexity?
bd, where d is the depth of the shallowest goal state
32. Optimal?
Yes, if path cost is a non-decreasing function of the depth of the node.
(33-37) Identify the basic components of a state space search node:
33. the current configuration in the state space
state
34. the steps taken to reach this state
the steps taken to reach this state
path
35. the value computed by the heuristic function; an estimate of the distance
remaining to the goal state
h
36. The cost of reaching this state
g
37. f
g + h
(38-44) Identify the following periods in the development of AI.
38. 1966-73: Problems encountered; simple approaches do not “scale up”
A dose of reality
40. 1995 - present :: Work on building complete agents, pulling together work from subareas.
Intelligent agents
39. 1952-69: Rapid development of ideas amid unbridled optimism.
Early enthusiasm; great expectations
40. 1986 - present :: Revival of McCulloch & Pitts’ model of computation.
Neural Networks again
41. 1956: Dartmouth Conference
Birth of AI
42. 1943-55: “Seeds” of ideas developed.
Gestation
40. 1987 - present :: Build on existing systems; base claims on rigorous theorems and/or hard experimental evidence
AI adopts scientific method
44. 2001-present: Apply machine learning methods to the "knowledge Bottleneck"
Availability of very large data sets
43. 1969-79: Wide spread use of expert systems.
Knowledge-based systems
44. 1980-present: Specialized A.I. hardware & software companies sprout.
The AI Industry
(45-48) Identify the approach to the study of A.I. named.
45. Rational agent approach
acting rationally
46. Turing Test approach
acting humanly
47. Laws of thought approach
thinking rationally
48. Cognitive modeling approach
thinking humanly
(49-50) Identify these events in the history of AI.
49. 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.
The Lighthill Report
50. A period of time when AI fell out of favor, especially with respect to funding agencies.
AI Winter
Short Answer Questions
72. A heuristic for A* is called admissible when . .
It never overestimate the distance to the goal
73. Given two heuristics, h1 and h2, we say h1 dominates h2 if . .
h1(n) ( h2(n) for all configurations/nodes n.
74. Give a cogent argument why OOP (number of tiles out of place) and manh (Manhattan distance) are admissible for the 8 puzzle.
OOP – if a tile is out of place, it must be moved. Therefore the number of steps to the goal can never be less than the number of tiles out of place.
manh – each out of place tile must travel the Manhattan distance to reach its goal position. Therefore the number of total steps can never be less than the sum of distances each of the tiles must travel.
75-75. Prove: manh dominates OOP.
Proof:
Since both sum a value obtained for each tile, all we need do is prove that for an arbitrary tile, t, manh(t) (OOP(t).
There are two cases:
1. t is already in the goal position
manh(t) = 0
OOP(t) = 0
So, manh(t) ( OOP(t)
2. t is not in the goal position
OOP(t) = 1
manh(t) ( 1, since t must travel some nonzero distance.
So, manh(t) ( OOP(t)
This proves that manh dominates OOP.
78-80. At the lines indicated by ** give the result of the execution of the sequence of entries to the Python shell.
>>> L1 =[1,2,3]
>>> L1.append(5)
>>> L1
**
>>> L2 = [6,7,8]
>>> L3 = L1 + L2
>>> L3
**
>>> L4 = L3.append(L2)
>>> L3
**
>>>
ANSWER:
>>> L1 =[1,2,3]
>>> L1.append(5)
>>> L1
[1, 2, 3, 5]
>>> L2 = [6,7,8]
>>> L3 = L1 + L2
>>> L3
[1, 2, 3, 5, 6, 7, 8]
>>> L4 = L3.append(L2)
>>> L4
>>> L3
[1, 2, 3, 5, 6, 7, 8, [6, 7, 8]]
>>>
>>> L1
[1, 2, 3, 5]
>>> L1 + 7
Traceback (most recent call last):
File "", line 1, in
L1 + 7
TypeError: can only concatenate list (not "int") to list
>>>
81. Suppose we have the list, L
L = [[1,10,11],[2,5,19],[3,12,21]]
Write a function which, when used with sort will allow us to transform L into this list:
[[2, 5, 19], [1, 10, 11], [3, 12, 21]]
In other words to allow us to sort on the second element in each of the sublists of L.
>>> L = [[1,10,11],[2,5,19],[3,12,21]]
ANSWER:
>>> def cmp2nd(a,b):
return cmp(a[1],b[1])
>>> L = [[1,10,11],[2,5,19],[3,12,21]]
>>> L.sort(cmp2nd)
>>> L
[[2, 5, 19], [1, 10, 11], [3, 12, 21]]
>>>
86-90. Compare A* search with respect to the 4 evaluation criteria – completeness, optimality, space complexity and time complexity – to depth-first and breadth-first search. Give justification for your analysis.
completeness – yes
optimality – yes
space complexity – more than depth-first, because must store a wider swath than just the direct path; but less than breadth-first, since as you go deeper the swath gets more narrow & never gets wide enough to encompass all nodes at all levels higher than d.
time complexity – less than both depth-first and breadth-first, because less nodes are considered and expanded.
Additional factor – the amount by which it is better depends on how good the heuristic is. In worst case, A* degenerates to breadth-first.
More formally{This discussion of #86-90 will not be on the midterm}:
Let h0 be the null heuristic, defined as follows:
h0(n) = 0, ∀n in the A* search tree.***
In other words, this heuristic gives us no information, so we are back to the blind search situation.
And let hcb be the crystal ball heuristic, defined as follows:
hcb(n) = s-dist(n), ∀n in the A* search tree,
where s-dist(n) is the actual distance from node n to the goal node.
In other words, this heuristic has perfect knowledge of the search space.
And let ha be any generic admissible heuristic.
Then,
h0(n) ( ha(n) ( hcb(n), ∀n in the A* search tree.
In other words, being admissible ha can never overestimate the distance to the goal. Hence:
ha(n) ( hcb(n)
And, as stated in Russell and Norvig, A* only works in a state space where there is never a negative cost for an action. Hence:
h0(n) ( ha(n)
We now explore each of these cases in turn. Suppose,
ha(n) = h0(n)
Then A* degenerates to breadth-first search, since there is no differentiation between nodes. We wind up expanding every node a one level, and then go on to expand all the nodes at the next level, and so on. In this case, as with breadth-first search, both time and space complexity of A* is bd+1.
On the other hand, suppose,
ha(n) = hcb(n)
Then, at every level, A* chooses for expansion that node from the Waiting List which is on the shortest path. Since, the process of expansion produces all the children of the node being expanded, the set of nodes produced is the nodes on the shortest path along with all of their siblings. Thus, both time and space complexity are bd. It is important to note that the siblings of the node on the shortest path are never expanded if, in case of a tie with respect to f-value, we always choose the most recently produced node.
This is summarized in the table below:
| |A* – best case |Depth 1st |A* – worst case |Breadth 1st |
| O(time) | bd | bm | bd+1 | bd+1 |
| O(space) | bd | bm | bd+1 | bd+1 |
| Complete | Yes | No | Yes | Yes |
| Optimal | Yes | No | Yes | Yes |
Thus, just as breadth first is better than depth first in terms of time, A* is also – even in the worst case scenario. And, although space usage depends on the merit of the heuristic, it can in some cases be an improvement over depth first search. With respect to breadth first search, A* can be no worse in both space and time and – as long as the heuristic yields even a modicum of useful information – A* is better.
Or, put in terms of comparison – on the average:
O(time):: A*b < A*w/Brd < Dpth
O(space):: A*b < Dpth < A*w/Brdt
where,
A*b = A*-best
A*w/Brd = A*-worst, which is same as Breadth-1st
The reason why A* can be worse than depth first in terms of space is explored in #EC-5.
***Strictly speaking, heuristic functions are not applied to nodes but to the states of nodes. So we should write h(ns), where ns is the state of node n. For simplicity, though, we will write h(n).
Beginnings of A.I.:
1. The beginning of A.I. is widely held to be the _____ which took place in 1956.
Dartmouth Conference
2-4. Among those attending the conference were A.I. pioneers _____, _____, and _____.
John McCarthy
Herbert Simon
Allen Newell
5. Additionally, in attendance was _____, the father of information theory, who had written a paper on computer chess.
Claude Shannon
6. Two conference attendees discussed their _____, a program for proving theorems from Principia Mathematica.
Logic Theorist
7. The following year they introduced their GPS or _____, a generalized state space search mechanism.
General Problem Solver
8. At Stanford Research Institute this was transformed into _____, a robot planning program used in Shakey.
STRIPS
9. After the initial successes of A.I. came the period known as the _____ when funding for A.I. research was hard to come by.
A.I. Winter
Theoretical basis & issues:
10. A.I. has historically been at the center of computing theory. The _____, a theoretical machine described by Alan Turing, is widely held as the theoretical model of computation.
Turing Machine
11. After two other models of computation were shown to be logically equivalent the _____ proposed that whatever is computable is computable by these.
Church-Turing Thesis
12. One of these models, the _____, is found in the logical framework of forward chaining expert systems.
Post production system
13-14. The other, the _____, proposed by Alonzo Church formed the basis of the programming language _____.
lambda calculus
Lisp
Theoretical issues – again:
57-58. Brachman and Levesque showed that in the design of A.I. systems there is a fundamental tradeoff between _____ and _____.
expressiveness
tractability
59. _____ is the process of complex pattern formation from more basic constituent parts or behaviors.
emergence
60. Boids, developed by Craig Reynolds in 1986, is an artificial life program, simulating the _____.
flocking behavior or birds
61-63. The behavior-based (BB) paradigm in A.I. (and especially in robotics) was proposed because reactive systems were found to be too _____, deliberative systems too _____, and hybrid systems required _____ among components.
inflexible
slow and cumbersome
complex interactions
64. The BB paradigm was inspired by biological systems which achieve complexity with _____ components.
simple and consistent
Robot control architectures:
65-68. In robotics a control architecture provides guiding principles and constraints for organizing a robot’s control system. List the four main control architectures.
deliberative
reactive
hybrid
behavior-based
69. _____ is the scientific study of animal behaviors.
ethology
70-71. Two of the pioneers in this field are:
Lorenz, Tinbergen
72-73. And two of the pioneers in applying biological studies of animal behavior to robotics are:
Moravec, Arbib
74. _____ is a specific stimulus which triggers a stereotypical pattern of action.
an innate releasing mechanism
75-76. Perception serves two functions with respect to action. It serves to _____ and then to ____ by providing information necessary to accomplish it.
release the behavior
guide the behavior
77. A _____ is a generic template for doing some activity.
schema
78. It consists of _____ to act and/or perceive . .
knowledge of how
79. and of the _____ for accomplishing the activity.
computational process
80. The subsumption architecture of Rodney Brooks solves the _____ by eliminating the need to model the world.
frame problem
81. Within this architecture behaviors are arranged in _____.
layers of competence
Enhanced True/False
(82-94) For each statement, indicate whether it is true or false. Correct those that are false to make them true.
92. When using depth-limited search, the first solution encountered is guaranteed to be optimal.
False: There may be a better solution on a branch yet to be explored.
93. Depth limited search has an inefficiency in that on each iteration the search space covered on the previous iteration is covered again.
False: Iterative deepening
Short Answer Questions
State space search:
95. Describe the Manhattan distance heuristic for the 8 Puzzle.
h(x) = number of moves each tile must make to reach its proper place
96-97. In A* search all active nodes are kept in a ordered list that is ordered by a function known as f(x). How is f(x) computed? How are the components of f(x) computed?
f(x) = g(x) + h(x)
g(x) is the cost of the path to this point
h(x) is the value given by the heuristic function
98. A key requirement of A* is that the heuristic function be admissible. When is a heuristic function admissible?
When it never overestimates the cost of reaching the goal
99. We found that the Manhattan heuristic dominates the OOP heuristic. What does that mean?
For all configurations, c, Manh(c) ( OOP(c).
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- title for literacy narrative
- title ix of the education amendments act of 1972
- how to title an essay
- title ix of education act
- title ix of the education amendments
- loan forgiveness for title 1 teachers
- title 9 of education amendments of 1972
- car title loans guaranteed approval
- how to type a book title correctly
- loan forgiveness title 1 school
- title loans near me
- global lending services title dept