Detailed schedule and class resources

Class 1: Tuesday, August 30

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

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

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

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

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

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

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

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

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:

In your own words, give one-sentence informal descriptions of quiescence and horizon effect, as they relate to searching game trees with cutoff.

Class 9: Tuesday, September 27

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

Sample exam questions:

• 5.16, 5.19

Class 10: Friday, September 30

Class 11: Tuesday, October 4

Stuart Russell's lecture notes: slides, handouts.

Java code demonstrating some of the algorithms discussed:

• HillClimbing.java
• SimulatedAnnealing.java
• GeneticAlgorithm.java

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:

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

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

Class 14: Friday, October 14

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:

• 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: 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:

• 8.9 a, c, e
• 8.10 a, e, g
• 8.11 c(i)
• 8.23 a, d
• 8.28 e, l

(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:

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

Class 21: Friday, November 11

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.

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

• 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 25: Tuesday, November 29

Class 26: Friday, December 2

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

Class 27: Tuesday, December 6

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:

• A.I. Inspiration: The Science Fiction That Frames Discussion. New York Times article by Matthew Rosenberg and John Markoff. Oct. 25, 2016. Online only.
• The Pentagon's "Terminator Conundrum": Robots That Could Kill on Their Own. New York Times article by Matthew Rosenberg and John Markoff. Oct. 25, 2016. Appears in print on October 26, 2016, on page A1 of the New York edition.
• Think about the following discussion question: Should completely driverless cars (i.e. with no human behind the wheel, even as a backup) be permitted on roads in the USA? If so, what new laws should be passed?
• [With thanks to Vy for this suggestion.] Watch one or more of the following episodes from the British TV show Black Mirror (it is available via Netflix streaming):
  • Series 1 Episode 3: The Entire History of You. (Relevant for human-machine symbiosis.)
  • Series 2 Episode 1: Be Right Back. (Relevant for questions of whether machines can think and generalizations of Turing test.)
• [With thanks to Vy for this suggestion.] Also consider watching some episodes of the HBO show Westworld. (This appears to be available only for paid HBO subscribers.)

Class 28: Friday, December 9