Teachers
When and where Friday 912, Bldg. 421, room 002. The course starts on September 8, 2017
Content Advanced stateoftheart 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).
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.
Week  Topics  Exercises  Material 

Entropy and coding  EntropyHuffman 


Arrays  Bit tricks and partial sums 


Bitvectors (1)  Entropycompressed bitvectors 


      
Bitvectors (2) and hashing  Runlength strings 


      
      
Wavelet trees  Dynamic strings 


Parentheses (1)   


Parentheses (2), trees, RMQ  3D range minimum 


Compressed indexes (1): CSA, FMindex  Runlength compressed suffix arrays 


Compressed indexes (2): The BurrowsWheeler Transform  Spaceefficient CSA construction 
