Kursusnavn

Data structures: Theory and practice

ECTS
 		7.5
Blokplacering
 		Quarter 2
Skemagruppe
 		C
Kursusansvarlig
 Jyrki Katajainen
Andre undervisere
 Amr Elmasry
Formål

The purpose of this course is to build a bridge between the theory and practice in the area of data structures. One is supposed to learn to transform theoretical designs into efficient programs.

Indhold

In the first part of the course, the teachers present some recent theoretical results on data structures and data-structuring techniques. The topics covered include among the others (seven lectures):
- cache-oblivious data structures
- external-memory data structures
- data-structural transformations
- global rebuilding
- deamortization
- derandomization
- universal hashing.
In the second part of the course, the students will apply the theory in practice and implement some advanced components to our program library (CPH STL, see www.cphstl.dk).

Kompetancebeskrivelse*


Målbeskrivelse
 		After the course the student should be able to
1) describe data structures and operations on them using a pseudo-code;
2) use fluently the concepts found in the literature on advanced data structures;
3) design data structures for different models of computation, including the standard random-access machine;
4) analyse the theoretical performance characteristics of data structures designed by himself and others;
5) implement advanced data structures using a concrete programming language;
6) explain the technical details of a modern program library on data structures and algorithms.
Eksamensform
 		4 assignments; presentation; 2-weeks group project; oral exam (30 minutes; without preparation; internal examiners; 7-grade scale)

The assignments must be passed before getting the right to start the project. The oral exam has two parts: in the first part the project is discussed and in the second part other parts of the pensum.
Faglige forudsætninger

A course on Algorithms and data structures

A course on C++ programming
Formelle krav

Right to take graduate courses at our department
Undervisningsprog
 		English
Varighed

7 weeks teaching plus 2 weeks exam period
Lærerbøger*
 		K. Mehlhorn and S. Näher: LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press (1999)
Dinesh P. Mehta and Sartaj Sahni (Editors): Handbook of Data Structures and Applications, CRC Press (2005)
Mark H. Overmars: The Design of Dynamic Data Structures, Lecture Notes in Computer Science 156, Springer-Verlag (1983)
Rajeev Raman: Eliminating Amortization: On Data Structures with Guarnteed Response Time, Ph.D. Thesis, University of Rochester
(1993)
Jeffrey Scott Vitter: Algorithms and Data Structures for External Memory, now Publishers Inc. (2008)

Plus articles and extracts from other relevant books.
Pensum*
 		To be announced by the end of the fourth week of the teaching period
Undervisningsform*

lectures, seminars, obligatory assignments, project exam


Omfang*

lectures 7 × 2 hours; seminars 7 × 2 hours; 4 assignments; 2-weeks project; oral exam