Computational Problem Solving

Course manual 2025/2026

Course content

This course provides an introduction to algorithmic thinking and basic problem solving techniques in AI. Special emphasis is put on search algorithms and their implementation in the declarative programming language Prolog. The following topics are covered:

• Basic features of the Prolog programming language, including lists, arithmetic, operators, cuts, and negation-as-failure; as well as a few additional features, such a file handling, dynamic predicates, and collecting answers.
• The concept of programming by means of recursion.
• The way Prolog works, including the concepts of matching and backtracking.
• The state-space representation for modelling a wide range of search problems.
• Search algorithms, including depth-first search, breadth-first search, iterative deepening, heuristic-guided search using A*, and adversarial search using the minimax algorithm and alpha-beta pruning.
• Sorting algorithms, including bubblesort and quicksort.
• Formal analysis of the time and memory requirements of algorithms, including basics of the Big-O notation.

A core skill you will acquire in the first part of this course is how to program in Prolog. This includes secondary skills such as presenting your code in an orderly fashion and explaining your solutions to others. You will also acquire general problem-solving skills, learn to think in a structured manner, and practice to express yourself clearly and precisely.

Study materials

Literature

• U. Endriss. An Introduction to Prolog Programming. Lecture Notes, 1999–2024 (for first half of the course, free to download from Canvas or here)

• I. Bratko. Prolog Programming for Artificial Intelligence, 4th edition, Addison Wesley Publishers, 2012. (for the second half of the course. page references will be given for the 4th edition)

Objectives

• Students will be able to solve non-trivial AI problems by choosing and using suitable algorithms.
• Students will be able to recognize and explain the most important search techniques.
• Students will be able to implement common sorting and search algorithms.
• Students will be able to perform basic programming in Prolog.
• Students will be able to describe the declarative programming paradigm.
• Students will be able to analyze the performance of existing algorithms.

Teaching methods

• Lecture
• Computer lab session/practical training
• Self-study

Lectures
The lectures are the primary source of new information in the course and the key to making most of the course material (notes, slides, exercises and homework). We strongly recommend that you attend all lectures and regular tutorials and attend the extra tutorial if needed.

Lab Sessions
In the lab sessions you will work on assignments in class and discuss them. You will also get practice questions that are similar to what you will be asked in the exam. Lastly, you will have the opportunity to work on the homework with direct access to expert help from your TA. You can also use the lab sessions to ask about any of the material covered in lectures. This is also the time to approach your personal TA in case you have questions regarding your graded homework.

Learning activities

Attendance

Programme's requirements concerning attendance (TER-B Article B-4.10):

• For some course component attendance is obligatory. If attendance is required, this is stated in the course catalogue. The reasons for, and the implementation of, this attendance requirement may vary by course and are included in the course manual. Students who do not meet this attendance requirement cannot complete the course with a passing grade.
  

Additional requirements for this course:

There is no formal requirement or rule about attendance for this course. We strongly recommend that you attend all lectures and all regular tutorials and attend the Q&A on Friday if you need extra help.

Assessment

Summary
Homework (40%) and two written exams (2 x 30%).
The lowest of the homework grades does not count.

An average grade of at least 5.5, both overall and over the two exams alone, is required to pass the course.

Full requirements
To pass the course, besides obtaining a final grade of at least 5.5 (before rounding), you also need to score at least a 5.5 in the exam component alone (again, before rounding). Thus, compensation between the two exams is possible, but compensation between the exams and the homework is not. Should you fail to achieve an average of 5.5 in the exams, you can attempt the resit. If you take the resit, the grade you obtain will replace your grade for the whole exam component (whatever your original exam results may have been). Any missed homework assignment is graded with 0 points. The lowest of the homework grades does not count. There is no resit opportunity for the homework component.

Late submissions
Start submitting your homework long before the deadline! You can upload to CodeGrade as often as you want and only your newest submission will be graded. Submissions up to 24 or 48 hours late will get a 25% or 50% reduction, respectively. Submitting later than 48 hours is never possible.

Inspection of assessed work

Homework feedback will be given via CodeGrade.

Exam viewings will be possible in-person and announced in Canvas.

Assignments

Reading assignments
These will usually be sections from the lecture notes or Bratko’s book. You should have a quick look at the beginning of the week and then read everything more carefully when you did not understand something in the lecture, and once more after you have submitted your weekly homework. For the exam it will be assumed that you have completed all reading assignments.

Assessed homework assignments
These will be assessed and need to be submitted by the deadline indicated (these are called the homework). We publish them at the beginning of the week and you should submit them by Saturday. Part of the homework is automatically graded using CodeGrade. You are allowed to submit as often as you want before the deadline. Only the last/newest submission will count for your grade.

Code of conduct
For the homework, you must submit your own solutions. It is always okay to talk to fellow students about the exercises (indeed, you should do this!), to read books, and to browse the Internet for information on Prolog — but it is not okay to copy-paste even a single line of code from others or to systematically search the Internet (or the literature) for solutions to the exercises. You are expected to be able to fully explain your solutions. This means that it is important to (briefly) explain how the programs you submit work (by using comments). It is critical that you use the exercises to actively practice your skills; otherwise you have no chance of passing the exams. So, use the help available during the lab sessions, but also make sure that you honestly assess your own level of ability every now and then and that you do not rely on others. 

NOTE IF YOU ARE RETAKING THIS COURSE
For the homework, you may use and refer to parts of your own solutions from last year, and use them again, but you must mention this in your homework submission as a comment. Explain clearly that you are retaking the course, and say which parts of the file are reused and what you changed. If you resubmit anything without mentioning this, some or all points for this homework may be deducted. Never submit the exact same file as last year - you will get points deducted. Always use the new template file provided on Canvas and decide for each question whether you want to re-use your old answer.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Honours information

Not applicable.

Additional information

The course will be managed through Canvas.

Language

Lectures and course material are in English, laptocolleges are mostly in Dutch.

You may use both Dutch and English when answering homework and exam questions.

Studieadviseur / Study Advisor

Als er gedurende dit vak bij jou bijzondere of persoonlijke omstandigheden ontstaan die invloed hebben op je vermogen om te studeren, meld dit dan direct bij de studieadviseur.

If during this course there are special or personal circumstances that limit your ability to study, please directly contact the study advisor to ask for help and advice.

Contact information

Coordinator

• Malvin Gattinger

The course is taught by Malvin Gattinger (he/him). The best way to contact him is in-person after the lectures.

The Senior TA for this course is Frank Wildenburg (he/him). You can contact Frank by e-mail at f.c.l.wildenburg@uva.nl.

There are several teaching assistants supporting the course. They run the lab sessions and grade the homework. You can find your own TA here on DataNose and find their contact details on Canvas. The best way to contact your TA is during the laptopcollege.

Your personal TA will grade the homework of everyone in your group and is the first person to contact for all questions regarding the course. Make sure you know who your TA is and introduce yourself to them in the first week of the course.