Written examination
The written examination is Tuesday 13th February, 8:30–12:30, in rooms HB2 and HB3, 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 HB2. 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 Tuesday 5th June, 14:00–18:00.
- The re-re-examination is Friday 24th August, 14:00–18:00.
Note: you have to register for the re-examinations via Studentportalen.
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 well in time.
Note: New for this year is that the written exam is graded (3/4/5 for Chalmers students and G/VG for GU students).
Reading list
Here is a list of concepts you should know, including course book references, and suggestions for exercises.
Note: The lecture slides are published in the schedule.
Note: The exercise numbers and pages below refer to the online course book that is available from Chalmers Library (3rd international edition). Or they refer to the previous written examinations, found below on this page.
Introduction (chapter 1)
You should read this chapter in full, because it’s necessary for the essay. But it won’t be tested in the written examination.
Agents (chapter 2)
- Rational agents [2.1–2.2]
- agents, environments
- sensors, actuators, percepts
- performance measure
- definition of rationality
- Book exercises: 3acgi, 13 (pages 62–64)
- 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
- Exam question: 1 (2014-08-19)
- Book exercise: 4 (page 63)
- Summary [2.5]
Not included: section 2.4
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
- Exam questions: 1 (2014-05-27); 2 (2014-08-19); 1 (2015-06-02); 1 (2016-05-03); 1a (2016-06-01); 1a (2017-05-02); 1a (2017-06-08)
- Book exercises: 2, 3a, 6, 9a, 27ab (pages 114–117)
- Tree search vs. graph search [3.3]
- generic search algorithm
- Book exercises: 10, 11 (page 117)
- Uninformed search [3.4–3.4.5, 3.4.7]
- depth-first, breadth-first, uniform cost, iterative deepening, bidirectional search
- Exam question: 3 (2016-06-01)
- Book exercises: 9bc, 15abe, 16ab, 21ab (pages 117–119)
- Heuristic search [3.5–3.5.2]
- greedy best first, A*
- Exam questions: 3 (2014-05-27); 2 (2016-05-03); 2, 3 (2017-05-02); 2 (2017-06-08)
- Book exercises: 14, 21c, 23, 25, 26 (pages 118–120)
- Heuristics [3.6–3.6.2]
- admissibility, consistency, dominating heuristic, relaxed problem
- Exam questions: 2 (2014-05-27); 3, A (2014-08-19); 2 (2015-06-02); 3 (2016-05-03); 1b (2016-06-01); 1b (2017-05-02); 1a (2017-06-08)
- Book exercises: 3bc, 27cd, 29 (pages 115–121)
- Summary [3.7]
Not included: sections 3.4.6, 3.5.3–3.5.4, 3.6.3–3.6.4
Non-classical search (chapter 4)
- Local search [4.1–4.1.1]
- hill-climbing, aka. greedy ascent/descent
- random moves vs. random restarts
- Book exercises: 2, 4 (page 161); replace “simulated annealing” by “hill climbing” in exercise 2
- Nondeterministic search [4.3–4.3.1]
- contingency plan, aka. strategy
- Book exercise: 12 (page 163)
- Partial observations [4.4–4.4.2]
- belief states
- sensor-less/conformant problems
- partially observable problems
- Book exercise: 10 (page 162)
- Summary [4.6]
Not included: sections 4.1.2–4.1.4, 4.2, 4.3.2–4.3.3, 4.4.3–4.4.4, 4.5
Adversarial search (chapter 5)
- Games [5.1]
- perfect / imperfect information games
- zero-sum games, utility function
- game trees, ply/plies
- pruning, evaluation function
- Book exercises: 2abc, 4, 8ab (pages 198–200)
- Optimal decisions [5.2–5.2.1]
- minimax algorithm
- Exam questions: 2a (2016-06-01); 6a (2017-05-02); 6 (2017-06-08)
- Book exercises: 3abc, 9 (pages 199–201)
- Alpha-beta pruning [5.3]
- alpha-beta algorithm
- move ordering
- transpositions
- Exam questions: 2b (2016-06-01); 6b (2017-05-02)
- 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
- Exam question: 5 (2017-06-08)
- Summary [5.9]
Not included: sections 5.2.2, 5.4.3–5.4.4, 5.6–5.8
Constraint satisfaction (chapter 6 or 7)
Depending on the edition of Russell & Norvig, the CSP chapter is either 6 or 7. Apart from the numbering there shouldn’t be any difference. Below I assume it’s chapter 7, because that’s how it’s numbered in the online version.
- CSP definition [7.1]
- variables, domains, constraints
- unary, binary, n-ary constraints
- constraint graph, constraint hypergraph
- Exam questions: 4 (2014-08-19); 4a (2016-05-03); 4a (2016-06-01); 4a (2017-05-02); 3a (2017-06-08)
- Book exercises: 2abc, 4, 6, 7 (pages 286–288)
- Constraint propagation / Consistency [7.2–7.2.2, 7.2.5–7.2.6]
- node consistency
- arc consistency – the AC3 algorithm
- consistency for global constraints (Alldiff and Atmost)
- Exam questions: C (2014-05-27); 4 (2015-06-02); 4b (2016-05-03); 4b (2016-06-01); 4b (2017-05-02); 3a (2017-06-08)
- Book exercise: 11 (page 288)
- Backtracking search [7.3–7.3.2]
- minimum remaining values heuristic (MRV)
- degree heuristic (aka. least constrained value)
- least constraining value heuristic
- forward checking
- maintaining arc consistency (MAC)
- Exam question: 5 (2017-05-02)
- Book exercises: 5, 9 (pages 287–288)
- Local search for CSP [7.4]
- min-conflicts algorithm
- tabu search, constraint weighting
- Book exercise: 2d (pages 286–287)
- Summary [7.6]
Not included: sections 7.2.3–7.2.4, 7.3.3, 7.5
Previous students
If you took this course in 2014-2017 (i.e., any of the course codes TIN172, TIN173, TIN174, or 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 13th February, you have to contact the course responsible in advance!
Note: The content might be different from when you took the course, see the reading list above.
Old exams
Here are some older exams from 2014–2017 (all in PDF):
-
2018-02-13: (exam, solutions).
- Note: The alternatives to question 1 was wrong, so it could not be solved.
-
2014-05-27: questions 1–4 and C (exam, solutions).
- Update 2018-02-06: The solution to the CSP question (4 Rolling the dice) is wrong! It treats (A<B) and (A+B=5) as different arcs, resulting in a non-arc-consistent graph!