Zadania.
Różne techniki rozwiązywania problemów:
1. Rozwiązać zadania ze strony http://livearchive.onlinejudge.org/. W celu poszukiwania
zadania o podanym numerze można wejść do odpowiedniego archiwum zadań
wybierajÄ…c linki:  Browse Problems , a potem  ICPC Archive Volumes
a) 2487  Lollies
b) 2122 - Recognizing S Expressions
c) 2535 - Magnificent Meatballs
d) 3390 - Pascal's Travels
Sortowanie .
1. Posortuj poniższą tablicę za pomocą algorytmu sortowania przez wstawianie (insertsort).
Dane mają być posortowane malejąco, a część posortowana ma narastać od końca tablicy.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
2. Posortuj poniższą tablicę za pomocą algorytmu sortowania bąbelkowego (bubblesort).
Dane mają być posortowane rosnąco, a bąbelki mają się przesuwać od końca tablicy do
poczÄ…tku.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
3. Posortuj poniższą tablicę za pomocą algorytmu sortowania bąbelkowego (bubblesort).
Dane mają być posortowane rosnąco, a bąbelki mają się przesuwać na przemian: raz od
początku tablicy, raz od końca tablicy.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
4. Posortuj poniższą tablicę za pomocą algorytmu sortowania przez wybór (selectsort). Dane
mają być posortowane rosnąco, a część posortowana ma narastać od końca tablicy.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
5. Posortuj poniższą tablicę za pomocą algorytmu sortowania szybkiego (quicksort). Dane
mają być posortowane rosnąco.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
6. Posortuj poniższą tablicę za pomocą algorytmu sortowania przez scalanie (mergesort).
Dane mają być posortowane rosnąco.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
7. Posortuj poniższą tablicę za pomocą algorytmu srotwania stogowego (heapsort). Dane
mają być posortowane rosnąco.
34,2,7,8,4,12,1,15,12,34,13,7
Pokazać stan tablicy po każdym dużym kroku.
Drzewo BST:
1. Pokaz stan drzewa BST po sekwencji rozkazów: wstaw( 20), wstaw (7), wstaw (10),
wstaw (25), wstaw (4), wstaw (1), wstaw (2), wstaw (12), wstaw (30), usun(12), usun(1),
usun(20).
2. Zaimplementuj funkcje na drzewie BST:
a. Zliczającą liczbę węzłów
b. Wysokość drzewa
c. Liczbę węzłów o parzystym kluczu.
Drzewo AVL:
1. Pokazać stan drzewa AVL po dodaniu kolejnych liczb: 1,2,3,4,5,& .
2. Pokazać stan drzewa AVL po sekwencji operacji: wstaw(15), wstaw(10), wstaw(5),
wstaw(20), wstaw 20, wstaw(30),wstaw(35), wstaw(7), wstaw(9), wstaw(8),
wstaw(3).wstaw(33).usuń(8), usuń(9), usuń(10), & .(kolejne operacje może podać
prowadzÄ…cy)
Drzewo czerwono-czarne (RB):
1. Pokazać stan drzewa RB po dodaniu kolejnych liczb: 1,2,3,4,5,& .
2. Pokazać stan drzewa RB po sekwencji operacji: wstaw(15), wstaw(10), wstaw(5),
wstaw(20), wstaw 20, wstaw(30),wstaw(35), wstaw(7), wstaw(9), wstaw(8),
wstaw(3).wstaw(33).usuń(8), usuń(9), usuń(10), & (kolejne operacje może podać
prowadzÄ…cy)
Kopiec dwumianowy:
1. Pokazać stan kopca dwumianowego po sekwencji operacji: wstaw(5), wstaw(20),
wstaw(3), wstaw(15), wstaw(10),wstaw(7),wstaw(2),wstaw(4),wstaw(11), wstaw(6),
wstaw(1), wstaw(9),wstaw(13), usun(11), usun(2), usun(13),usun(7),usun(1), usun(5).
Las zbiorów rozłącznych:
1. Pokazać stan lasu zbiorów rozłącznych dla 12 elementów po przeanalizowaniu sekwencji
połączeń: (A,E),(B,D),(G,K),(I,K),(L,J),(E,D),(L,A),(C,F),(D,F). W przypadku łączenia
(X,Y), przedstawiciel zbioru X staje się wspólnym przedstawicielem. Użyj kompresji
ścieżki, ale nie używaj rang.
2. Pokazać stan lasu zbiorów rozłącznych dla 12 elementów po przeanalizowaniu sekwencji
połączeń: (A,E),(B,D),(G,K),(I,K),(L,J),(E,D),(L,A),(C,F),(D,F).Użyj zarówno kompresji
ścieżki jak i rang jak w programie z wykładu.
Teoria grafów.
Dla poniższego grafu:
26 30
a d
15
g
25
s
12
10 12
20
b
14
t
20 7
11
h
30
e
15
c
5
10
15
7
5
f i
10
1) Pokaż kolejność odwiedzanych węzłów podczas przeszukiwania najpierw-w-
głąb. Jeśli masz wybór kolejnego wierzchołka, wybieraj pierwszy w kolejności
alfabetycznej.
2) Pokaż kolejność odwiedzanych węzłów podczas przeszukiwania najpierw-
wszerz. Jeśli masz wybór kolejnego wierzchołka, wybieraj pierwszy w
kolejności alfabetycznej.
3) Znajdz
najkrótsze ścieżki od wierzchołka  c używając algorytmu Dijkstry.
4) Znajdz
minimalne drzewo rozpinające używając algorytmu Kruskala.
5) Znajdz
minimalne drzewo rozpinające używając algorytmu Prim a.
6) Znajdz
najkrótsze ścieżki (dokładnie ich wagi) pomiędzy każdą parą
wierzchołków.
W zadaniach 1) i 2) wagi są nie używane.
Poszukiwania wzorca w tekście
1. Pokaż ile porównań należy wykonać w algorytmie naiwnym dla wzorca P = 0001 w
tekście T = 000010001010001.
2. Używając wartości modulo q = 11, ile fałszywych trafień będzie przy porównywaniu
metodą Rabina-Karpa w tekście T =3141592653589793 podczas poszukiwań wzorca
P = 26?
3. Stwórz automat skończony dla wzorca P = aabab i pokaż jego użycie podczas
poszukiwań w tekście T = aaababaabaababaab nad alfabetem S = {a, b}
4. Stwórz diagram/tablicę dal automatu skończonego do poszukiwań wzorca
P=ababbabbababbababbabb nad alfabetem S = {a, b}.
5. Dla wzorca z zadania 4 stwórz tablicÄ™ przejść pð powstaÅ‚Ä… w algorytmie Knutha-
Morrisa-Pratta.