CS 271 Intro AI Fall 2009

Note Board:

CompSci: 271
Instructor: Max Welling

Office hours: Wednedays 1-2pm


The goal of this class is to familiarize you with the basic principles of artificial intelligence.

Class Setup:

The course will primarily be lecture-based (Mondays and Wednesdays) while Fridays will be reserved for the students
to present papers and progress on their project.


Your grade will be based on your project results and class presentations (50%) and your final exam (50%).
Homework is mandataory but will not contribute to your final grade (unless you fail to submit your HW).
It's very important that you try each HW exercise, it's not important that you get it right the first time.

Homework Solutions:

[HW-1 Solutions]

[HW-2 Solutions]

[HW-3 Solutions]

[HW-4 Solutions-partA; HW4-solutions-partB]

[HW-5 Solutions]

[HW-6 Solutions]

[HW-7 Solutions]

[HW-8 Solutions]


Week 1: Ch-2:agents [ppt] [pdf]
Week 2: Ch-3:intro search [ppt] [pdf]
Week 3: Ch-3:uninformed search [ppt] [pdf] ;
Ch-4 infomed search [ppt] [pdf]

Week 4 : Ch-4: Local Search [ppt] [pdf]
Week 5: Ch-5: Constraint Satisfaction [ppt] [pdf]
Week 6: Ch-6: Games [ppt] [pdf]
Week 7: Ch-7: Propositional Logic Part-I: [ppt] [pdf]; Part II: [ppt] [pdf]
Week 8: Ch-8: First Order Logic: [ppt] [pdf];
Week 9: Ch-9: Inference in First Order Logic: [ppt] [pdf];
Week 10: Reinforcement Learning : [ppt] [pdf];

Online Resources:

This paper on Cryptogram solvers

Harder paper on CG solving

Invisible hand algorithm

My own Crypto-EM algorithm that you could implement and test as a project.

Homework : (always due the next Monday at midnight)

Week 1:
Reading-book: Chapter 26
Reading-paper: This paper on Cryptogram solvers

Week 2:
Reading-book: Chapter 1&2
Reading-paper: Read Alan Turing's famous1950 paper
Exercises: Exc. 2.1, 2.2, 2.5, 2.6,(due Monday Oct 5 midnight in EEE dropbox)

Week 3:
Reading-book: Chapter 3
Reading-paper: Introduction Ant Colony Optimization
Exercises: 3.5 (book) + HW-Ch3 [doc] [pdf] (due Monday Oct 12 midnight in EEE dropbox)

Week 4:
Reading-book: Chapter 4
Reading-paper: Game of Life as a Turing Machines
Exercises: HW -Ch4 [doc][pdf] (due Monday Oct 19 midnight in EEE dropbox)

Week 5:
Reading-book: Chapter 5
Reading-paper: CSPs in AI
Exercises: HW Ch5 [doc][pdf] (due Monday Oct. 26 midnight in EEE dropbox)

Week 6:
Reading-book: Chapter 6
Exercises: HW Ch. 6 [doc] [pdf]

Week 7:
Reading-book: Chapter 7
Exercises: HW Ch. 7 [doc] [pdf]

Week 8:
Reading-book: Chapter 8
Exercises: HW Ch.8 page 268-270: 8.3; 8.6; 8.7; 8.8; 8.15. (due Monday Nov. 16 midnight in EEE dropbox)

Week 9:
Reading-book: Chapter 9
Reading-paper: Paper on Godel's Theorem amd the Mind
Exercises: HW Ch. 9 page 315-318: 9.3; 9.4; 9.9; 9.10a; 9.18; 9.19


Your project will consist of implementing a solver for the Cryptograms. A cryptogram is a piece of text where the letters have been permuted. Your task is to come up with
a solver that decodes a piece of text that is scambled. For instance, can you read this:?

L O K U L D C T L U H Z D Q Q C K V U K N S P D Y Q U T T O J R U E D U S S D K N C K V C T C Y T 2 7 1 . C Z C T P D M D O J K D V J J N Q R Y F !

No I presume? So get to work :-)
It is important that you do your research in the same way that you will do research during your PhD:
-If you were inspired by somebody elses work, make sure you reference that that work.
-Write a paper (with abstract, references etc.) in LATEX where you explain your algorithm.
-Perform experiments to analyze your algorithm. How fast is it? How does it compare to other
algorithms? How accurate is it? What are its weaknesses and strengths?
-Try to be original and not just copy things already done in the literature. Even better,
come up with a related problem and design a solver for that:
-e.g.1) a solver that can handle sentences where the space-bar function is also permuted with some other symbol.
-e.g.2) a solver that can handle mapping where two letters are mapped to the same symbol (information gets lost!)
-e.g.3) a solver based on some relatively unknown algorithm such as "ant colony optimization" or something.

You may work in groups of 5 people at most, but you are required to write your own code and report.

Some useful links:
(A solver by David Eppstein from ICS!)
(general page on Cryptogram solvers)
(If you want to found out what I wrote, copy and paste the coded sentence into this solver. I actually made a type....)
-Birkhoff-von Neumann theorem: A doubly stochastic matrix can always be written as a convex combination of
permutation matrices (a doubly stochastic matrix is a matrix with real positive entries where each row and column sum to one).
You could use this useful theorem in designing an algorithm because searching over the space of stochastic matrices is easier
over the space of permutation matrices.
-Another very useful page is the following list of English words with their frequencies of appearing in text.
(can you already think of a rough outline of an algorithm?)
-My Crypto-EM algorithm that you could implement and test

Syllabus: (incomplete)

The following represents a very preliminary syllabus. Expect significant changes.

Introduction: Goals, history (Ch.1)
Agents (Ch.2)
Uninformed Search (Ch.3)
Informed Search (Ch.4 NOT  sec.4.5 and after)
Constraint satisfaction (Ch.5).
Games (Ch.6)
Propositional Logic (Ch.7 NOT "circuit based agents" on page 227 and after)
First Order Logic (Ch.8 NOT sec. 8.4 and after)
Inference in first order logic (Ch.9 NOT including "Completeness of Resolution" and after, p.300)
Uncertainty (Ch.13)
Reinforcement Learning
AI: Present and Future (Ch 27)

Final: Wed. Dec 9, 4-6 pm


Russel & Norvig : Artificial Intelligence; A Modern Approach.