# CS4804 Midterm Topic List

This is a list of concepts that I’ll expect you to have a good understanding of midway through the course. You don’t need to know the exact details of every concept, but having a rough idea of what each means and connections to other concepts will help you use AI ideas in your future work. For the exam, since you’re free to use the book, your class notes, and my class materials, as well as any properly cited external materials from the Internet or other books, you certainly don’t need to memorize specific details.

### Environments and Agents

- PEAS: performance measure, environment, actuators, sensors
- Single-agent vs. multi-agent
- Stochastic vs. deterministic
- Episodic vs. sequential
- Dynamic vs. static
- Continuous vs. discrete

### Search

- Problem formulations: states, actions, transitions, costs, goals
- Algorithmic framework: frontier, expansion
- Uninformed search algorithms: BFS, DFS, uniform-cost, iterative-deepening
- Informed search: greedy heuristic, A*
- Properties of search algorithms: completeness, optimality, time and space complexity
- Properties of heuristics: admissibility, consistency

### Adversarial search

- minimax search algorithm
- alpha-beta pruning
- Variants of minimax: maximax (or any order of agent goals), expectimax

### Logic

- Knowledge base
- Propositional logic
- concepts: literals, negations, conjunctions, disjunctions, implications
- entailment
- inference rules: modus ponens, resolution
- completeness of inference
- First-order logic
- quantifiers: existential, universal
- predicates

- Horn clauses, definite clauses
- Forward-chaining, backward chaining

### Markov decision processes

- MDP descriptions: states, transition probabilities, rewards
- Bellman utility function
- conversion between different forms of rewards
- value iteration
- policy iteration

### Reinforcement Learning

- Passive vs active learning
- Adaptive dynamic programming
- temporal-difference learning
- Q-learning
- approximate state functions