ASD - Temat A - ćw. ogólno-algorytmiczne, sortowanie, drzewa BST

UWAGA: przy wszystkich zadaniach należy napisać kod tworzący "wydruki diagnostyczne"
demonstrujące, że kod działa prawidłowo...
i należy te wydruki WSTAWIĆ do sprawozdania!!!
sprawozdania należy pisać samodzielnie!!!

mały kompilator języka C dla Windows: tcc-0.9.23.zip (na wszelki wypadek;-);)
UWAGA: w pliku cc.bat należy wymienić ścieżkę "E:\kompC\" na ścieżkę do katalogu, do którego
rozpakowaliśmy zip-a... (także w opcjach -I oraz -L, czyli w 3 miejscach!!)
kompilacja: cc plik.c; powinień powstać "plik.exe"
tutoriale/ książki do języka C: -1-, -2-

edytor pokazujący nr linii tekstu (przydatne przy szukaniu błędów w programie): notepad++ download
wersji "Notepad++ minimalist package" można używać bez instalacji (??) i jest krótka

Zestaw A.1 (sortowanie)
proszę zrobić zadania 1 i 2 z tej strony (sort. przez selekcję i przez wstawianie)
najlepiej w jednym eksperymencie porównać czas działania obu algorytmów;
wprowadź liczniki operacji dominujących (obu, "=" jak i "<=");
dodatkowo proszę zbadać "wrażliwość pesymistyczną" obu tych algorytmów!
(tak dobrać dane, operacje dominujące itp, aby dało się wyciągnąć ciekawy wniosek...)

wykonaj zadanie 3 (wyszukiwanie proste i binarne) oraz zadanie 5 (MergeSort) z tej strony;
a także zadanie 6 (QuickSort) z tej strony;
w QuickSort należy samodzielnie zaimpl. procedurę podziałową Partition
(nie używać "trikowej"; za to można użyć pomocniczej tablicy...)

Zestaw A.2 (drzewa BST)
wykonaj zadanie 111, oraz przyjrzyj się zadaniom 110 i 112 (o listach) z tej strony
wskazówki: uruchom i przeanalizuj przykład listy.cc

wykonaj zadania 20 (impl. BST) z tej strony
do wizualizowania drzewa BST użyj proc PokazPreorder...

Zadanie A.2.1 "oczekiwana wysokość drzewa BST"
Zbadaj oczekiwaną wysokość drzewa BST powstałego przez wstawianie elementów z losowej permutcji liczb {1, ..., n}.
Wskazówki jak to zrobić znajdziesz tutaj, patrz zadanie 21.

Zadanie A.2.2 "wysokość BST bez rekurencji"
Wprowadź do drzewa BST możliwość obliczania wysokości dowolnego wierzchołka drzewa w STAŁYM czasie. Czas działania innych operacji powinien pozostać (asymptotycznie) taki sam!

Zadanie A.2.3 "BST_Delete"
Zaimplementuj operację usuwania wierz z drzewa BST.
Wskazówki: slajdy (str 13), uwagi do zadania 22

Zestaw A.3 (ogólne ćwiczenia algorytmiczne)
wykonaj (także programistycznie) zadania 1 i 2 tej strony

zadania poniżej są łatwiejsze i być może powinny być wykonywane w pierwszej kolejności...
(powinny to być procedury w jednym programie)

Zadanie A.3.1
WE: tablica A[1..n]
WY: max, min - maksymalni i minimalny element tablicy A.
Wymaganie dodatkowe: wszystko oblicz w jednym przebiegu przez A.

Zadanie A.3.2
WE: tablica A[1..n], n; A jest posortowane "<=" (niemalejąco)
WY: x = liczba różnych elementów w tablicy A
Wymaganie dodatkowe: wszystko oblicz w jednym przebiegu przez A.

Zadanie A.3.3
WE: tablica A[1..n]
WY: x = liczba różnych elementów w tablicy A

Zadanie A.3.4
WE: tablica A[1..n], n, m
WY: znaleźć element tablicy A który najczęściej występuje w A
Założenie: elementy tablicy A należą do zbioru {1, ..., m}

Zadanie A.3.5
WE: tablica A[1..n], n
WY: odwróć kolejność elementów tablicy A

Zadanie A.3.5a
Oszacuj pesymistyczną złożoność czasową algorytmów z zadań A.3.1-5.
Podaj jak rozumiesz "rozmiar danych WE" oraz czym jest "operacja dominująca".
Wynik przedstaw w postaci asymptotycznej O(???).

Zadanie A.3.6
Napisz algorytm generujący losową permutację zbioru {1, ..., n} w tablicy A[1..n]. Zakładamy że dysponujemy funkcją random(k) zwracającą liczbę wybraną ze zbioru {1, ..., k} z tym samym prawdopodobieństwem (=1/k). Wszystkie permutacje mają mieć to samo prawdopodobieństwo = 1/(n!), i ma to być oczywiste ...

Zadanie A.3.7
WE: tablice A[1..n], B[1..n] - tablice reprezentujące liczby w zapisie dziesiętnym (każdy element tablicy zawiera jedną cyfrę);
WY: tablica C[1..n+1] = wynik dodawania liczb zapisanych w tablicach A i B.

Zadanie A.3.8
WE: A[1..n], B[1..n], C[1..n] - posortowane "<=" tablice liczb;
WY: W[1..3n] - tablica W zawiera wszystkie elementy tablic A, B i C, oraz jest posortowana.
Wymaganie dodatkowe: algorytm powinien działać w czasie O(n); w szczególności nie wolno po prostu przepisać tablic A, B, C do W i potem posortować W.

Zadanie A.3.9
Zapisz algorytm który oblicza C:=A suma B, czyli sumę teoriomnogościową zbiorów liczb całkowitych A i B, a wynik umieszcza w C. Zbiory liczb są reprezentowane jako tablice w których liczby się nie powtarzają (tablice te NIE są posortowane !!!). Liczba elementów zbioru A jest równa dluA, czyli używane są elementy A[1], ..., A[dluA], podobnie z pozostałymi zbiorami. Zauważ, że wynik działania procedury, czyli C, także musi być prawidłową reprezentacją zbioru! Wymiary tablic A, B i C są następujące: A[1..n], B[1..n], C[1..2n]. Nie wolno używać żadnych pomocniczych tablic. Procedura musi działać w czasie O(n^2).

Zadanie A.3.10
Zapisz algorytm który oblicza C:=A suma B. Tym razem zbiory liczb są reprezentowane jako posortowane rosnąco tablice w których liczby się nie powtarzają. Obowiązują oznaczenia z poprzedniego zadania. Procedura musi działać w czasie O(n).
Wskazówka: przypomnij sobie algorytm scalania dwóch posortowanych ciągów liczb ... .