General Info

Teachers

• Nicola Prezza, npre@dtu.dk
• Inge Li Gørtz, inge@dtu.dk
• Philip Bille, phbi@dtu.dk

When and where Friday 9-12, Bldg. 421, room 002. The course starts on September 8, 2017

Content Advanced state-of-the-art compact data structures. Entropy, coding, arrays, bitvectors, permutations, sequences, trees, graphs, grids, compressed text indexes, dynamic data structures.

Course format The course is a reading course, meaning that no ordinary lectures will take place. Instead, everyone is expected to read the material and do the exercises on their own at home. At our meetings we will go through the material together, discussing the difficult parts, repeating proofs on the whiteboard, etc. We will also explore open problems and identify possibly fruitful research directions. Everyone is expected to be able and willing to contribute to the discussion.

Material During the course we will go through the following book: Compact Data Structures: A Practical Approach, Gonzalo Navarro. We will also use research articles containing new material not present in the book.

Prerequisites Undergraduate level courses in algorithms and data structures (comparable to 02105 + 02110) and mathematical maturity. You should have a working knowledge of algorithm analysis (e.g. asymptotic notation, worst case analysis, amortized analysis, basic analysis of randomized algorithms) and data structures (e.g. stacks, queues, linked lists, trees, heaps, priority queues, hash tables, balanced binary search trees, tries).

Weekplan

The weekplan is preliminary. It will be updated during the course. Under each week there is the material that will be discussed during the lecture and the exercises that should be done by the lecture.