# Written examination

The written examination is *Tuesday 2nd May*,
8:30–12:30, in rooms *HB2* and *HB4*, i.e., not in the exam period!
You will not be able to register to the written exam via Studentportalen.
The exam is followed by a *peer review* the same day, 13:30–16:00, in room *HA4*.
This review is *compulsory for all students* who write the exam!

The re-examinations are organised by the central administration as ordinary exams (non-peer-reviewed):

- The re-examination is Thursday 8th June, 14:00–18:00.
- The re-re-examination is Monday 21st August, 8:30–12:30.

Your grade on the written exam *will not* influence the final grade on the course,
it’s only pass/fail that matters!

## Organisation

The written examination will be in the middle of the course instead of at the end. The reason is that you will get more time to focus on the project afterwards.

The main written exam will be **peer reviewed**!
This means that the students will review each other’s exams,
before we teachers do the final correction.
Both the exam and the review will be done anonymously.
It works like this:

- You come to the examination hall in time and find a place.
- You write your exam as usual for 4 hours (8:30–12:30).
- Then we collect all theses, and you go for lunch.
- After lunch we shuffle them and hand them out to you again, so that everyone will get another student’s exam to review.
- We will go through the answers on the blackboard one by one, and you will correct the thesis you have in front of you (13:30–16:00).
- We collect all theses again, and you are free to leave.
- We will check all your corrections, and hopefully finish within a day or two.

Here are the main rules that you should adhere to:

- Come in time. (Or even better, come 10 minutes early)
- No books or cheat-sheets are allowed.
- Don’t use a red pen when writing the exam!
- And of course – turn off your phone.

*Note*: if you have any special needs, please
contact the course responsible a.s.a.p.

## Reading list

Here is a list of concepts you should know, including course book references.

** Note:**
The lecture slides are published in the schedule!

### Agents (chapter 2)

- Rational agents [2.1–2.2]
- agents, environments
- sensors, actuators, percepts
- performance measure
- definition of rationality

- Properties of task environments [2.3]
- PEAS (performance, environment, actuators, sensors)
- fully/partially observable; single-/multi-agent; competetive/cooperative; deterministic/stochastic; episodic/sequential; static/dynamic; discrete/continuous; known/unknown

- Agent structure [2.4]
- simple reflex agents
- model-based reflex agents
- goal-based agents
- utility-based agents

### Classical search (chapter 3)

- What is a search problem? [3.1–3.2]
- states, arcs, start state, and goal test
- how to encode a search problem

- Tree search vs. graph search [3.3]
- generic search algorithm

- Uninformed search [3.4]
- depth-first, breadth-first, uniform cost, iterative deepening, bidirectional search

- Heuristic search [3.5–3.5.2]
- greedy best first, A*

- Heuristics [3.6–3.6.2]
- admissibility, consistency, dominating heuristic, relaxed problem

### Non-classical search (chapter 4)

- Local search [4.1–4.1.3]
- hill-climbing, aka. greedy ascent/descent
- random moves vs. random restarts
- simulated annealing
- local beam search, stochastic beam search

- Nondeterministic search [4.3]
- contingency plan, aka. strategy
- and-or search trees

- Partial observations [4.4]
- belief states
- sensor-less/conformant problems
- partially observable problems

### Adversarial search (chapter 5)

- Games [5.1]
- perfect / imperfect information games
- zero-sum games, utility function
- game trees, ply/plies
- pruning, evaluation function

- Optimal decisions [5.2]
- minimax algorithm
- multiplayer games

- Alpha-beta pruning [5.3]
- alpha-beta algorithm
- move ordering
- transpositions

- Imperfect decisions [5.4–5.4.2]
- H-minimax algorithm
- evaluation function, cutoff test
- features, weighted linear function
- quiescence search, horizon effect

- Stochastic games [5.5]
- chance nodes, expected value
- expecti-minimax algorithm

### Constraint satisfaction (chapter 6)

Note that in some 3rd editions of Russell & Norvig, the CSP chapter is 7, not 6. But apart from that there shouldn’t be any difference.

- CSP definition [6.1]
- variables, domains, constraints
- unary, binary, n-ary constraints
- constraint graph, constraint hypergraph

- Constraint propagation / Consistency [6.2]
- node consistency
- arc consistency – the AC3 algorithm
- path consistency,
*k*consistency - consistency for global constraints (
*Alldiff*and*Atmost*)

- Backtracking search [6.3–6.3.2]
- minimum remaining values heuristic (MRV)
- degree heuristic (aka. least constrained value)
- least constraining value heuristic
- forward checking
- maintaining arc consistency (MAC)

- Local search for CSP [6.4]
- min-conflicts algorithm
- tabu search, constraint weighting

- Problem structure [6.5]
- independent subproblems, connected components
- tree-structured CSP, directed arc consistency, topological sort
- reducing to tree-structured CSPs, cycle cutset

## Students from previous years

If you took this course in 2014-2016 (i.e., course codes TIN172/TIN173/DIT410), and only have the written exam left to do, then you can write the exam together with this year’s course.

You can take any of the exams, but if you want to write the exam 2nd May, you have to contact the course responsible in advance!

** Note**:
The content has changed a bit.
This year the course will not have anything about probability and Bayesian reasoning.
Instead we have added more about non-classical and adversarial search,
see the reading list above.

## Old exams

Here are some older exams from 2014–2017 (all in PDF):