Algorytmy i Struktury Danych, Semestr 5,

Imię i Nazwisko: Numer grupy:

Problem 1.

Proszę zaklasyfikować pesymistyczną złożoności następujących algorytmów (sortujących n liczb): insertionsort, selectionsort, mergesort, quicksort, heapsort:

-O(log(n))

-O(n)

-O(n*log(n))

-O(n²)

-O(n³)

Problem 2.

Proszę zbudować z liter swojego nazwiska heap metodą Floyda (na odwrocie kartki). Następnie proszę o narysowanie struktury kopca po jednokrotnym wykonaniu operacji delete_max.

Problem 3.

Niech x - będzie Pani/Pana nazwiskiem, a y - będzie rewersem słowa x. Proszę wyznaczyć najdłuższy wspólny podciąg dla ciągów x i y - nwp(x,y).

Problem 4.

W danej tablicy char tab[] zapisane są litery Pana/Pani nazwiska. Proszę zapisać zawartość tablicy tab[] poddanej jednokrotnej procedurze partitioning'u (na odwrocie kartki).

Problem 5.

Dany jest zbiór wszystkich trzyliterowych sekwencji z Pana/Pani nazwiska. Proszę wypisać (na odwrotnej stronie tej kartki) wszystkie etapy sortowania tego zbioru metodą kubełkową.

Problem 6.

Proszę zbudować drzewo kodu Huffmana dla liter teksty składającego się z następujących elementów: Pani/Pana - pierwsze imię, drugie imię, nazwisko.

Problem 7.

Proszę oszacować szybkość wzrostu poniżej podanych funkcji:

1. t[n]=2*t[n/2] dla n>1 oraz t[1]=1;

2. t[n]=t[n-1]+1/n dla n>1 oraz t[1]=1.

Problem 8.

Dana jest tablica int tab[2n]. Proszę zaprojektować
algorytm dekomponujący tablicę tab[] na dwie tablice:
int tab1[n] oraz int tab2[n], takie że: dla dowolnych i, j = 0,..,n-1: tab1[i]  tab2[j]. Proszę oszacować złożoność czasową zaproponowanego algorytmu.

Problem 9.

Proszę zilustrować działanie poniżej podanych algorytmów (na nietrywialnym przykładzie): DFS, BFS, algorytm wyznaczania cykli Eulera, Forda-Bellmana, Dijkstry, MST Prima-Dijkstry, oraz MST Kruskala.

UWAGA: Porządek liter: a < b < c < ... < z,

zaniedbywany jest rozmiar litery: x = X.

Powodzenia!

---