CSE 150 – Introduction to Artificial Intelligence
Week 6 – Discussion Notes
November 3, 2004
MIDTERM REVIEW

Outline:
1.) Format, Resources, and Other Info
2.) Review of Topics
3.) Answers to Your Questions
1.) Format, Resources, and Other Info

The two major topics we have covered are Search Algorithms (Uninformed, Informed, Constraint Satisfaction Problems (CSP) and Probability (conditional probability, Bayes Rule, Naive Bayes assumption). 

The format of the test will be similar to the midterm from the last time the course was offered. A copy of last  year's midterm can be found at http://www.cse.ucsd.edu/~elkan/150/midterm.pdf
Solutions can be found at http://www-cse.ucsd.edu/users/elkan/150winter04/midsoln.pdf

I have also handed out Question 2: Parts 17-25 from last year final. These questions relate to Probability. Similar questions will be a major component of the midterm. A soft copy of these questions will NOT be made available.  Email me to arrange a time to pick up a hard copy or make arrangements to copy another's student handout.

Note that Question 2: Parts 9-15 from the sample midterm relate to first-order logic. We have not covered first-order logic yet, so this material will NOT be on this year's midterm.

The best way to study is to try the exercises on your own before coming to discussion.  Learning what you do not know before you sit down to study is the most effective and efficient way to prepare.

2.) Review of Topic

The two main topics covered thus far are Search Algorithms and Probability.

Search Algorithms.
- Uninformed Search Algorithms (Chapter 3) - BFS, DFS
- Informed Search Algorithms (Chapter 4) - A*
- Constraint Satisfaction Problems (Chapter 5) - DPLL, Walksat

Things to know:
    1) Pseudocode of the alogorithm - Intuition on how algorithms run
    2) Taxonomy - how the various algorithms relate
    3) Theoretical Properties
        - properties of algorithms - completness, optimality, and exhastive
        - time and space complexity - in terms of branch factor (b), depth of solution(d), etc - See figrue 3.17

Probability:
    - probability concepts - events, random variables
    - probability definitions and assumptions
        - Conditional Proability definition - Pr(A|B) = P(A and B) / P(B)
        - Independence - Events A and B are independent iff P(A and B) = Pr(A) * P(B), or similarly P(A|B) = Pr(A)
        - Bayes Rule - P(A|B) = P(B|A)P(A) / P(B)
        - Naive Bayes Assumptions - "A and B are conditionally independent given C" iff P(A|B,C) = P(A|C)
             - Note that this does NOT imply general independence P(A|B) = P(A) or P(A|C) = P(A).
3.) Answers to Your Questions

In discussion, we answered questions from last years midterm and final (see above).  If you have any additional questions, please post them on the discussion board or come to office hours.


(c) This page was prepared for CSE 150 by Douglas Turnbull (dturnbul@cs.ucsd.edu) on November 3rd 2004.