Zaawansowane Struktury Danych (strona rozproszona)

wykład monograficzny w semestrze zimowym 2006/07

Prowadzący

Łukasz Kowalik i Marcin Mucha (który umieszcza materiały do swoich wykładów tutaj)

Egzamin (ustny)

Można wybrać dowolny z dwóch terminów: 02.02.2007 (piątek) i 06.02.2007 (wtorek). Najpóźniej dzień wcześniej trzeba wysłać e-mail na adres mucha AT mimuw, zaznaczając który termin się wybiera. Zaczniemy o 12.00. W danym dniu, na stronie Marcina pojawi się lista zapisanych osób i przydzielony slot czasowy (12.00 + k*Delta dla k-tej zgłaszającej się osoby).

Cel wykładu

Celem jest przedstawienie aktualnego stanu wiedzy na temat wybranych zagadnień z zakresu struktur danych.

Przedstawimy zarówno struktury danych używane w praktyce (dynamiczne haszowanie, drzewa typu splay, kopce parujące) jak i struktury danych o szokujących implikacjach teoretycznych (jak np. sortowanie liczb całkowitych w czasie O(n*loglogn)). W każdym przypadku będzie nas interesowała analiza złożoności czasowej omawianych struktur -- w sensie czasu pesymistycznego, zamortyzowanego lub oczekiwanego.

Jeśli chcesz się dowiedzieć dlaczego FBI używa filtrów Blooma albo poznać fascynujące problemy otwarte dotyczące drzew typu splay, zapraszamy!

Plan wykładu i odnośniki do literatury (w tym nasze notatki)

Haszowanie. Haszowanie uniwersalne; haszowanie w przetrzeni liniowej i ze stałym czasem zapytań (tzw. haszowanie doskonałe, algorytm Fredmana, Komlosa, Semerediego); haszowanie dynamiczne (Cuckoo Hashing); filtry Blooma. 2 wykłady.
Materiały:
- Cormen (haszowanie uniwersalne i doskonałe)
- Notatki do wykladow E. Demaine'a (wykład 1. i 2.)
- Artykuł Rasmusa Pagha Cuckoo Hashing for Undergraduates (tytuł trzeba chyba przetłumaczyć jako "Haszowanie kukułkowe dla opornych")
Sortowanie i wyszukiwanie liczb całkowitych (z ograniczonego uniwersum). Drzewa van Emde Boas'a, X-szybkie drzewa trie, Y-szybkie drzewa trie, fusion trees; szybkie sortowanie liczb całkowitych; twierdzenie o równoważności problemów sortowania i kolejki priorytetowej; dolne ograniczenia. 5-6 wykładów
Materiały: strona Marcina
Drzewa typu splay. Podstawowe własności; twierdzenie o dostępie sekwencyjnym; hipoteza o kolejce dwustronnej i jej częściowe rozwiązanie; hipoteza o dynamicznej optymalności drzew typu splay i jej częściowe rozwiązania (drzewa Tango). 2 wykłady
Materiały:
- moje notatki (podstawowe własności + twierdzenie o dostępnie sekwencyjnym): [PDF],
- notatki E. Demaine'a [PDF],
- praca o drzewach Tango: Demaine, Harmon, Iacono, Patrascu "Dynamic Optimality--Almost".
Kolejki priorytetowe. Kopce parujące (pairing heaps); wzbogacanie kolejek priorytetowych o operację złączania. 2 wykłady
Materiały:
- moje notatki (kopce parujące): [PDF] -- POJAWIĄ SIĘ :),
- Praca Fredman, Sedgewick, Sleator, Tarjan "The pairing heap..." [PDF],
- rozdział 3 z pracy Mendelson, Tarjan, Thorup, Zwick "Melding priority queues".
- Lemat 23, ze strony 36 z pracy Alstrup, Husfeldt, Rauhe "Marked Ancestor Problems"
Problem najniższego wspólnego przodka (lowest common ancestor) i problem minimum z zakresu (range minimum query). 1 wykład
Materiały: strona Marcina
Struktury danych dla dynamicznych algorytmów grafowych. Dynamiczne drzewa (link-cut trees) i algorytm przepływowy w czasie O(mn log n), drzewa Eulera (ET trees) i dynamiczna spójność w czasie O(log^2 n), struktury danych przechowujące informacje o najkrótszych ścieżkach w grafie. 2 wykłady
Materiały:
- moje notatki (link-cut, zastosowania do LCA i algorytmu Dinica): [PDF]
- notatki E. Demaine'a (link-cut, chyba jest błąd w analizie) [PDF]
- Praca Sleator, Tarjan "Self-Adjusting..." [PDF]
- Praca Sleator, Tarjan "A data structure for dynamic trees" [PDF]
- ET trees i dynamiczna spójność strona Marcina
- Aproksymacyjna wyrocznia najkrótszych ścieżek: praca Thorup, Zwick "Approximate Distance Oracles" [PS]