This is a 1st-year course in the UvA's BSc Artificial Intelligence programme. It provides an introduction to algorithmic thinking and basic problem solving techniques in AI. Special emphasis is put on search algorithms, including both uninformed search algorithms such as depth-first search and breadth-first search, and heuristic-guided search with the A* algorithm. These algorithms are implemented in the declarative programming language Prolog. This website provides some general information on the course as well as access to the lecture notes and the slides used during classes. For day-to-day information, including homework assignments, please refer to the UvA Blackboard system.

- Lecturer: Ulle Endriss (ILLC, University of Amsterdam)
- Textbook: I. Bratko. Prolog Programming for Artificial Intelligence. 4th edition, Addison-Wesley Publishers, 2012.
- Lecture Notes: An Introduction to Prolog Programming (errata)
- Lecture slides (updated throughout the semester)
- Resources: SWI-Prolog

**Examples.**
During weekly homework assignments you will encounter a wide variety of exciting but challenging problems in AI and you will learn how to solve them by applying the fundamental principles and techniques taught during lectures. Below are some representative examples.

In the You will learn that it is fairly easy to write a program that beats any human player hands down at this game. |
In the Although much more challenging than the |
At the heart of online travel recommendation services such as the one offered by Google are algorithms for finding the shortest path between two points on a map. You will learn how to write a program to find the shortest route between any two major cities in the Netherlands. |

In the Treaty of Rome (1957) the six founding members of the European Union fixed the voting rule to decide on proposals in the European Council. To pass, a proposal had to get at least 12 votes. France, Germany, and Italy each had 4 votes; Belgium and the Netherlands each had 2 votes; and Luxembourg had 1 vote. Is that fair? You will learn how to write a program to compute the voting power of each country, so as to be able to discuss such questions of fairness systematically. |
You will learn how to write a program to automatically solve some of the most difficult exercises for your Alas, by the time you will know enough about algorithms and programming to do this, the |
In 1742, in a letter to the famous mathematician Leonhard Euler, Christian Goldbach conjectured that every even number greater than 2 is the sum of two prime numbers. To date, no mathematician has been able to prove that Goldbach's Conjecture really is true for You will learn how to write a program that confirms the conjecture for all numbers up to 10,000 in under 1 second. |

Suppose a robot starts in the upper lefthand corner of the maze shown below and wants to move to the lower righthand corner... You will learn how to write a program to help the robot find its way through this and any other kind of maze. |
The Eight Queens Problem is a famous chess problem asking you to place eight queens on a chess board in such a way that none of them can attack any of the others. You will learn how to write a program that solves the problem in under 10 milliseconds. And it will enumerate |
A farmer wants to get a fox, a chicken, and a bag of grain across a river, but at most one of these will fit in his boat besides himself. He mustn't leave the fox and the chicken on their own, nor the chicken and the grain, for fear of one of them getting eaten by the other. Is it possible to move everything safely to the other side? You will learn how to write programs to solve puzzles of this kind in a systematic fashion. |

**Why Prolog?**
In Prolog you can write very short and elegant programs to solve nontrivial problems. For example, the nine problems described above on average require fewer than 30 lines of code. (Well, to be completely precise, for the route-finding application we also need access to a database of cities and roads in the Netherlands; and for the *Letters Game* we also need access to a lexicon.) The course will focus on the general patterns underlying the solutions to such problems. For example, finding a perfect answer in the *Numbers Game*, helping the robot through the maze, and solving the *Eight Queens Problem* can all be done by using the same kind of fundamental search algorithm.

**Topics.**
The course covers the following topics:

- Basic features of the Prolog programming language, including lists, arithmetic expressions, cuts, and negation-as-failure; as well as a few additional features, such a file handling, dynamic predicates, and collecting all answers for a given goal. The basic concept of programming by means of recursion will take on a central role. We will also discuss the way in which Prolog works, including the concepts of matching and backtracking.
- Basic aspects of algorithm design, including the formal analysis of the time and memory requirements of algorithms using the
*Big-O notation*. Our initial exampels will concern teh design of sorting algorithms, such as*bubblesort*and*quicksort*. - Search algorithms, including
*depth-first search*,*breadth-first search*, and*heuristic-guided search*using the A* algorithm; as well as a general approach for modelling a wide range of search problems using the so-called*state-space representation*.