UMBC - CMSC 471 - FALL 2008 - ARTIFICIAL INTELLIGENCE
 Instructor: DON MINER

FINAL EXAM DATE: MONDAY, DECEMBER 8TH

=== GENERAL SUGGESTIONS ===
Look at the lecture slides mainly, as they will be the main source of questions on the
exam.

However, reading the chapters and looking at the suggested reading material will greatly
increase your knowledge of the topic. If you just study the lecture slides, you may miss
some important facts or not be exposed to as many examples.

This final exam is worth 20% of your grade. This weight is equal to five quizzes or
four homework assignments. Take it seriously!


=== TOPICS ===
The following topics may appear on the exam. Specifics on each topic will be provided
in class on the review day. Any short questions will be answered before the exam is given.


AI Philosophy and History
	* Eliza, Deep Blue, etc.
	* Turing Test
	* General Problem Solver

Agents & Environments
	* Sensors and Effectors (definition, examples)
	* Simple agent diagram
	* Agents with Goals
	* Agents with Memory
	* Properties of agents
	* Properties of environments
	* Be familiar with the existence of popular agent architectures

Search
	* Representing problems as search
	* Understanding properties of search spaces (size & branching)
	* Familiarity with classic problems such as 8-puzzle, 8-queens,
	  missionaries and cannibals
	* Evaluation of search strategies (completeness, time & space complexity, optimality)
	* Uninformed search vs. Informed search
	* BFS
	* DFS
	* DFS with Iterative Deepening
	* Definition of heuristic
	* A*
	* Hill-Climbing
	* Simulated Annealing
	* Genetic Algorithms
	* Ant Colony Optimization
	* Particle Swarm Optimization
	* Implementing graphs (adjacency matrix vs. adjacency lists)

Constraint Satisfaction
	* Defining a problem as a CSP
	* Boolean satisfiability problem
	* Coloring problem
	* Minimum Remaining Values heuristic
	* Degree heuristic
	* Least-Constraining Value heuristic
	* Constraint propagation
	* Min-conflicts heuristic

Game Playing
	* Solved and unsolved games
	* Chinook and Deep Blue
	* Definition of a zero-sum game
	* Game trees
	* Minimax
	* Alpha-beta pruning
	* Prisoner's Dilemma
	* Nash Equilibrium
	* Auctions

Logical Inference
	* Converting to CNF
	* Horn clauses
	* Resolution theorem proving
	* Resolution proof trees

Planning
	* Blocks world
	* STRIPS representation
	* STRIPS planning
	* Partial order planning
	* Serializing POPs
	* Drawing POP graphs
	
Machine Learning
	Neural Networks
		* Purpose
		* History (brief)
		* Neuron model in NN
		* Activation function
		* Perceptrons
		* Multi-layer feed-forward neural networks (one hidden layer)
		* Learning neural network weights
		* Advantages and disadvantages of NNs

	Decision Trees
		* DT input, output
		* Classification
		* Properties and structure
		* Learning trees
		* Choosing attributes (know concept, not math)
		* Problems with DTs

	Naive Bayes
		* Naive Bayes input, output
		* Bayes rule
		* Assumptions
		* Understanding of the formula

	K-Nearest Neighbor
		* General concept
		* Picking k
		* Function approximation

	Reinforcement Learning
		* Markov Decision Processes
		* Understand the concepts of policies, rewards, states, actions
		* Exploration vs. Exploitation
		* Basic algorithms
		* TD-Gammon
		
Markov Localization
	* Uses
	* Dead reckoning
	* General concept
	* Advantages & disadvantages