Problem Solving and Search

Studiewijzer 2021/2022

Globale inhoud

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 expressions, 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 the correct use 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. But the course also has the ambition to help you acquire some general problem-solving skills, to get you to think in a structured manner, and to express yourself clearly and precisely.

Studiemateriaal

Literatuur

• I. Bratko. Prolog Programming for Artificial Intelligence, 4th edition, Addison Wesley Publishers, 2012. (Earlier editions are also acceptable, but page references will be given for the 4th edition only.)

• U. Endriss. An Introduction to Prolog Programming. Lecture Notes, King’s College London and University of Amsterdam, 1999–2018 (free to download from Canvas or here).

Leerdoelen

• Students will be able to recognise, explain and implement the most important search techniques to solve non-trivial AI problems.
• They will be able to design new algorithms and learn how to analyse the performance of existing algorithms.
• The student is able to perform basic programming in Prolog and can describe the declarative programming paradigm.
• They will gather experience with how to approach the challenge of designing a new algorithm and learn how to analyse the performance of existing algorithms

Onderwijsvormen

• Hoorcollege
• Laptopcollege
• Zelfstudie

Lectures
The lectures are the primary source of teaching 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 the regular lectures (on Tuesday and Wednesday) and attend the remedial lecture on Thursdays if needed.

Lab Sessions
The main purpose of the lab sessions is to give you the opportunity to work on your exercises under supervision, with direct access to expert help. 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. There will usually be at least two TAs working in every room. Your own personal TA will be present for some but not all of your weekly lab sessions.

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Voor practica en werkgroepbijeenkomsten met opdrachten geldt een aanwezigheidsplicht. De invulling van deze aanwezigheidsplicht kan per vak verschillen en staat aangegeven in de studiewijzer. Wanneer studenten niet voldoen aan deze aanwezigheidsplicht kan het onderdeel niet met een voldoende worden afgerond.
  

Aanvullende eisen voor dit vak:

The lab sessions on Tuesdays and Wednesdays are compulsory and you are required to attend 10 out of these 12 sessions. You may attend the optional lab on Friday instead of one of the mandatory ones.

If this obligation is not met, you are not permitted to take the resit exam (hertentamen) in December. In the event of personal circumstances, as described in Teaching and Examination Regulations (OER), a different arrangement may be proposed in consultation with the study advisor.

Toetsing

Summary
Homework (40%) and two written exams (2 x 30%).

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 hertentamen. If you sit the hertentamen, the grade you obtain will replace your grade for the exam component (whatever your original exam results may have been). Any missed exam or homework assignment is graded with a 1.0. There is no resit opportunity for the homework component.

Late submissions
Always make sure to submit the homework before the deadline! Submissions up to 24 or 48 hours late will get a 25% or 50% reduction, respectively. Any submission more than 48 hours late will not be graded and you will receive a 1 for this homework.

Opdrachten

There are three kinds of assignments in this course. These will be announced on Canvas as the course progresses.

Reading assignments
These will usually be sections from the lecture notes and/or Bratko’s book. You should read the material indicated sometime before the next lecture. In practice, you will probably want to have a quick look at the beginning of (or before) your lab session and then read everything more carefully once more after you have submitted your weekly homework. It will be assumed that you have completed the reading assignments.

Lab assignments
Each week there will be exercises to explore in the next lab session. Sometimes these will be given explicitly; otherwise you are expected to try out  the examples discussed during the latest lecture. You should investigate and analyse these carefully (e.g. see what happens when the code changes a little or pose somewhat different queries). Don't just reproduce what has been shown in class.

Assessed assignments (the 'homework')
These will be assessed and need to be submitted by the deadline indicated (these are called the homework). We will typically give you unassessed exercises on Tuesdays to practice during the lab session, and homework consisting of assessed exercises on Wednesdays, to be submitted by Saturday.

Code of conduct
For the homework, you must submit your own solutions. It is ok 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 ok 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. 

Fraude en plagiaat

Dit vak hanteert de algemene 'Fraude- en plagiaatregeling' van de UvA. Hier wordt nauwkeurig op gecontroleerd. Bij verdenking van fraude of plagiaat wordt de examencommissie van de opleiding ingeschakeld. Zie de Fraude- en plagiaatregeling van de UvA: http://student.uva.nl

Weekplanning

Rooster

Het rooster van dit vak is in te zien op DataNose.

Aanvullende informatie

This course will be taught in English, but you may use Dutch during the laptopcollege.

The course will be managed through Canvas.

Contactinformatie

Coördinator

• dr. Malvin Gattinger

The course is taught by Malvin Gattinger (b.r.m.gattinger@uva.nl, room F2.41 at Science Park 107).

The Senior TA for this course is Lieuwe Rekker (l.h.rekker@uva.nl, room C2.159 at Science Park 904).

There are several teaching assistants supporting the course. They run the lab sessions and grade the homework. You can find contact details on Canvas.

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. Note that during the lab session you will also interact with some of the other TAs.