TU Delft Algorithmics
Cees Witteveen
Delft University of Technology Teaching ALG Group
EWI ALG Cees WitteveenTeaching
eng
 
 
 
 
 
 
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 NP-complete. Also approximation techniques will be introduced and evaluated.
Time permitting, we will also explore some hot topics of research including cryptography, zero-knowledge 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 4-5 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 mini-symposium. 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:
DNA-computing

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 Work-Time presentation framework,
Basic techniques: Balanced trees, Divide and conquer, Cascading, Pipelining, Partitioning,
Algorithms for matrix operations,
Sorting and Searching,
Graph Algorithms

Powerpoint presentations and pdf-versions 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 multi-agent systems, like task allocation, coalition formation, distributive cooperative planning, diagnosis in multi-agent systems, repair-based planning replanning and incidence handling in multi-agent 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
    Market-based Multi-agent Systems
    Evolving Cooperation
  • Task Allocation in MAS
    Distributed Planning
    Coordination by Plan Merging