- Reading list
- Students from previous years
- Old exams
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!
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.
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
- 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.
Here are some older exams from 2014–2017 (all in PDF):