assignments
due Tue Sep 6
Getting Started
- If you're exploring lisp, install clisp, and start looking at it.
- Get a copy of the textbook, AIMA, and read the first chapter. Start reading the second chapter.
- Look through the ai-class.com site, and their schedule. Compare with chapters in the text.
- Do these exercises:
- As a programming warmup, write a program that asks for a number N and then finds the sum of all even fibonacci numbers less than N.
- Discuss the last Loebner prize winner, what they did and so what.
- Discuss the "Surely * cannot be intelligent" questions at the end of chapter 1.
due Fri Sep 16
Searching
- Continue practicing Lisp
- If you haven't yet, install and play around with the AIMA code in lisp or python for the vacuum world.
- Read chapter 3. Come to class ready to explain and discuss.
- Do something along the lines of problem 20, 3rd edition (19 in the 2nd edition), asking you to write an agent for the vacuum world. In addition to answering their questions, use this as a way to explore the concepts in the first three chapters. Discuss your approaches, and how they fit into the author's conceptual framework. (This is pretty open ended - use it to explore these ideas as time allows.)
due Tue Sep 20
More Search
- A heavy reading weekend: finish at least a first pass through all the search chapters, i.e. part II of the text. We'll do adverserial alpha-beta, genetic, and all that next week.
- One programming assignment, to implement the depth-first-using-a-stack vs breadth-first-using-a-queue that I discussed in our last class. If you've had algorithms before, then this is review and you should certainly do it in lisp. If you haven't had algorithms before, use whatever language you like, and ask if you need hints. You can use any tree to search you like (it's the method of tree traversal that we're after here), but if you aren't sure and have time to implement something fun, I suggest this one:
Consider a puzzle like the TopSpin one described
at http://www.jaapsch.net/puzzles/topspin.htm
but having 8 numbers, not 20. That is, you
have a list of the numbers 1 to 8 in a
randomized order, such as
[3,1,4,5,7,6,2,8].
You have three possible moves:
1) flip the first four numbers to get [5,4,1,3,7,6,2,8]
2) rotate them to the right to get [8,3,1,4,5,7,6,2], or
3) rotate them left to get [1,4,5,7,6,2,8,3].
The goal is to put them into the order 1 through 8.
To reach the goal, search the tree of possible moves.
(From each node of the tree except the root, one
move goes backward, and two of these three moves
move down the tree.) Got it? Good; we'll discuss Tues.
due Tue Sep 27
Last Bit of Search
- Finish reading through the end of part II.
- Come to class ready to discuss alpha/beta, min/max, and genetic search.
- Pick one more coding / search project, of your choice. One type of search, one type of problem. Choose something that matches your level of experience, and be ready to present to other folks next week.
- Do the following exercises :
due Thu Oct 6
Propositional Logic
- read chapter 7 (skip 7.6)
- read wikipedia:propositional calculus
- Explain what all this logic formalism has to do with the wumpus world.
- define the following terms; give an example if appropriate
- propositional logic (read ahead or lookup "first-order logic", for comparison)
- inference
- resolution
- de Morgan's laws
- CNF (conjuctive normal form) and Horn form
- KB
- Convert the assertion (A -> B and B -> C) into CNF. Use the resolution procudure to show that A -> C is a valid inference.
- Explain the wumpus agent algorithm described in the text in chap 7. In particular,
- What information (and how much) does it start with?
- what are the (input, output, side-effects) for the routines TELL(), ASK() ?
- Do (7.8 from AIMA 2nd pg 237) ; (7.10 from AIMA 3rd pg 281) :
Decide whether each of the following sentences is valid, unsatisfiable, or neither.
Verify your decisions using truth tables or logical equivalence rules.
(Symbols here mean (| or) (& and) (=> implies) (~ not).)
a. Smoke => Smoke
b. Smoke => Fire
c. (Smoke => Fire) => (~ Smoke => ~ Fire)
d. Smoke | Fire | ~Fire
e. ((Smoke & Heat) => Fire) <=> ((Smoke => Fire) | (Heat => Fire))
f. (Smoke => Fire) => ((Smoke & Heat) => Fire)
g. Big | Dumb | (Big => Dumb)
h. (Big & Dumb) | ~ Dumb
- Do (7.11 from AIMA 2nd pg 238) ; (7.22 from AIMA 3rd pg 284) , on minesweeper
due Thu Oct 13
First Order Logic
- Read chapter 8.
- Look into SNARK :
- Start in on chapter 9, inference in FOL
- Do 8.10 from AIMA 3rd, which is :
Consider a vocabulary with the following symbols:
Occupation(p, o): Predicate. Person p has occupation o.
Customer (p1, p2): Predicate. Person p1 is a customer of person p2.
Boss(p1, p2): Predicate. Person p1 is a boss of person p2.
Doctor, Surgeon, Lawyer, Actor: Constants denoting occupations.
Emily, Joe: Constants denoting people.
Use these symbols to write the following assertions in first-order logic:
a. Emily is either a surgeon or a lawyer.
b. Joe is an actor, but he also holds another job.
c. All surgeons are doctors.
d. Joe does not have a lawyer (i.e., is not a customer of any lawyer).
e. Emily has a boss who is a lawyer.
f. There exists a lawyer all of whose customers are doctors.
g. Every surgeon has a lawyer.
- Do 8.18 in AIMA 3rd, namely:
Write out the axioms required for reasoning about the wumpus’s
location, using a constant symbol Wumpus and a binary predicate
At(Wumpus, Location). Remember that there is only one wumpus.
- Pick one of the Lewis Carroll puzzles on http://www.math.hawaii.edu/~hile/math100/logice.htm. Represent it in either propositional logic or first order logic (and explain why you chose that one), and find the conclusion.
- Optional (but may well be assigned next week): 8.14 in AIMA 3rd :
Write axioms describing the predicates Grandchild, Greatgrandparent,
Ancestor, Brother, Sister, Daughter, Son, FirstCousin, BrotherInLaw,
SisterInLaw, Aunt, and Uncle. Find out the proper definition of mth
cousin n times removed, and write the definition in first-order logic. Now
write down the basic facts depicted in the family tree. Using
a suitable logical reasoning system (i.e. snark) TELL it all the sentences you
have written down, and ASK it who are Elizabeth’s grandchildren,
brothers-in-law, Zara’s great-grandparents, and Eugenie’s ancestors.
due Tue Oct 25
mid term coding project
- This one's for a grade.
- Complete a coding project including docs and examples in either Lisp or Python related to the material we've been studying so far.
- For most of you, I expect a more polished version of the search projects you began earlier this term.
- If you'd like to do something new (something I haven't seen you working on yet), please do email me to confirm that your topic and project scale is OK.
due Tue Nov 1
Learning part 1
- start reading chapters 13, 18, 20
- i.e Bayesian Probablity, learning, neural networks, etc
- Do the following three problems from AIMA 3rd:
- 13.13, a conditional probability disease testing question.
- 13.21, on green and blue taxis.
- 13.22, on text categorization. (This one heading towards the material in chapter 20.) Be as algorithmically specific as you can.
due Tue Nov 8
Naive Bayes
- Your mission this week is to show that you understand text classification as described in class, the text, or unit 5 "Machine Learning" of the ai-class.com online video lectures.
- Choice 1 is to implement a text classification scheme. Choose a language, some text, what the categories are, and write some code. You can use any of the methods we've discussed, just be clear about which one you choose.
- Choice 2 is to do problems 1 and 2 in the ai-class.com homework 3, and to write code that automates the answer to those two questions given their data.
- In either case, explain exactly what's going on.
due Tue Nov 15
Term Project Proposal & Neural Nets
- As discussed in class this week, choose a term project and start looking into it.
- class presentations near Thu Dec 1
- Your choice of
- a machine learning project (i.e. neural net, decision tree, ...)
- an agent that uses first order logic
- an AI related topic we haven't covered in any depth (e.g. data mining); confirm with me first
- something else closely related to topics we've been considering - please check with me first
- This should be *different* than your 1st project.
- Should include a description of the method, some type of problem to solve, and some code or configuration of your devising. (You may use a system or library or application from another source, such as a neural net simulator, but if so you should be creating some technical piece within that system.)
- Do two problems from AIMA 3rd in chap 18: 6 (decision trees) and 19 (xor neural net by hand).
- Investigate a neural net software package; several are listed in the Nov 8 notes.
- Explore one of its tutorials or demos, and come to class ready to explain it.
- You can do something python code I showed in class on Nov 10; if so, simplify the problem and/or look closely at what's going on and what is or isn't working.
due Tue Nov 22
image processing
- Implement several of the image processing techniques we discussed in class, including at least
- gaussian smoothing
- edge detection via (0, 1, 0, -1, 0) -ish convolutions in 2D
- Your code should read and write actual images, to see the effects.
- One simple library to do this is Zelle's graphics.py that can read and write .gif files, and get/set pixels. Or you can use whatever graphics package you like.
- Come to class ready to show your work.
due Fri Dec 9
final project
- submit code, docs, and write-up for final project
term grade
- a place for Jim to give comments and grade