Algorytmy i struktury danych


Radosław Ziemann
mail: Radoslaw.Ziemann@ug.edu.pl
konsultacje: środa 12.00-13.00, proszę o mail potwierdzający chęć udziału w konsultacjach


INFORMACJE ORGANIZACYJNE:

Grupa 4: wtorek 12.15-13.45, s. 3.13

Dopuszczalne są 2 nieusprawiedliwione nieobecności. Nieobecności trzeba usprawiedliwiać na pierwszych zajęciach po zwolnieniu.

OCENA KOŃCOWA O składa się z 2 składowych: punktów za programy P oraz punktów za sprawdziany S, gdzie P=~70%O i S=~30%O.

PRGRAMY:
Programy piszemy samodzielnie, będą sprawdzane programem antyplagiatowym.
Programy są oceniane w 2 etapach. Najpierw należy w odpowiednim terminie przesłać kod żródłowy na portal edukacyjny, a następnie zgłosić się na zajęciach do jego osobistego omówienia.
Programy można pisać w dowolnym języku programowania, przy czym preferowane języki to:
python, C/C++, Java.
W przypadku wyboru innych języków należy powiadomić o tym mailowo prowadzącego zajęcia w pierwszym tygodniu zajęć.
Sprawdziany będą zapowiedziane tydzień wcześniej.
Nie można ich poprawiać.
Po okazaniu usprawiedliwienia można umówić się na NAJBLIŻSZE konsultacje w celu napisania zaległego sprawdzianu


ZADANIA:


1. (21.02.2023) Eksperymentalne badanie złożoności czasowej algorytmów, Termin: 28.02.2023, godz 12.00

Zadanie z1.1 (2 punkty)

W pliku czas.py znajdują się definicje pięciu funkcji: f1, f2, ... , f5 oraz pomiar sprawdzający, czy rzeczywisty czas działania funkcji f1(n) (wyliczony w zmiennej Tn) dla różnych wartości n (równych 2000, 4000, 8000, 16000, 32000) zmienia się zgodnie z przebiegiem funkcji liniowej (Fn = n). Otrzymane wyniki interpretujemy następująco: funkcja Fn dobrze opisuje prawdziwy czas Tn funkcji f1, jeżeli ilorazy Fn/Tn są mniej więcej takie same dla wszystkich wartości n.

Wykonać podobne pomiary dla pozostałych funkcji, dobierając odpowiednie funkcje Fn. Aby dobrać odpowiednią funkcję Fn trzeba przeanalizować kod; np. jeżeli mamy 4 zagnieżdżone pętle, każda długości n, to można się spodziewać, że czas ich działania będzie się zmieniał jak funkcja n4.

Jako rozwiązanie przesłać kod programu wykonującego pomiary z dołączonymi wynikami wygenerowanymi przez ten program dla wszyskich pięciu funkcji. Wyniki te można dołączyć np. jako komentarz na końcu kodu programu.

Zadanie z1.2 (2 punkty)

Zaimplementuj dwie różne funkcje, które dla ustalonej zero-jedynkowej macierzy kwadratowej M rozmiaru n×n wyznaczają rozmiar jej największej podmacierzy zawierającej same jedynki (interpretując to graficznie – pole największego prostokątąta złożonego z samych jedynek). Oszacuj złożoność czasową zaimplementowanych funkcji, a następnie w oparciu o eksperymentalny pomiar czasu działania z zadania z1.1 przetestuj doświadczalnie zaproponowane oszacowania, np. dla n = 10, 100, 1000. Przykładowy pseudokod rozwiązujący to zadanie:

max=0
for x1=1 to n:
    for y1=1 to n:
        for x2=n downto x1
            for y2=n downto y1
                local_max=0
                for x=x1 to x2
                    for y=y1 to y2
                        local_max+=M[x][y]
                if local_max==(x2-x1+1)*(y2-y1+1) and local_max>max
                    max=local_max

Podobnie jak w poprzenim zadaniu, jako rozwiązanie należy przesłać kod programu wykonującego pomiary z dołączonymi wynikami wygenerowanymi przez ten program.



2. (28.02.2023) Heapsort Termin: 7.03.2023, godz 12.00
Zadania

Sprawdzian za tydzień (7.03)

3. (7.03.2023) Quicksort Termin: 21.03.2023, godz 12.00
Zadania

Ważne: należy wybrać tylko jedno zadanie spośród z3.2, z3.3, z3.4, z3.5.

Sprawdzian za tydzień (14.03)

3.1 (14.03.2023) Quicksort - kontynuacja

4. (21.03.2023) Listy dowiązaniowe Termin: 4.04.2023, godz 12.00
Zadania

Ważne: należy wybrać tylko jedno zadanie spośród z4.1, z4.2

4.1 (28.03.2023) Listy - kontynuacja

5. (4.04.2023) Haszowanie - metoda łańcuchowa Termin: 18.04.2023, godz 12.00
Zadania

6. (18.04.2023) Haszowanie - adresowanie otwarte Termin: 9.05.2023, godz 12.00
Zadania

Sprawdzian za tydzie (25.04)