Detailed schedule and class resources
Notation (applies to the summary schedule also): Any section number
(e.g. 3.5) refers to the textbook, Russell and Norvig. PA1 =
Programming assignment 1. Q3 = quiz 3. PP2 = paper presentation,
milestone 2. FP1 = final project, milestone 1.
Class 1: Monday, August 30
Introduction to course and discussion of syllabus. Elementary
notions of classical search. Discussion of the cannibal problem. SimpleCannibals.java demonstrates
one possible approach -- but note that this code is incomplete (look
at the end of the findSolution() method to see where).
Ungraded homework, due by class 3:
- Read and understand the SimpleCannibals.java code.
- Make a list of all questions you have about this code. The
questions need not be related to artificial intelligence -- it
is crucial that you understand all of the Java used in this
code, so make a note of any Java features that are not clear to
you. We will discuss these questions in class 3.
- Complete the two challenges in the code (search for the word
"challenge" to find them).
Class 2: Thursday, September 2
Required reading:
- Computing machinery and intelligence,
A. M. Turing, Mind 59(236), October 1950 (Available on Moodle). You
must bring with you to class either an electronic copy (e.g. on a
laptop) or a printout of the reading. Be prepared for an
interactive discussion, including answers to the following two
questions: In your opinion, what is the most compelling of
the nine objections listed in Section 6? What is the least
compelling?
- 1.1, 1.2, 1.4
Class will consist of
discussion of the readings.
Here is a link to a chatbot
we can use to try a real live Turing test.
Sample quiz questions:
- Do you
believe the Turing Test is a valid approach for defining whether a machine can think? Justify your answer in a few sentences.
- Select
two of the objections listed in Turing's 1950 paper on AI. For
each objection you select, describe the objection itself in one
sentence, then explain Turing's rebuttal of the objection in
another sentence or two.
Class 3: Monday, September 6
Required reading: 3.1-3.4
Stuart Russell's lecture notes: slides, handouts.
Ungraded homework: read the instructions and code for programming
assignment 1, and bring any questions about the code to the next
class.
Sample quiz questions:
- 3.6a, 3.10, 3.15a, 3.15b
- For each of the uninformed strategies studied
(breadth-first, uniform-cost, depth-first,
iterative deepening), explain a chief advantage or a chief
disadvantage of the strategy compared to one of the other
strategies. (See table on Figure 3.21 in the textbook, and my
solution.)
- For each of the uninformed strategies studied, given the
current state of the algorithm (e.g. the frontier set and the
explored set) be able to specify the next node to be expanded.
For example, given any of the trees in figure 3.16 or 3.19, be
able to specify the next tree in the figure.
Class 4: Thursday, September 9
Required reading: 3.5
Romania map
Simple example in which uniform-cost search needs to replace an
element in the frontier with a lower-cost node.
A very helpful presentation on A* search, by Dr Andrew J. Parkes, University of Nottingham. Note in particular the step by step explanation on slide 9.
Sample quiz question: given a problem and an admissible heuristic
function, be able to explain the order in which nodes are
expanded. (e.g. on the Romania map above.)
Class 5: Monday, September 13
Required reading: 3.6
Announcement: I recommend trying to complete programming
assignment 1 by the due date (Thursday), but because pairings for
this assignment were only officially confirmed today, you can submit
until midnight Sunday without penalty.
Sample quiz questions: 3.14, 3.27, "Prove that a consistent heuristic is also admissible", "State the optimality properties of A* search for consistent, admissible, and inconsistent heuristics."
Class 6: Thursday, September 16
Required reading: 5.1-5.2
Stuart Russell's lecture notes: slides, handouts.
Sample quiz questions:
- define zero-sum game; give a well-known example of a game
that is zero-sum, and a game that is not zero-sum.
- be able to fill in the minimax values on a game tree, such as
the one in figure 5.2
- 5.8, 5.9a-d
Class 7: Monday, September 20
Required reading: 5.3
Stuart Russell's lecture notes (same link as previous class): slides,
handouts.
My own note that will help to understand alpha-beta pruning.
Sample quiz questions:
- Be able to fill in the alpha and beta values on a game tree, such as figure 5.5, and the one in the note linked above.
- 5.10a, 5.10d (it is fine to make a few additional assumptions for this question)
Class 8: Thursday, September 23
Quiz 1.
Class 9: Monday, September 27
Required reading: 5.4
Optional reading: Knuth, D. E., and Moore, R. W., An analysis
of Alpha-Beta pruning, Artificial Intelligence, 6:293-326, 1975
(Available on Moodle). This is a beautifully-written paper, and is
the standard reference for the best-case complexity analysis of
alpha-beta pruning. I recommend checking out the first few pages, up
to and including Section 6.
Sample quiz questions:
Class 10: Thursday, September 30
Required reading: 5.5-5.7
Optional reading: Jonathan Schaeffer et al., Checkers is Solved,
Science, 14 September 2007: Vol. 317. no. 5844, pp. 1518 -
1522. Fulltext PDF available electronically from Dickinson Library.
Sample quiz questions:
Class 11: Monday, October 4
Required reading: 4.1, 4.3.
Links demonstrating some of the algorithms discussed:
Sample quiz questions:
- Be able to give a brief description (a few sentences) of
each of the following
algorithms: hill-climbing, simulated annealing, local beam
search, genetic algorithm.
- 4.1
- Be able to specify the solution of an AND-OR tree, such as
figure 4.10.
Class 12: Thursday, October 7
Required reading: 4.4, 4.5.
Some brief notes and exercises on non-classical search.
Sample quiz questions:
- 4.10, and the exercises in the link to the non-classical search PowerPoint file above
Class 13: Monday, October 11
Required reading: none.
Sample quiz questions:
- From the opening 45 minutes of Spielberg's movie AI:
Artificial Intelligence, give: (a) an example of a human
showing emotional attachment to David (who is a robot), and (b)
an example of a human treating David differently to the way a
human would be treated.
- Suppose that robots such as David in Spielberg's movie AI:
Artificial Intelligence could be built. Do you believe our
society would pass laws preventing cruelty to such robots?
Justify your answer in 3 to 4 sentences.
- Do you believe it is possible, in principle, that
robots such as David in Spielberg's movie AI: Artificial
Intelligence could ever be built? Justify your answer in 3
to 4
sentences, referring to one or more of the important points in
Turing's 1950 paper, Computing Machinery and
Intelligence.
Class 14: Thursday, October 14
Required reading: 7.0-7.5.2; 7.7.0-7.7.1.
The above required reading is important, but the absolute essentials
of propositional logic are covered in Sections 2, 3, and 4 of the
document describing the third programming assignment, available here
as clue.pdf. In class, we will step through
the relevant parts of this document.
Sample quiz questions:
- 7.1; 7.2 (solution must be written in the notation of
propositional logic); 7.4 c, e, g, k; 7.7 a, c; 7.12.
Class 15: Thursday, October 21
Quiz 2.
Class 16: Monday, October 25
Required reading: 8.1-8.5.
Sample quiz questions:
- 8.9 a, c, e
- 8.10 a, e, g
- 8.11 c(i)
- 8.23 a, d
- 8.28 e, l
Examples of realistic applications of first-order logic (taken
from the textbook's bibliography) -- these are for interest only,
feel free to glance at the abstracts, but reading the actual papers
would be excessive:
Class 17: Thursday, October 28
Required reading: 9.1, 9.2, 9.5.
Sample quiz questions:
- 9.4, first example of Section 9.5.3 (i.e. Fig 9.11), and
this additional example question.
- Quiz questions will not require Skolem functions, Skolem
constants, or factoring.
Class 18: Monday, November 1
Required reading:
- Minds,
brains, and programs, John Searle, The Behavioral and Brain
Sciences 3(3) 417-457, 1980. Be prepared to answer
the following discussion questions: which of Turing's (1950)
"objections" most closely resemble Searle's argument? How do you
think Turing would specifically rebut the Chinese room argument?
Who do you side with: Searle or Turing?
- Google
Cars Drive Themselves, in Traffic, John Markoff, New York
Times, October 9, 2010. Be prepared to answer the following
discussion questions: What new laws will need to be passed before
automated cars can drive on regular roads? Could Google sell
their present prototype for use by regular citizens on regular
roads?
- U.N. urged
to set up panel on ethics of robot weapons, Patrick Worsnip,
Reuters, Oct 22, 2010. Discussion questions: Who is responsible
if a drone kills innocent civilians? Does the US need
new laws governing drone strikes?
Sample quiz questions: all of the above discussion questions.
Reminder: request interlibrary loan materials for paper
presentation NOW if you have not already done so.
Class 19: Thursday, November 4
Required reading:
- Chapter 5 of the book your instructor is currently working on
(available on Moodle). This is an easy introduction to some
aspects
of statistical pattern recognition, intended for readers who have
no background in computer science. However, it also serves as a
useful high-level introduction to the machine learning ideas we
will be studying. (Please remember this draft chapter is for your
personal use only; please don't share it with anyone else or make
it available on any public website.)
- Textbook sections 18.1-18.3 and 18.8.1.
Some detailed notes are provided, describing how to choose
which attribute to split when generating a decision tree for a
multi-class problem.
Sample quiz questions.
Class 20: Monday, November 8
Paper presentations by: Katherine, Stephen Pierce, Stephen Wittman,
Michael (in that order).
Class 21: Thursday, November 11
Paper presentations by: Russell, John, Adam, Danni and Ouwen (in
that order).
Class 22: Monday, November 15
Sample quiz questions: 13.8, 14.1, 14.6(a)-(d).
Class 23: Thursday, November 18
Sample quiz questions: See the questions at the end of the Bayesian networks handout.
Note: Neural networks will not be included in Quiz 3, so there
are no sample quiz questions for this topic.
The informal presentation on
artificial neural networks is available.