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

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:

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: Friday, September 2

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:

Class 3: Tuesday, 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 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: Friday, September 9

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

Required reading:

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:

Class 6: Friday, September 16

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:

Class 7: Tuesday, September 20

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:

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

Class 8: Friday, September 23

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.

Note that the textbook commentary on computer Go has been superseded by striking developments over the last two years. Google's DeepMind unit (originally a separate company based in London) has created a program called AlphaGo that has beaten the leading human player. For details, see the technical article published in Nature, and the AlphaGo website.

Sample exam questions:

Class 9: Tuesday, September 27

Required reading: 5.5-5.7.

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

Sample exam questions:

Class 10: Friday, September 30

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: Tuesday, October 4

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. Also on Moodle is a file containing a few key figures from the textbook, called other-search-techniques-figs.pdf (it's on Moodle for copyright reasons--feel free to download it for personal use).

Sample exam questions:

Class 12: Friday, October 7

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:

  1. 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.
  2. 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.
  3. 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: Tuesday, October 11

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: Friday, October 14

Exam 1

Class 15: Friday, October 21

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:

Class 16: Tuesday, October 25

Required reading: 7.5.2 (again).

Lecture notes on resolution are available.

Sample exam questions: see previous class.

Class 17: Friday, October 28

Required reading: 8.1-8.5.

Lecture notes on first order logic are available.

Sample exam questions:

(optional) Demo of first-order logic being used in a real system: the programming language Prolog. The example file course-inference.pl is available if you are interested.

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 18: Tuesday, November 1

Required reading: 9.1, 9.2.1.

Lecture notes on inference in first order logic are available.

Sample exam questions:

Classes 19 and 20

Paper presentations.

Class 21: Friday, November 11

Required reading:

Lecture notes on nearest neighbors and decision trees are available.

Sample exam questions for nearest neighbors and decision trees.

Please start thinking about the final project now. The first milestone is due in less than two weeks.

Class 22: Tuesday, November 15

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: Friday, November 18

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.

And check out the incredibly useful interactive demo at http://playground.tensorflow.org.

Class 24: Tuesday, November 22

Required reading:

There is an excellent Wikipedia page on the Chinese Room.

Class 25: Tuesday, November 29

Exam revision. Please bring to class examples of questions that you would like to go over in class.

Class 26: Friday, December 2

Exam 2.

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

Class 27: Tuesday, December 6

This discussion class will take place at the instructor's house, 1:45-2:45pm. I look forward to seeing you there! Some light refreshments will be served.

Readings will be posted soon -- check back here for some links to contemporary ethical issues in AI. If you have particular areas that you would like to cover, please let me know by 5 PM Wednesday, November 30. Likely areas for discussion include driverless cars, robotic warfare, and the ethics of machine learning algorithms. (But we can't do all of those, so let me know what you are interested in.)

Optional reading/viewing/thinking for the discussion:

Class 28: Friday, December 9

Lab day for working on final project.