lecture notes | calendar
| projects | AI
links | discussion
board
CSE 250A is a graduate course devoted to the basic concepts and algorithms of modern artificial intelligence (AI) research. 250A is part of a two quarter sequence with 250B, which will be offered in Spring 2001. 250A will mainly cover search and reasoning methods, while 250B will focus on learning methods. Both courses will cover theory and applications, with a special focus on Internet applications. Some guest lecturers from universities and research labs are expected.
The specific AI topics that will be covered in CSE 250A are:
The course will be based on an excellent textbook and on recent technical articles. Other readings and references will also be used, which will be distributed as the quarter progresses. Lecture notes will be published on the web.
The instructor is Charles
Elkan, Associate Professor. Office hours will be on Mondays
and Wednesdays, in AP&M room 4856, times to be announced. If
you are unable to attend office hours, feel free to send email
to arrange an appointment, or telephone (858) 534-8897.
Seniors in CSE, mathematics, and cognitive science with excellent records are welcome. The only prerequisite for 250A is CSE 100 (upper-division data structures) or an equivalent course. Undergraduates who are interested in 250A should contact the instructor at elkan@cs.ucsd.edu. For undergraduates, CSE 250A and 250B will count as technical electives and as replacements for CSE 150 and 151.
For registration, the Winter 2001 section id of CSE 250A is 392713.
| date | topic |
| January 8 | General state-space search algorithm, BFS, DFS, offline versus online search |
| January 10 | Analysis of BFS and DFS, iterative deepening, greedy search, A* algorithm |
| January 15 | Martin Luther King day-no lecture |
| January 17 | Proof of A* optimality, etc., how to invent heuristic functions, CSPs |
| January 19 | DFS for CSPs, backtracking, forward checking, arc consistency |
| January 24 | AC-3 method, heuristics for variable and value ordering |
| January 29 | Combining CSP heuristics, DPLL algorithm for clause satisfiability, local search |
| January 31 | GSAT stochastic search algorithm, simulated annealing, Walksat |
| February 5 | Project report comments, setting stochastic search parameters, metaphorical algorithms |
| February 9 | Knowledge-based systems, first-order logic, quantifiers, predicates, function-symbols |
| February 12 | Equality predicate, unique names assumption, semantics of first-order logic |
| February 14 | Axiomatizing knowledge, Peano axioms, unintended models, actions and fluents |
| February 19 | President's day-no lecture |
| February 21 | Second project comments, situation calculus, type errors in FOL, Yale shooting world |
| February 23 | The frame problem, axiomatizing causation, link with analytic philosophy |
| February 26 | Planning, proof by refutation, resolution, conversion to CNF |
| March 5 | Skolemization, unification, resolution control strategies (unit, input) |
| March 7 | Semi-decidability, set-of-support resolution. Conditional probabilities. |
| March 12 | Independence, Bayes' rule, reasoning with counts, Bayesian networks |
| March 14 | Inference algorithm for polytrees, explaining away, learning for simple networks |
| March 19 |
Fourth project report due
|
| March 23 | Final examination in Center Hall, room 222, 11:30am to 2:30pm |
Quite a few of the topics discussed in class will not be in either textbook, 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 sections of the textbook and to study them. Examinations will be based mainly on the online lecture notes, but may ask questions that involve knowledge in the textbook.
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, but no midterm.
The final exam will be in APM 4882, like the lectures, on Friday March
23 from 11:30am to 2:30pm. Here are three
sample
examination questions and here is the actual final
examination from Winter 2000, slightly revised; these documents are
in postscript. Here is the 2001
final exam.
| topic | date assigned | date due | sample project report from Winter 2000 |
| heuristic online web searching | January 10 | January 29 | Effective Heuristics for Domain-Specific Online Web Searching by John Bellardo, Bob Boyer, and Greg Hamerly |
| improved satisfiability testing | January 29 | February 16 | Improved Noise Tolerance for WalkSat by Chris Harris and Nadya Williams |
| reviewing research papers | February 9 | February 26 | |
| knowledge representation | February 26 | March 19 |
Here is a New York Times article about specialized web search engines similar to those in the first project.
The third project involves writing reviews of published papers. Note that it overlaps by one week with the second project.
Students will work in teams of two or three for each project, which will be graded based on a written report using this score sheet. One person from each team should place the team's complete project report in the instructor's mailbox in AP&M room 3132 before 4:30pm on the day that the report is due. Each day that a report is late will cost 10% of the maximum score available for the project.
Detailed guidelines for all projects are here. Also learn from these comments concerning the reports submitted for the first project, and these comments for the second project.
See also this collection of links to advice
on research and writing.
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 250A just because you are unhappy with the score
that you receive on a project. Instead, you should make an appointment
to discuss with the instructor how you can do better on following projects.
Most recently updated on May 2, 2001 by Charles Elkan, elkan@cs.ucsd.edu