Projekt Programistyczny „Struktury Danych”

Ogólne informacje

Nieprzesuwalny termin oddania rozwiązania: 30.05.2005

W tym projekcie programistycznym każdy będzie miał do zaimplementowania co najmniej jedną ze struktur danych prezentowanych na wykładzie. Dla każdej z tych struktur należy napisać moduł realizujący podstawowe operacje:

• Drzewa AVL – operacje init, insert, search, delete; Komentarz: operacja init tworzy puste drzewo. Ta semantyka dotyczy też tej operacji dla drzew czerwono-czarnych, i drzew samoorganizujących się
• Drzewa czerwono-czarne – operacje init, insert, search, delete;
• Union-find – operacje init, union, find; Komentarz: operacja init inicjuje strukturę dla lasu drzew jednoelementowych
• Słownik statyczny – operacje makedict, search; Komentarz: operacja makedict(n:integer; a: array[1..n] of names) tworzy słownik dla n nazw zapamiętanych w tablicy a
• Kopiec minimaksowy– operacje init, insert, min, max, deletemin, deletemax;
• Kopiec – operacje makeheap, insert, min (lub max), deletemin (lub deletemax);
• Drzewa optymalne – operacje maketree, search; Komentarz: operacja maketree(n:integer; p: array[1..n] of real; q:array[0..n] of real) tworzy drzewo optymalne dla prawdopodobieństw zapamiętanych w tablicach p i q.
• Kopce dwumianowe – operacje makeheap, insert, min, deletemin, meld.
• Kopce Fibonacciego – operacje makeheap, insert, min, deletemin, meld, decreasekey;
• Drzewa samoorganizujące się – operacje init, insert, search, delete, split, join.

Na Wasze rozwiązania powinny składać się (co najmniej) następujące pliki:

• Plik(i) z modułem(-ami);
• Pliki(i) z programem(-ami) wykorzystującymi moduł - programy te zostaną wykorzystane do automatycznego sprawdzenia poprawności Waszych implementacji, w szczególności podczas wykonania nie powinny oczekiwać żadnej interakcji ze strony użytkownika.
• Plik(i) z przykładowymi danymi bądź programem je generującymi;
• Plik przewodni o nazwie guide zawierający (co najmniej) następujące informacje:
• Imię i nazwisko autora
• Treść zadania
• Spis zawartości poszczególnych plików
• Wszelkie informacje, które pomogą osobom trzecim testowanie Waszego rozwiązania.

• Wszystkie pliki należy spakować w jeden się plik typu *.zip. Plik powinien rozpakowywać się do katalogu o nazwie postaci projekt<nr><nazwisko>, np. projekt2.3lorys
• Przyjmujemy następującą konwencję odnośnie nazw plików:
• Pliki z modułami: <akronim><nazwisko>, gdzie akronimy są ze zbioru {avl, redblack, uf, statdict, mmheap, heap, opttree, binheaplazy, binheapeager, fibheap, splaytree}
• Pliki z programami: program<akronim><nazwisko>, gdzie akronimy są jw.
• Pliki z danymi: dane.in
• Pliki z generatorami danych: generator<nazwisko>
• Oczywiście nazwy plików z modułami i programami powinny mieć rozszerzenie właściwe dla użytego języka programowania.
• Przykładowe nazwy plików: redblackrzechonek, programredblacklewicki.
• Programy we wszystkich projektach mają czytać dane z pliku tekstowego dane.in a wyniki wypisywać do pliku wyniki.out.
• Dane w pliku dane.in oddzielane są pojedynczymi spacjami (nie przecinkami!!!)
• Nie określamy rozmiaru danych. Powinniście przyjąć następujące założenia:
• Struktury mają mieć maksymalny rozmiar, jaki zmieści się w pamięci 32MB
• Ciągi danych, na których struktury będą testowane, powinny być bardzo długie (tak by czas wykonania operacji był mierzalny a błąd pomiarów zaniedbywalnie mały w stosunku do tego czasu)
• Programy napisane mają być w jednym z następujących języków programowania:

§ Pascal (standard FreePascal 1.0.6)

§ C++ (standard GCC 3.3.1)

§ Java (standard J2SDK 1.4.0)

o Programy będą kompilowane następującymi poleceniami: fpc, g++, javac. Jedynym parametrem tych poleceń będzie nazwa pliku z programem.

o Programy będą uruchamiane projektów środowisku Linux’owym.

o Proszę nie korzystać projektów projektów bibliotek specyficznych dla poszczególnych producentów oprogramowania.

UWAGA: Wymagane jest przestrzeganie powyższych konwencji - w przeciwnym przypadku może się zdarzyć, że poprawnie działający program nie zaliczy testów sprawdzających poprawność implementacji.

Lista projektów

Projekt 2.1

Napisz moduł implementujący kopce Fibonacciego. Następnie wykorzystaj go do znalezienia najkrótszych dróg w grafie od zadanego źródła do pozostałych wierzchołków.

Postać pliku dane.in:

• w pierwszym wierszu znajdują się n – liczba wierzchołków oraz m – liczba krawędzi w grafie;
• w każdym z kolejnych m wierszy znajduje się trójka liczb naturalnych oznaczających odpowiednio początek, koniec oraz wagę krawędzi;

W pliku wynikowym ma znaleźć się n-1 liczb całkowitych: i-ta liczba ma być równa odległości wierzchołka nr (i+1) od wierzchołka nr 1 (wierzchołek nr 1 będzie źródłem).

Wymagane pliki: fibheap<nazwisko>, programfibheap<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
4 4
1 2 1
2 3 1
1 3 1
3 4 1
 
wyniki.out
1
1
2

Projekt 2.2

Napisz moduł tworzący optymalne drzewo binarnych wyszukiwań, a następnie zastosuj go do utworzenia drzewa dla przykładowych danych.

Postać pliku dane.in:

• w pierwszym wierszu znajduje się n – liczba kluczy w drzewie;
• w drugim wierszu znajduje się ciąg liczb p₁,...,p_n – prawdopodobieństwa zapytań o i-ty klucz słownika
• w trzecim wierszu znajduje się ciąg liczb q₀,...,q_n – prawdopodobieństwa zapytań o klucze spoza słownika - np. q₂ prawdopodobienstwo zapytania o wartosc pomiedzy 2 a 3 kluczem

W pliku wynikowym zawierającym n wierszy ma znaleźć się opis optymalnego drzewa (w postaci ciągu wierzchołków wypisanych w porządku preorder).

Wymagane pliki: opttree<nazwisko> programoptree<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
3
0.2 0.1 0.5
0.0 0.0 0.0 0.2
 
wyniki.out
3
1
2 

optymalne drzewo: 3(1(nil, 2), nil) - o wadze 1.4
drzewo zbalansowane: 2(1, 3) posiada wage 1.9

Projekt 2.3

Napisz moduł tworzący słownik statyczny, a następnie zastosuj go do utworzenia słownika dla przykładowych danych. W module mają znaleźć się co najmniej dwie procedury: makedict, tworząca słownik dla danych z pliku wejściowego, oraz search(key) sprawdzająca, czy key znajduje się w słowniku. Twój program powinien wywoływać procedurę makedict a następnie wypisywać do pliku wynikowego opis utworzonego słownika.

Postać pliku dane.in:

• w pierwszym wierszu znajdują się n – liczba kluczy (przyjmujemy, że n£500000) oraz l – ograniczenie na długość kluczy (przyjmujemy l£ 10);
• w każdym z kolejnych n wierszy znajduje się jeden klucz - słowo co najwyżej l-literowe; litery są z zakresu ‘a’..’z’.

Ustalenia co do rodziny funkcji hashujących. Przyjmij, że funkcja pierwotna i funkcje wtórne są losowane z rodzin funkcji hashujących postaci H_p,l={h_a : a=áa₁,a₂,...,a_lñ, gdzie "_i a_iÎ Z_p}. Wartością funkcji h_a z rodziny H_p,l dla napisu x₁x₂...x_l jest

(åa_ic(x_i)) mod p,

gdzie c(x_i) jest kodem ASCII litery x_i modulo 32. Przyjmij, że napisy o długości mniejszej od l uzupełniane są z prawej strony spacjami (zwróć uwagę, że c(spacja)=0).

W pliku wynikowym (jest to plik tekstowy) znajdują się:

• w pierwszym wierszu – opis pierwotnej funkcji hashującej, podany jako ciąg p a₁ a₂...a_l
• w każdym z kolejnych p wierszy - opis wtórnej funkcji hashującej dla kolejnego kubełka, w formacie takim samym jak dla funkcji pierwotnej.

Wymagane pliki: statdict<nazwisko> programstatdict<nazwisko>

Przykładowe dane i wyniki:
 
 
dane.in
3 2
aa
ab
ba
 
wyniki.out
3 1 2 
3 1 1
3 1 1
3 1 1

Projekt 2.4

Napisz moduły obsługujące kopiec minimaksowy oraz zwykły kopiec. Następne użyj ich w programie implementującym podwójną kolejkę priorytetową.

Postać pliku dane.in:

• w pierwszym wierszu znajduje się m – maksymalna wielkość kopca;
• w drugim wierszu znajduje się n – liczba operacji;
• w każdym z kolejnych wierszy znajduje się opis jednej operacji na podwójnej kolejce priorytetowej; stosujemy przy tym następującą konwencję:
• i, liczba – oznacza operację insert(liczba)
• d – oznacza deletemin
• D – oznacza deletemax

W pliku wynikowym powinien znaleźć się ciąg n liczb, na i-tym miejscu powinna znaleźć się liczba, której dotyczyła i-ta operacja (insert, deletemin lub deletemax). Ponadto wypisz na standardowe wyjście liczbę całkowitą równą czasowi w milisekundach wykonania ciągu operacji przy obydwu implementacjach kolejki.

Wymagane pliki: mmheap<nazwisko> programmmheap<nazwisko> heap<nazwisko> programheap<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
3
5
i,2
i,1
i,3
d
D
 
wyniki.out
2
1
3
1
3

Projekt 2.5

Napisz moduły obsługujące drzewa samoorganizujące się oraz drzewa AVL. Następnie wykorzystaj do porównania średniego czasu dostępu do elementów drzewa dla przykładowych danych.

Postać pliku dane.in:

• w pierwszym wierszu znajduje się n – liczba operacji;
• w każdym z kolejnych wierszy znajduje się opis jednej operacji na drzewie; opis ten ma postać pary op,klucz, gdzie op jest jedną z liter {i,s,d} oznaczających odpowiednio insert, search i delete, a klucz jest liczbą naturalną.

W pliku wyjściowym powinien znaleźć się ciąg złożony z (oddzielonych spacjami) zer i jedynek - na i-tym miejscu powinna znaleźć się cyfra 0 jeśli i-ta operacja search zakończyła się niepowodzeniem, a 1 w przeciwnym przypadku. Ponadto wypisz na standardowe wyjście liczbę rzeczywistą równą odpowiednio średniej liczbie porównań wykonywanych podczas jednej operacji w drzewie.

Wymagane pliki: avl<nazwisko> programavl<nazwisko> splaytree<nazwisko> programsplaytree<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
7
i,1
i,2
i,3
s,4
d,2
s,2
s,1
 
wyniki.out
0 0 1

Projekt 2.6

Napisz moduły obsługujące drzewa samoorganizujące się i drzewa czerwono-czarne. Następnie wykorzystaj do porównania średniego czasu dostępu do elementów drzewa dla przykładowych danych.

Postać pliku dane.in:

o w pierwszym wierszu znajduje się n – liczba operacji;

o w każdym z kolejnych n wierszy znajduje się opis jednej operacji na drzewie; opis ten ma postać pary op,klucz, gdzie op jest jedną z liter {i,s,d} oznaczających odpowiednio insert, search i delete, a klucz jest liczbą naturalną.

W pliku wyjściowym powinien znaleźć się ciąg złożony z (oddzielonych spacjami) zer i jedynek - na i-tym miejscu powinna znaleźć się cyfra 0, jeśli i-ta operacja search zakończyła się niepowodzeniem, a 1 - w przeciwnym przypadku. Ponadto wypisz na standardowe wyjście liczbę rzeczywistą równą odpowiednio średniej liczbie porównań wykonywanych podczas jednej operacji w drzewie.

Wymagane pliki: redblack<nazwisko> programredblack<nazwisko> splaytree<nazwisko> programsplaytree<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
7
i,1
i,2
i,3
s,4
d,2
s,2
s,1
 
wyniki.out
0 0 1

Projekt 2.7

Napisz moduły obsługujące kopce dwumianowe w wersji eager i wersji lazy. Następnie wykorzystaj je do porównania efektywności tych dwóch wersji.

Postać pliku dane.in:

1. w pierwszym wierszu znajduje się n – liczba operacji;

2. w każdym z kolejnych n wierszy znajduje się opis jednej operacji na kopcu według poniższego formatu:

1. c heap gdzie c oznacza operację makeheap, a heap jest nazwą kopca; przyjmujemy, że nazwa ta składa się z jednej dużej litery (przykład: c B oznacza utworzenie kopca o nazwie B)
2. i heap klucz gdzie i oznacza operację insert, heap jest nazwą kopca, a klucz jest liczba całowitą
3. d heap gdzie d oznacza operację deletemin, a heap jest nazwą kopca;
4. m heap1 heap2 gdzie m oznacza opercję meld, a heap1 i heap2 są nazwami łączonych kopców; powstały w wyniku tej operacji kopiec ma nazwę heap1.

W pliku wyjściowym powinien znaleźć się ciąg kluczy - na i-tym miejscu klucz usunięty w i-tej operacji deletemin. Ponadto wypisz na standardowe wyjście liczbę całkowitą podającą w milisekundach czas wykonania przykładowego ciągu operacji.

Wymagane pliki: binheapeager<nazwisko> programbinheapeager<nazwisko> binheaplazy<nazwisko> programbinheaplazy<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
8
c A
i A 2
i A 3
c B
i B 1
d A
m A B
d A
 
wyniki.out
2
1
 

Projekt 2.8

Napisz moduł obsługujący operacje na drzewiastej strukturze dla Union-Find. Zaimplementuj dwie wersje operacji find: jedną z kompresją ścieżek wykonywaną w sposób podany na wykładzie; drugą z kompresją wykonywaną przez podczepianie wierzchołków pod swoim dziadkiem. Następnie wykorzystaj w programie znajdującym liczbę spójnych składowych grafu.

Postać pliku dane.in:

o w pierwszym wierszu znajduje się n – liczba wierzchołków grafu

o w drugim wierszu znajduje się m – liczba krawędzi grafu

o w każdym z kolejnych m wierszy znajduje się para liczb naturalnych nie większych od n opisująca krawędź grafu.

W pliku wyjściowym mają znaleźć się :

o w pierwszym wierszu – liczba naturalna równa liczbie składowych spójności grafu

o w drugim wierszu - dwie liczby naturalne oznaczające czasy w milisekundach znajdowania liczby składowych przez program stosujący pierwszą i (odpowiednio) drugą metodę kompresji ścieżek

o w drugim wierszu - dwie liczby rzeczywiste oznaczające średnią głębokość wierzchołków, do których stosowano find w trakcie obliczeń programu stosującego poszczególne metody kompresji ścieżek.

Wymagane pliki: uf<nazwisko> programuf<nazwisko>

 
Przykładowe dane i wyniki:
 
dane.in
5
4
1 3
4 3
2 5
4 1
 
wyniki.out
2
2 2
2.71828183 3.14159265