CSCI 3344 - Artificial Intelligence

Spring 2008

TR 9:55-11:10am, 228 HAS

Professor: Yu Zhang office: 201H HAS phone: 999-7399 email: yzhang@cs.trinity.edu Office hours: MWF 11:30am-1:30pm or by appointment
Help session hours: W 4:30-6:30pm, 228 HAS
TA: Phillip Coleman Phillip.Coleman@Trinity.edu

Course Pre-requisites

  1. CSCI1320 PAD1, CSCI1321 PAD2 and CSCI1323 Discrete Structures.
  2. Solid programming experience. You are expected to write programs that implement and test various heuristic search algorithms, etc., for which you may use either C, C++, or Java.

Textbook

Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, second edition. Prentice Hall, 2002.

Course URL

http://www.cs.trinity.edu/~yzhang/teaching/spring2008/CSCI3344.

Goals of This Course

Artificial Intelligence is possibly some of the most interesteing, alluring, challenging and stimulating topics in Computer Science today. Intelligent Agents, in particular, have played an important role in intelligent search engines, personalized web-based services, computer games, and e-ecommerce. Over the pase two decades, views about AI have undergone several major changes -- from highly optimistic expectations for simulating all aspects of human intelligence, to a period of set back due to overclaims, to the current more realistic role in embedding the technology in a wide range of "digital personal assistants" and other "intelligent appliances". We shall try to reveal the true capabilities of the technology while understanding its current limitations in our path through the course.

  1. To understand the concepts behind, and potential of, intelligent agents.
  2. To learn search and representation techniques for building intelligent problem-solving programs.
  3. To get exposure to tradition fields of AI.

Email and WWW

We will be using an email list this semester to communicate pertinent messages to everyone in the class. I will put together the list of email addresses in the first two weeks of class. It is the student's responsbility to ensure that they watch for and read any messages throughout the semester. In addition, this web page will continually be updated with the class schedule, resources, and other information.

Late Turn-in Policy

The penalty for late assignments will be -10% per day (determined on a 24-hour basis relative the due-time, which is the start of class), down to a minimum of 50% (you can still get 1/2 credit if you turn it in by the end of the semester).

Assignments, Projects, Quizzes and Presentations

There will be NO exams.
The will be several quizzes which will be given randomly in class.
There will be about 5-6 homework assignments: e.g. search algorithms to analyze, problems to do in logic, etc.
There will be three project assignments. Projects will be done in groups (3 students).

  1. Using Simulated Annealing algorithm to solve N-Queens problem.
  2. Solving Wumpus World problem in JESS.
  3. Developing a rules-based system.
Project 2 requires to use JESS (Java Expert System Shell). Project 1&3 require to use whatever programming language you are comfortable with.
There also will be two presentations for each group. There are four topics from which they can choose:
  1. Bayesian Network (Ch 13, Ch 14).
  2. Neural Network (Ch 20.5)
  3. Game Theory (Ch 17.6)
  4. Genetic Algorithm (Ch 4.3)

Grading

Grades will be determined by the percentage of total points earned during the course of the semester. The total points will be computed according to the following approximate weighting scheme, though it is subject to slight adjustment as appropriate:

Homework Assignment 25%
Project Assignment 15% each
Quiz 15%
Presentation 15%

The cutoff for an `A' will be at most 90%, 80% for a `B', 70% for a `C', and 60% for a `D'. However, these cutoffs might be lowered at the end of the semester to accomodate the actual distribution of grades.

Attendance Policy

Lecture attendance is encouraged, but will not be used for grades. Unavoidable absences are understood, but each student is responsible for any missed material. For excused absences, an opportunity will be provided to make up any graded work that was missed. For unexcused absences, a grade of zero will be assigned for in-class assignment. Missed exams will be rescheduled without penalty for an excused absence, or with a 25% penalty if the absence is not excused. If you are going to be absent when an assignment is due you should try to turn in the assignment early. If that is not possible, be sure to include a request for an extended turn-in time in your e-mail.

To request approval of an absence or late turn-in, send me an e-mail explaining the reason prior to the class or due date. Tell me if you believe it is a university excused absence. If advance notification is not possible (e.g. unexpected illness) send the e-mail within 48 hours of the absence and be sure to explain why you were not able to notify me in advance. For illness, follow-up the e-mail by submitting a note from a doctor or clinic to my office.

Miscellaneous Notes

Do not copy anybody else's homework assignments or source code, or even give the appearance of having shared work. You can talk with each other about problems and solutions unless otherwise specified, but do not turn in syntactically similar work. Cheating will be dealt with according to the university's policies on academic integrity.

If you have a documented disability and will need accomodations in this class, please speak with me privately early in the semester so I may be prepared to meet your needs. If you have not already registered with Disability Services for Students, contact the office at 999-7411. You must be registered with DSS before I can provide accommodations.


Tentative Schedule

The following is a planning schedule. It may be modified as necessary during the course. Students will be expected to have some familiarity with the material in the schedule at the beginning of the lecture.

Week of Topic R&N
1/13 What is AICh 1
1/20 Intelligent Agents Ch 2
1/27 Multi-agent systems .
2/3 Search spaces and strategies Ch 3
2/10 Uniformed Search Algorithms Ch 3
2/17 Informed Search Algorithms Ch 4
2/24 Project 1 Demo .
3/2 Adversarial Search Ch 6
3/9 Propositional Logic Ch 7
3/16 Spring Break .
3/23 First-Order Logic Ch 8
3/30 Project 2 Demo.
4/6 Inference in First-Order Logic Ch 9
4/13 Inference in First-Order Logic Ch 9
4/20 Various-Topic Presentation .
4/27 Project 3 Demo .


Calendar

Details about lectures, homework assignments, exams etc. are added here.

Monday Tuesday Wednesday Thursday Friday






1/17
Motivation.
Go over syllabus.
Read Ch 1 and Appendix A & B.
1/18
1/21
1/22
What is AI?.
1/23
1/24
Quiz 1.
Agent and env.
Rationality.
PEAS description.
Last day for Add/Drop.
1/25
1/28
1/29
Env types.
Agent types.
HW1 Assignment.
1/30
1/31
Quiz 2.
Solving problems by Searching.
Problem solving agents.
Problem formulation.
2/1
2/4
2/5
HW1 is due.
Search strategy.
Basic uninformed searching algorithms.
Breadth-first search.
HW2 Assignment.
Project 1 Assignment.
Project Evaluation Form.
Group Evaluation Form.
2/6
2/7
Uniformed-cost search.
Depth-first search.
BFS vs. DFS.
Depth-limited search.
2/8

Monday Tuesday Wednesday Thursday Friday
2/11
2/12
Iterative deepening search.
Repeated states.
Graph Search.
Quiz 3.
2/13
2/14
HW2 is due.
Informed Search.
Heuristics.
Best-first search.
Greedy search.
A* search.
HW3 Assignment.
2/15
2/18
2/19
Admissible heuristics.
Optimality of A*.
2/20
2/21
Quiz 4.
Local search algorithms.
Hill-climbing search.
Simulated Annealing search.
Local beam search.
Genetic algorithm.
2/22
2/25
2/26
HW3 is due.
Quiz 5.
Adversarial Search.
Minimax.
alpha-beta pruning .
HW4 Assignment.
2/27
2/28
No class.
2/29

Monday Tuesday Wednesday Thursday Friday
3/3
3/4
Quiz 6.
Logic agents.
Knowledge-based agents.
Wumpus world.
Logic in general - models and entailment.
3/5
3/6
Project 1 demo.
Project 2 Assignment.
A simple JESS manual.
3/7
3/10
3/11
No class.
3/12
3/13
HW4 is due.
Propositional (Boolean) logic.
Equivalence, validity, satisfiability.
HW5 Assignment.
3/14
3/17
3/18
Spring Break.
3/19
3/20
Spring Break.
3/21
3/24
3/25
Quiz 7.
Inference rules and theorem proving.
3/26
3/27
First-Order Logic.
3/28
Last day for Withdraw.
3/31
4/1
Wumpus World in FOL.
Quiz 8.
HW5 is due.
HW6 Assignment.
4/2
4/3
Project 2 demo.
Project 3 Assignment.
zoo.rbs.
facult.rbs.
4/4

Monday Tuesday Wednesday Thursday Friday
4/7
4/8
4/9
4/10
HW 6 is due.
4/11
4/14
4/15
No class.
4/16
4/17
No class.
4/18
4/21
4/22
Student Presentation.
4/23
4/24
Student Presentation.
4/25
4/28
4/29
Project 3 demo.
Final due day for all homework assignments.
4/30
5/1
5/2
5/5
5/6
5/7
5/8
5/9


Last updated: Thursday, Apr. 3, 2008 by Yu Zhang.