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

Class 1: Monday, September 1

Introduction to course and discussion of syllabus. Elementary notions of classical search. Discussion of the missionaries and cannibals problem (see Wikipedia for a definition, if desired, but don't read about how to solve it). 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 2:

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 2.
Complete the two challenges in the code (search for the word "challenge" to find them).

Optional reading, for interest only: A good article on river-crossing problems is "The Jealous Husbands" and "The Missionaries and Cannibals", Ian Pressman and David Singmaster, The Mathematical Gazette, Vol. 73, No. 464 (Jun., 1989), pp. 73-81, http://www.jstor.org/stable/3619658.

Class 2: Thursday, September 4

Required reading: 3.1-3.4

Some elementary notes on terminology for graphs are provided: graph-theory-basics.pdf.

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).

All algorithms from the latest edition, written in pseudocode, in one place: algorithms.pdf.

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 3: Monday, September 8

Required reading: 3.5

Please see this temporary workaround for Tome mac permissions issues, especially for unzipping .zip files.

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 nice animation of A* search in action, created by Prof. Graham Kendall of the University of Nottingham: astar-demo.pptx.

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 4: Thursday, September 11

Required reading: 3.6

Lecture notes for class 4.

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 5: Monday, September 15

Required reading:

Computing machinery and intelligence, A. M. Turing, Mind 59(236), October 1950. 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.

Many news organizations reported a breakthrough in passing the Turing test earlier this year. For example, here's a 6/8/14 report from The Independent, a reputable mainstream British newspaper:

http://www.independent.co.uk/life-style/gadgets-and-tech/computer-becomes-first-to-pass-turing-test-in-artificial-intelligence-milestone-but-academics-warn-of-dangerous-future-9508370.html

However, others are skeptical of the way this "breakthrough" was reported. The following article from techdirt.com takes this skeptical angle:

https://www.techdirt.com/articles/20140609/07284327524/no-computer-did-not-pass-turing-test-first-time-everyone-should-know-better.shtml

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 6: Thursday, September 18

Required reading: 5.1-5.2

Stuart Russell's lecture notes: slides, handouts.

Sidetrack on simultaneous games with mixed strategies (not examinable): Examples include matching pennies and penalty kicks in soccer.

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 7: Monday, September 22

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 8: Thursday, September 25

Required reading: 5.4

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

The instructor's lecture notes on search cutoff 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:

quiescence

horizon effect

Class 9: Monday, September 29

Required reading: 5.5-5.7.

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

Sample exam questions:

5.16, 5.19

Class 10: Thursday, October 2

Lab day. Before class begins, make as much progress as possible on PA2. In class, you can work on this assignment and receive individual help from the instructor.

Class 11: Monday, October 6

Required reading: 4.1, 4.3, 4.4.

Stuart Russell's lecture notes: slides, handouts.

Java code demonstrating some of the algorithms discussed:

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 (including stochastic, first choice, random-restart), 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 12: Thursday, October 9

Required reading: none. In class, we will watch approximately the first 45 minutes of the 2001 Steven Spielberg movie AI: Artificial Intelligence. If you're interested in this, you might want to watch the whole movie on your own time, either before or after today's class. In addition, it might be interesting to read the short story on which this movie is based: Super-Toys Last All Summer Long, by Brian Aldiss. A copy of this story is available on Moodle. This reading is optional, but it's an easy and entertaining 11 pages, so I do recommend it.

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 13: Monday, October 13

Exam revision. Work through as many homework problems as possible, consulting the solutions on Moodle when necessary. Bring any questions to class. Also, a handout with additional revision questions is available on Moodle.

Class 14: Thursday, October 16

Exam 1

Class 15: Thursday, October 23

Please take the mid-semester survey.

Required reading: 7.0-7.5.2; 7.7.0-7.7.1.

The 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 16: Monday, October 27

Required reading: 7.5.2 (again).

Feedback results and action plan.

Lecture notes on resolution are available.

Sample exam questions: see previous class.

Class 17: Thursday, October 30

Required reading: 8.1-8.5.

Lecture notes on first order logic 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

Finally, the order of paper presentations has been determined using http://www.random.org/lists/. Teams 1-4 will present on Thursday, November 6. Teams 5-8 will present on Monday, November 10.

Class 18: Monday, November 3

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 19 and 20

Paper presentations.

Class 21: Thursday, November 13

Required reading:

Chapter 5 of the book "9 Algorithms That Changed the Future" (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.

Sample exam questions for nearest neighbors and decision trees.

The main course page now has a new link to the final project. Please start thinking about this now. The first milestone is due in less than two weeks.

Class 22: Monday, November 17

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 23: Thursday, November 20

Note: Neural networks will not be included in Exam 2, so there are no sample exam questions for this topic.

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 24: Monday, November 24

No class.

Class 25: Monday, December 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?

There is an excellent Wikipedia page on the Chinese Room.

Class 26: Thursday, December 4

Exam 2.

Solutions to sample questions for exam 2 are available on Moodle.

Class 27: Monday, December 8

Required reading/viewing:

P. W. Singer's 2009 TED talk about robotic warfare.
Arkin, Ronald (2009) Ethical Robots in Warfare, IEEE Technology and Society Magazine, Spring, 2009. Available on Moodle.

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?

Optional reading:

The Case Against Robotic Warfare: a response to Arkin. Ryan Tonkens, Journal of Military Ethics, Volume 11, Issue 2, 2012. Available on Moodle.

Class 28: Thursday, December 11

Lab day for working on final project.