Instructor: Max Welling

to present papers and progress on their project.

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-4 Solutions-partA; HW4-solutions-partB]**

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];

Harder paper on CG solving

** **

Reading-book: Chapter 26

Reading-paper: This paper on Cryptogram solvers

Exercises:

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)

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)

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
Reading-paper:Exercises: HW Ch. 6 [doc] [pdf]**

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

**Week 8:
Reading-book: Chapter 8
Reading-paper:
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 MindExercises: HW Ch. 9 page 315-318: 9.3; 9.4; 9.9; 9.10a; 9.18; 9.19 **

a solver that decodes a piece of text that is scambled. For instance, can you read this:?

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.

Some useful links:

-http://www.ics.uci.edu/~eppstein/cryptogram/algo.html

(A solver by David Eppstein from ICS!)

-http://www.gtoal.com/wordgames/cryptograms.html

(general page on Cryptogram solvers)

-http://www.blisstonia.com/software/WebDecrypto/index.php

(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

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

*Planning*

*Reinforcement Learning*

*AI: Present and Future* (Ch 27)

**Final: Wed. Dec 9, 4-6 pm**