




IN3110 + IN3120 


Fundamentals of Computer Science 


In these courses we study two of the most fundamental questions in computer science: What computations can be performed on a computer (computability theory) and How efficiently can they be performed (complexity theory).
These questions will be studied with respect to a suitable model of computation: the Turing machine. In the first part of the course we will show that some fundamental issues in computer science such as: given a program P does it halt for any input? and given two program P and Q, are they equivalent? cannot be solved in an algorithmic way.
In the second part we will study the complexity of some important problems for which algorithms are known. The major issue here is whether a problem can be characterized as tractable (there exists an efficient algorithm for the problem) or as intractable (no efficient algorithm can exist). The famous P = NP? problem will be discussed and reduction techniques will be discussed to show that a problem is NPcomplete. Also approximation techniques will be introduced and evaluated.
Time permitting, we will also explore some hot topics of research including cryptography, zeroknowledge protocols and complexity of quantum computation.




Powerpoint presentations and pdf files of the lectures (Part 1 + Part 2) given can be downloaded here.

In this seminar, groups of 45 students are assigned to topics in algorithmics, computability and complexity. Each group is given a number of papers, has to write an essay and to give a public presentation during a minisymposium.
This year we had the following subjects:
Complexity:
Kolmogorov Complexity, Quantum Complexity,
The limits of Quantum Computing, Quantum Computing Algorithms
NP and Physics
Alternative computing models:
DNAcomputing
Computational Geometry:
Path Planning, Collision Detection,
Convex hull, Diameter of Set of Points
Market Based Computing:
Principles of Mechanism Design
Collective Intelligence:
Principles of COIN





Understanding and general knowledge of the most important aspects of parallel computers, parallel algorithms and parallel languages and skills in implementing some simple parallel algorithms.
Architecture and languages:
Models of Parallel Computers, Basic Architectures and Communication Operations, Performance and Scalability, Parallel Programming Languages.
Algorithmics:
The WorkTime presentation framework,
Basic techniques: Balanced trees, Divide and conquer, Cascading, Pipelining, Partitioning,
Algorithms for matrix operations,
Sorting and Searching,
Graph Algorithms




Powerpoint presentations and pdfversions of the lectures given can be downloaded here. 
In july 2005, we presented a tutorial on Planning in Multiagent Systems given at the EASSS'05. Below you can download the pdf versions of the slides presented.
Part 1: Multiagent Planning
Part 2: AI Planning
Part 3: Coordination before/during and after planning





In this course we discuss topics in cooperative algorithmics applied to multiagent systems, like task allocation, coalition formation, distributive cooperative planning, diagnosis in multiagent systems, repairbased planning replanning and incidence handling in multiagent systems.
This course will be given as a student seminar. During the course students will have to participate in
 preparing and presenting a lecture on the basis of journal papers about some topics selected;
 discussion of research questions after the presentation
 preparing a short survey about some topic in cooperative algorithmics
Last year's (2005) topics were
 Social laws and social conventions
Norms and obligations
Rights and Argumentation
 Collective Intelligence
Marketbased Multiagent Systems
Evolving Cooperation
 Task Allocation in MAS
Distributed Planning
Coordination by Plan Merging





  