Algorytmy i struktury danych

Zagadnienia do ćwiczeń

1. Konstruowanie algorytmów i ich zapis za pomocą:

a. opisu słownego,
b. schematu blokowego
c. pseudokodu

2. Ocena złożoności czasowej algorytmów za pomocą O-notacji (na poziomie idei algorytmu, zapisu za pomocą schematu i

pseudokodu).

3. Analiza metod sortowania (w tym sortowanie stogowe przy zapisie danych w postaci drzewa i w tablicy).
4. Analiza metod wyszukiwania (liniowe, połówkowe, haszowanie).
5. Operacje na listach w reprezentacji ze wskaźnikami osadzonymi i w reprezentacji tablicowej (Front, Push, Pop, Rear,

Inject, Eject).

6. Przykłady zastosowania stosu (m. in. Notacja Polska i ONP).
7. Przykłady zastosowania kolejki (np. sortowanie plików sekwencyjnych).
8. Przykłady i reprezentacja grafów (wskaźniki, skorowidze, mapy bitów, macierze sąsiedztwa).
9. Zastosowania grafów (np. sterowanie w automacie skończonym, maszynie Turinga).
10. Rodzaje i reprezentacja drzew (wskaźniki, tablice, uporządkowanie lewolistowe).
11. Zastosowanie drzew (np. drzewo rozbioru gramatycznego wyrażeń arytmetycznych, drzewa BST w sortowaniu i

wyszukiwaniu).

12. Znajdowanie minimalnego drzewa rozpinającego algorytmami Prima i Kruskala.
13. Generowanie kodu Huffmana algorytmem zachłannym z wykorzystaniem drzewa.
14. Znajdowanie cyklu Eulera w grafach.
15. Znajdowanie cyklu Hamiltona w grafach.
16. Znajdowanie najkrótszej ścieżki w grafach (porównanie algorytmu zachłannego z programowaniem dynamicznym).
17. Analiza problemu komiwojażera.
18. Zalety i wady rekurencji na przykładzie algorytmów (porównanie algorytmów rekurencyjnych i iteracyjnych):

a. silnia,
b. liczby Fibonacchiego,
c. wieże Hamoi.

19. Algorytmy tworzenia trójkąta Sierpińskiego i innych fraktali.