Algorytmy i struktury danych, studia zaoczne 2017/18


WYNIKI: kolokwium 2 , zaliczenie i egzamin 3.02.2018 .

Egzamin poprawkowy jest zaplanowany na 24.02.2018 godz. 10 w sali 52. (Można ten termin zmodyfikować w razie potrzeby, o ile zainteresowane osoby zgłoszą jakąś inną propozycję.) Na egzaminie poprawkowym z teorii część pytań będzie podobna jak na pierwszym terminie - warto douczyć się tego, co było na pierwszym termnie. Można też pisać egzamin z zadań, takich jak na kolokwiach, żeby poprawić  wynik z zaliczenia.

Osoby zainteresowane obejrzeniem swojej pracy egzaminacyjnej mogą to zrobić w czasie egzaminu poprawkowego

informacje o egzaminie: EGZAMIN.html

zagadnienia z teorii obowiązujące na agzaminie

Wykład

Wykład jest prowadzony wg podręcznika "Wprowadzenie do algorytmów" Cormen, Leiserson, Rivest, Stein, Wydawnictwo Naukowe PWN. Poniżej są podane wybrane uzupełniające informacje.

analiza złożoności czasowej - wstęp: zlozonosc16.pdf

Kopce binarne i Sortowanie kopcowe (Heap-sort): definicje i pseudokod oraz przykład

Sortowanie szybkie (Quick-sort): pseudokod oraz przykład

Sortowanie przez zliczanie (Counting-sort) i pozycyjne (Radix-sort): pseudokod i teoria

Listy, kolejki i stosy: definicje, fragmenty pseudokodu

Tablice z haszowaniem: funkcje haszujące, pseudokod i przykład

Uwaga: 26.11.2017 na ćwiczeniach (14.50) będzie kolokwium

Drzewa poszukiwań binarnych: definicja i pseudokod operacji na drzewie

Drzewa czerwono-czarne: definicja, wstawianie i usuwanie, złożoność, skrócona wersja.

Najdłuższy wspólny podciąg: pseudokod przykład

Algorytm Huffmana: pseudokod przykład

B-drzewa: wstawianie - przykład, usuwanie - przykład, pseudokod algorytmu usuwania (dwie różnie sformatowane wersje) btreeDelS.pdf btreeDelP.pdf.

Uwaga: 28.01.2018 na ćwiczeniach (14.50) będzie drugie kolokwium




Ćwiczenia

Napisać i przetestować program zgodnie z podaną niżej specyfikacją i z przydzielonym wariantem (tylko jeden program dla każdej osoby). Przydział wariantów - zgodnie z numeracją na liście obecności. We wszystkich tych zadaniach przez listę napiów rozumiemy listę dowiązaniową, w której węzłach są jakieś napisy.

Wskazówka: listy.c oraz listyW.c

Na zajęciach należy zademonstrować działanie programu i umieć wyjaśnić szczegóły kodu (nawet jeżeli kod został napisany na podstawie podręczników, źródeł internetowych, itd.). Ponadto program należy przesłać używając formularza

Przy pierwszym użyciu należy się wpisać na przedmiot. (W razie problemów ze stroną proszę się kontaktować z prowadzącym zajęcia: pawel.paczkowski@inf.ug.edu.pl)

1. Napisać i przetestować funkcję, która dostawia na koniec listy napisów nowy napis. Lista dwukierunkowa niecykliczna bez wartownika

2. Napisać i przetestować funkcję, która dostawia na koniec listy napisów nowy napis. Lista dwukierunkowa cykliczna z wartownikiem

3. Napisać i przetestować funkcję, która dołącza do jednej listy napisów drugą listę napisów (nie tworzyć nowych węzłów, tylko dowiązać jedną listę na koniec drugiej) Lista dwukierunkowa niecykliczna bez wartownika

4. Napisać i przetestować funkcję, która dołącza do jednej listy napisów drugą listę napisów (nie tworzyć nowych węzłów, tylko dowiązać jedną listę na koniec drugiej) Lista dwukierunkowa cykliczna z wartownikiem.

5. Napisać i przetestować funkcję, która usuwa z listy napisów napis z zadanej pozycji "p". Pozycje w liście liczymy od 0. Lista dwukierunkowa niecykliczna bez wartownika

6. Napisać i przetestować funkcję, która usuwa z listy napisów napis z zadanej pozycji "p". Pozycje w liście liczymy od 0. Lista dwukierunkowa cykliczna z wartownikiem.

7. Napisać i przetestować funkcję, która wstawia do listy napisów nowy napis pomiędzy napisy na pozycjach "p" i "p+1", gdzie "p" jest pewną zadaną wartością". Pozycje w liście liczymy od 0. W przypadku braku pozycji "p" na liście - wstawiamy na koniec listy. Lista dwukierunkowa niecykliczna bez wartownika

8. Napisać i przetestować funkcję, która wstawia do listy napisów nowy napis pomiędzy napisy na pozycjach "p" i "p+1", gdzie "p" jest pewną zadaną wartością". Pozycje w liście liczymy od 0. W przypadku braku pozycji "p" na liście - wstawiamy na koniec listy. Lista dwukierunkowa cykliczna z wartownikiem.

9. Napisać i przetestować funkcję, która tworzy kopię listy napisów. Na utworzonej kopii jest taka sama kolejność napisów jak na liście oryginalnej. Lista dwukierunkowa niecykliczna bez wartownika

10. Napisać i przetestować funkcję, która tworzy kopię listy napisów. Na utworzonej kopii jest taka sama kolejność napisów jak na liście oryginalnej. Lista dwukierunkowa cykliczna z wartownikiem.

11. Napisać i przetestować funkcję, która tworzy kopię listy napisów ale zmieniając ich kolejność na odwrotną, czyli na utworzonej kopii kolejność napisów jak odwrotna niż na liście oryginalnej. Lista dwukierunkowa niecykliczna bez wartownika

12. Napisać i przetestować funkcję, która tworzy kopię listy napisów ale zmieniając ich kolejność na odwrotną, czyli na utworzonej kopii kolejność napisów jak odwrotna niż na liście oryginalnej. Lista dwukierunkowa cykliczna z wartownikiem.

13. Napisać i przetestować funkcję, która dla danej listy napiów przestawia ostani napis na początek listy. Na przykład, lista [a, b, c, d] zmieni się na [d, a, b, c] przy czym tylko węzeł listy zawierający ostatni napis jest przestawiany a pozostałe napisy nie są przepisywane. Zakładamy, że lista ma co najmniej 2 napisy. Lista dwukierunkowa niecykliczna bez wartownika

14. Napisać i przetestować funkcję, która dla danej listy napisów przestawia ostani napis na początek listy. Na przykład, lista [a, b, c, d] zmieni się na [d, a, b, c] przy czym tylko węzeł listy zawierający ostatni napis jest przestawiany a pozostałe napisy nie są przepisywane. Zakładamy, że lista ma co najmniej 2 napisy. Lista dwukierunkowa cykliczna z wartownikiem.

15. Napisać i przetestować funkcję, która dla danej listy napiów przestawia pierwszy napis na koniec listy. Na przykład, lista [a, b, c, d] zmieni się na [b, c, d, a] przy czym tylko węzeł listy zawierający pierwszy napis jest przestawiany a pozostałe napisy nie są przepisywane. Zakładamy, że lista ma co najmniej 2 napisy. Lista dwukierunkowa niecykliczna bez wartownika

16. Napisać i przetestować funkcję, która dla danej listy napisów przestawia pierwszy napis na koniec listy. Na przykład, lista [a, b, c, d] zmieni się na [b, c, d, a] przy czym tylko węzeł listy zawierający pierwszy napis jest przestawiany a pozostałe napisy nie są przepisywane. Zakładamy, że lista ma co najmniej 2 napisy. Lista dwukierunkowa cykliczna z wartownikiem.

17. Napisać i przetestować funkcję, która dla danej listy napisów i pozycji "p" odetnie od listy jej końcówkę pozostawiając tylko napisy do pozycji "p" włącznie (jeżeli lista jest krótsza i nie ma pozycji "p" to zostaje bez zmiany). Pozycje w liście liczymy od 0. Lista dwukierunkowa niecykliczna bez wartownika

18. Napisać i przetestować funkcję, która dla danej listy napisów i pozycji "p" odetnie od listy jej końcówkę pozostawiając tylko napisy do pozycji "p" włącznie (jeżeli lista jest krótsza i nie ma pozycji "p" to zostaje bez zmiany). Pozycje w liście liczymy od 0. Lista dwukierunkowa cykliczna z wartownikiem.