ĆWICZENIA   5 ASD

W części tablicowej proszę omówić następujący algorytm równoczesnego wyszukiwania minimum i maksimum w danym ciągu liczbowym (modyfikacja algorytmu, o którym była mowa na wykładzie):

Wersja A

Krok1: dla każdej pary kolejnych elementów ciągu ustawiam minimum na pozycji nieparzystej, a maksimum na pozycji parzystej .

Krok 2: szukam elementu najmniejszego na pozycjach nieparzystych

Krok 3: szukam elementu największego na pozycjach parzystych.

Wersja B

Krok1: porównuję parami elementy i-ty i n-i+1szy (i-ty od początku z i-tym od końca) ; większy z pary zostawiam na wyższej pozycji .

Krok 2: szukam elementu najmniejszego na pozycjach od 1 do połowy ciągu

Krok 3: szukam elementu największego na pozycjach od połowy do końca.

Policzyć koszt tego algorytmu, omówić poprawność i implementację.

Wersja C

Algorytmy jak wyżej ale implementacja na listach jedno lub dwukierunkowych.

W drugiej części ćwiczeń studenci powinni napisać i uruchomić jedną z wersji tego algorytmu(można pomyśleć o wersji z elementami dowolnego typu, jeśli umiejętności studentów w programowaniu obiektowym są wystarczające).

Nie wiem czy to pora na wejściówkę, ale jeśli tak to niech ona dotyczy wyszukiwania:

Przykładowe pytania na wejściówkę 3

1. Jaki jest minimalny koszt wyszukania elementu najmniejszego w ciągu n elementowym?
2. Oszacować koszt pesymistyczny wyszukiwania elementu x w ciągu uporządkowanym n elementowym metodą skoków co 5 elementów.
3. Jaki jest koszt optymalnego algorytmu wyszukiwania drugiego co do wielkości elementu w ciągu n elementowym?
4. Czy, w algorytmie wyszukiwania drugiego co do wielkości elementu ciągu metodą turnieju, koszt czasowy zależy od początkowej kolejności elementów w ciągu?
5. Jaki jest koszt pamięciowy algorytmu „turniej” ?