CSE 150 is an upper-division course devoted to the basic concepts and algorithms of modern artificial intelligence (AI) research. 150 is part of a two quarter sequence with CSE 151, which will be taught in Spring 2004 by Prof. Gary Cottrell. 150 will mainly cover search and reasoning methods, while 151 will focus on learning methods. Both courses will cover theory and applications.
Some specific AI topics that will be covered in CSE 250A are:
Juniors and seniors in CSE, mathematics, and cognitive science are
welcome. The only prerequisite for 150 is CSE 100
(upper-division data structures) or an equivalent course.
Lectures will be on Tuesdays and Thursdays from 2pm to 3:20pm in the
Cognitive Science Building (CSB), room 002 on the lowest level.
Students must also be available for a discussion section between 2pm
and
3pm on Fridays, in Center Hall room 216.
The instructor is Charles
Elkan, Associate Professor. Office hours will be on Mondays
and Wednesdays from 2pm to 3pm, in AP&M room 4856. If you are
unable to attend office hours, feel free to send email to arrange an appointment.
We have three excellent, experienced teaching assistants (TAs):
| name |
office hours
day |
office hours
time |
room |
| Anjum Gupta | Monday |
1:30 to 2:30 |
APM 4859 |
| Thursday |
12:30 to 1:30 |
APM 4859 | |
| Kristin Branson | Tuesday |
3:30 to 4:30 |
APM 4859 |
| Piotr Dollar | Wednesday |
3pm to 4pm |
APM 4859 |
| date |
topics |
assignment
due |
| January 6 |
Planning as search,
priority-queue search, DFS, BFS, depth-limited DFS |
|
| January 8 |
Branching-factor time and space
analysis, A* search algorithm, proof of optimality |
|
| January 13 |
Proof of A* completeness and
efficiency. Online versus offline search, global vs local. |
|
| January 15 |
How to invent A* heuristics.
Constraint satisfaction problems: backtracking, incremental
constraint checking. |
|
| January 20 |
Forward checking, heuristics for
variable ordering and value ordering. DPLL algorithm. |
|
| January 22 |
DPLL method: backtracking, unit propagation, variable selection. Randomized local search. | Assignment 1 |
| January 27 |
GSAT local search algorithm for
the 3SAT problem, simulated annealing, Walksat algorithm. |
|
| January 29 |
Knowledge-based system examples
and weaknesses. Intro to first-order logic (FOL) . |
|
| February 3 |
Equality, functions vs
predicates. Semantics of FOL: universe, interpretation, model,
etc. |
|
| February 5 |
Peano axioms, axiomatizing
states and actions. Syntax, type, and semantic errors. |
|
| February 10 |
Reasoning about action with the
situation calculus, the frame problem, a FOL solution. |
|
| February 12 |
Entails |= notation,
reasoning forwards and backwards in time, planning. Knowledge
representation and philosophy. |
|
| February 17 |
In-class midterm. |
|
| February 19 |
Proves |- notation, Godel's
completeness theorem, proof by refutation, resolution. |
|
| February 24 |
Midterm feedback.
Conversion to clausal normal form (CNF). Skolemization.
Unification. |
|
| February 26 |
Strategies for finding proofs:
unit resolution, input resolution, set-of-support.
(In)completeness of strategies. |
|
| March 2 |
Unconditional and conditional
probabilities, Bayes' rule and its use for diagnosis.
Representing
training and test data. |
Assignment 3 |
| March 4 |
Feature and class random
variables. Bayes' rule for classifying a test example; estimating
P(C=c). |
|
| March 9 |
More on naive Bayes: computing
P(X1= y1 ... Xp=yp), assuming conditional independence, logs,
pseudo-counts |
|
| March 11 |
Bayesian networks: graph
structure, conditional probability tables, "explaining away" phenomenon |
|
| March 15 |
(Monday 8am) |
Assignment 4 |
| March 18 |
(Thursday) Final exam
3pm to 6pm |
| date |
TA |
topics |
| January 9
|
Anjum |
A* search algorithm, heuristic
function h properties. |
| January 16 |
Kristin | A* implementation, 8-puzzle and robot navigation applications. |
| January 23 |
Anjum |
CSP example: map coloring with
backtracking and heuristics. |
| January 30 |
Kristin |
DPLL algorithm: explanation,
detailed example, data structures |
| February 6 |
Kristin |
Examples of how to represent
knowledge using first-order logic |
| February 13 |
Anjum |
The situation calculus: causes, cancels, etc. |
| February 20 |
Kristin |
How to encode stories and
queries using the situation calculus and Otter |
| February 27 |
Anjum |
Using < to solve the
unique-names problem in Otter |
| March 5 |
Kristin |
Learning a spam classifier and
the naive Bayes algorithm |
Quite a few of the topics discussed in class will not be in either
book, or will be explained differently. Coming to lectures and taking
notes carefully is important. As the quarter progresses,
it is your responsibility to locate relevant chapters of the books and
to study them. Use the indexes of the books!
An excellent second reference is Mathematical
Methods in Artificial Intelligence by Edward A. Bender, IEEE
Press, 1995, ISBN 0818672005.
The course will have an open-book final examination on March 18, and
one in-class midterm on February 17. Examinations will be based
mainly on the assignments and the online lecture notes, but may ask
questions that involve knowledge in the books.
There will be four assignments. The examinations will count
for 40% of your overall grade and the assignments for 60%. Complete academic honesty is always
required.
The first three assignments are due in class, i.e. at 2pm. The
penalty for late submission is 20% of the maximum score per day or part
of day late. One day late means after 2pm and before midnight on
the due date, two days late means the next day, and so on.
For all programming assignments, code quality is very
important. This includes useful commenting, clarity and
concision,
modularity and organization, and appropriate error checking. See How To Write Unmaintainable Code
for what not to do. Coding assignments will use Java, C++, and/or
C.
Grading will not be based on arbitrary numerical standards, nor will there be a fixed "curve." There is no a priori correspondence between letter grades and numerical scores on the assignments or on the exam. You can evaluate your performance in the class by comparing your scores with the means and standard deviations, which will be announced. However there is also no fixed correspondence between letter grades and standard deviations above or below the mean. If all students do well in the absolute, then all students will get a good grade.
You should not drop CSE 150 just because you are unhappy with the score that you receive on an assignment or the midterm. Instead, you should make an appointment to discuss with the instructor how you can do better on following assignments.
Here is the first assignment, due
Thursday January 22. Here are detailed submission
instructions, input
format instructions, and test cases
for the robot navigation problem. See these section notes
and this web board summary
for
advice about the assignment.
The second
assignment was due on Friday February 13 in section. The
grading guide and I/O format instructions are here.
The midterm was in class on Tuesday
February 17. Here are review exercises
that you can use to prepare for the final exam also and here are sample
midterm answers.
The third
assignment was due on Tuesday March 2 in class. The extended
deadline for submitting code online was noon on March 3.
Most recently updated on March 12, 2004 by Charles Elkan, elkan@cs.ucsd.edu