Problem Solving and Search

Studiewijzer 2023/2024

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 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. 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. (used mostly in the second half of the course. 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 (covers the first half of the course, free to download from Canvas or here).

Leerdoelen

• Students will be able to perform basic programming in Prolog.
• Students will be able to recognize and explain the most important search techniques.
• Students will be able to solve non-trivial AI problems by choosing and using suitable algorithms.
• Students will be able to implement common search algorithms.
• Students will be able to describe the declarative programming paradigm.
• Students will be able to analyze 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.

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.

If this obligation is not met, you are not permitted to take the resit exam (hertentamen) in December. In the event of special 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 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 exam or homework assignment is graded with 0 points. 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 0 points for this homework.

Opdrachten

There are two 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 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 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 on Tuesday and you should submit them by Saturday. Part of the homework is automatically graded using CodeGrade. You are allowed to submit multiple times before the deadline and only the last/newest submission will count for your grade.

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

• Malvin Gattinger

The course is taught by Malvin Gattinger (he/him): b.r.m.gattinger@uva.nl

The Senior TA for the first half of this course is Helena Willard (she/her): h.f.willard@uva.nl

The Senior TA for the second half of this course is Frank Wildenburg (he/him): 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.

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.