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. E3 = exam 3. PP2 = paper presentation, milestone 2. FP1 = final project, milestone 1.

Class 1: Tuesday, August 28

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, August 30

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 tablet) 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. Another one we can try: cleverbot.

Sample exam 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: Tuesday, September 4

Required reading: 3.1-3.4

Stuart Russell's lecture notes: slides, handouts. Warning: these slides correspond to an earlier edition of the textbook, so there are some inconsistencies with the latest edition (e.g. fringe versus frontier, successor-function versus actions).

Ungraded homework: read the instructions and code for programming assignment 1, and bring any questions about the code to the next class.

Sample exam 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 own 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 6

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.

Table showing advantages and disadvantages of uninformed search algorithms.

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 exam 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: Tuesday, September 11

Cancelled due to ill health.

Class 6: Thursday, September 13

Cancelled due to ill health.

Class 7: Tuesday, September 18

Required reading: 3.6

Lecture notes for class 7.

For interest only: presentation by Andrew Goldberg describing some algorithms behind Bing maps route planning, and the 2010 publication containing the rigorous results behind this work.

Sample exam questions: 3.14, 3.27, "Prove that a consistent heuristic is also admissible," "State the optimality properties of A* search for consistent, admissible, and inadmissible heuristics."

Class 8: Thursday, September 20

Exam 1.

Class 9: Tuesday, September 25

Required reading: 5.1-5.2

Stuart Russell's lecture notes: slides, handouts.

Sample exam 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 10: Thursday, September 27

Required reading: 5.3

Stuart Russell's lecture notes (same link as previous class): slides, handouts.

My own lecture notes on alpha-beta pruning.

Today's handout on alpha-beta pruning.

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 skimming the math and enjoying the commentary sections. See the lecture notes for a few more pointers.

Sample exam questions:

Be able to fill in the alpha and beta values on a game tree, as in the lecture notes above.
5.9, 5.10a, 5.10d (it is fine to make a few additional assumptions for this question)

You now have (nearly) all the background you need for programming assignment 2!

Class 11: Tuesday, October 2

Required reading: 5.4.0-5.4.2, 5.5, 5.7

Stuart Russell's lecture notes are again relevant (same link as previous class): slides, handouts.

The instructor's lecture notes on search cutoff and stochastic games are available.

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 exam questions:

5.16, 5.19

Class 12: Thursday, October 4

Required reading: 4.1.0, 4.1.1, 4.1.4, 4.3.0-2, 4.4.0-1

Stuart Russell's lecture notes: slides, handouts.

Links demonstrating some of the algorithms discussed:

A "biological" demonstration of a genetic algorithm
Traveling salesman problem using a genetic algorithm

Handout on non-classical search. And my lecture notes.

Sample exam questions:

Be able to give a brief description (a few sentences) of each of the following algorithms: hill-climbing, genetic algorithm.
Be able to specify the solution of an AND-OR tree, such as figure 4.10.
4.10, and the exercises in the link to the handout above

Class 13: Tuesday, October 9

Required reading: none.

Sample exam questions:

From the opening 45 minutes of Spielberg's movie AI: Artificial Intelligence, give: (a) two examples of a human showing emotional attachment to David (who is a robot), and (b) two examples 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 11

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 exam 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 18

Exam 2.

Class 16: Tuesday, October 23

Please take the mid-semester survey.

Required reading: 7.5.2 (again).

Lecture notes on resolution are available.

Sample exam questions: see previous class.

Class 17: Thursday, October 25

Required reading: 8.1-8.5.

Lecture notes on first order logic are available.

Results of mid semester survey are available.

Sample exam 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:

Computing access permissions in a filesystem: Joseph Halpern and Vicky Weissman, Using First-Order Logic to Reason about Policies, ACM Transactions on Information and System Security (TISSEC), 11(4) (July 2008).
Validating models of groups of applications: Mike Mannion, Using First-Order Logic for Product Line Model Validation, Lecture Notes in Computer Science (Springer), 2002, Volume 2379, 149-202

Class 18: Tuesday, October 30

This class was canceled due to the storm. The philosophy and ethics discussion originally scheduled for this class will now take place on Tuesday, December 4.

Class 19: Thursday, November 1

Required reading: 9.1, 9.2.1.

Lecture notes on inference in first order logic are available.

Sample exam questions:

9.3, and these additional sample questions.

Classes 20 and 21

Paper presentations.

Class 22: Tuesday, November 13

Announcements.

Required reading:

Chapter 5 of a book by your instructor (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 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.

Lecture notes on nearest neighbors and decision trees are available.

Class 25: Tuesday, November 27

Lecture notes on Bayesian networks are available.

Ungraded homework questions: 13.8, 14.1, 14.6(a)-(d), and the exercises in the lecture notes.

Class 26: Thursday, November 29

The informal presentation on artificial neural networks is available. You can also read the book chapter available on Moodle (MacCormick 2012, Chapter 5) for some additional details.

Class 27: Tuesday, December 4

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?

There is an excellent Wikipedia page on the Chinese Room.

Class 28: Thursday, December 6

Required reading/viewing:

P. W. Singer's 2009 TED talk about robotic warfare. Be prepared to answer the following discussion questions: Who is responsible if a drone kills innocent civilians? Does the US need new laws governing drone strikes and other forms of robotic warfare?
Two New York Times articles about driverless cars:
- Google Cars Drive Themselves, in Traffic, John Markoff, New York Times, October 9, 2010.
- With a Push From Google, California Legalizes Driverless Cars, Claire Miller, 10/01/2012.
Be prepared to answer the following discussion questions: What new laws will need to be passed before completely driver-less cars can drive on regular roads? Could/should Google sell their present prototype for use by regular citizens on regular roads?