DM207: I/O-Efficient Algorithms and Data Structures. (10 ECTS)

STADS: 15017401

Level
PhD course

Teaching period
The course is offered when needed.

Teacher responsible
Email: rolf@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
None

Course introduction
In many applications dealing with large data sets, the limiting factor is not CPU cycles but data transfer between memory levels such as RAM and disk. This is due to the huge differences in access time found among the levels of the memory hierarchy of modern computers (typically including registers, cache levels, RAM, and disk). In the area of I/O-efficient algorithms, the goal is to develop algorithms that minimize the number of data transfers (I/Os) between the memory levels when solving a given problem. This course will cover I/O-efficient algorithms and data structures for fundamental problems such as sorting, searching, and permuting, as well as problems in areas like graphs, strings, and computational geometry. The aim is to teach general techniques for designing I/O-efficient algorithms and data structures, as well as to present an array of results from the research frontier of the area.

Expected learning outcome
After the course, the participant is expected to be able to:

• Describe general methods and results relevant for developing I/O-efficient algorithms and data structures, as covered in the course.
• Give proofs of correctness and complexity of algorithms and data structures covered in the course.
• Formulate the above in precise language and notation.
• Implement algorithms and data structures from the course.
• Do experiments on these implementations and reflect on the results achieved.
• Describe the implementation and experimental work done in clear and precise language, and in a structured fashion.

Subject overview
Hierarchical memory models, fundamental upper and lower bounds, algorithms and data structures for sorting and searching (e.g. by merge and distribution sort, B-trees, buffer-trees, string sorting, string B-trees), geometric searching problems (e.g. interval trees, point location, priority search trees, range trees, kdB-trees, O-trees, R-trees), batched geometric problems (e.g. distribution sweeping, batched filtering, line segment intersection), graph problems (e.g. list ranking, MST, SSSP, planar graph algorithms), cache-oblivious algorithms, and implementation of I/O-efficient algorithms and data structures.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Project assignment. Pass/fail, internal evaluation by teacher.

Assessment and marking:
Oral exam. Danish 7-mark scale, external examiner. 10 ECTS

Reexamination according to the rules decided by the Study Board.

Expected working hours
The teaching method is based on three phase model.

42 forelæsninger.
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.