Nadas institutionssymbol

^ Up to the home page of the course (in Swedish)

på svenska

Course description 1997/98

2D1443 Parallel Computations

KTH credits4Lectures30
Grading, KTHU, 3, 4, 5Lab work-
Compulsory for-OtherIndividual work
Elective forD, FPeriodsWill not be given in
LanguageSwedish; if
requested by
students in


Jens Lagergren, +46 - 8 - 790 7327,


Advanced course in theoretical computer science focusing on the parallel computational model PRAM.


The goal of the course is to give the students so that they will be able to


The course will describe the PRAM model. In this model a number of processors work synchronously in a loop: read-think-write. The time that a PRAM algorithm demands is the number of read-think-write phases. An algorithm is called a NC algorithm if it uses at most the time O(logk n) och at most O(nc) processors on any input data of size n (where k and c are constants).

The course first introduces the model and a number of basic techniques like: pointer jumping, accelerated cascading, and symmetry breaking. Then the course moves on to parallel algorithms for problems of about the same type that will be considered in an ordinary algorithm course: lists, evaluation of expressions, search and sorting, lower bounds for search and sorting (comparison models), graphs, strings, and arithmetic.

If there is time probabilistic, parallel algorithms and lower bounds for parallel PRAM algorithms (general) will be studied.


One of the courses 2D1353 Algorithms, Data Structures, and Complexity and 2D1354 Algorithms and Complexity or the equivalent.


Please discuss with the instructor.


Written exercises (OVN1; 4 cr.).

Course material

Reading list available at the department. In 96/97: J. JáJá, An introduction to parallel algorithms, Addison Wesley, 1992.


The course is given every second year. Will not be given in 97/98.

Link to course description 1996/97

^ Up to the home page of the course (in Swedish)

Responsible for this page: <>
Latest change June 9, 1997
Technical support: <>