Algorytmy i struktury danych


Radosław Ziemann
mail: Radoslaw.Ziemann@ug.edu.pl
konsultacje: czwartek 12.00-13.00, z powodu epidemii konsultacje odbywają się drogą mailową, jesli to nie wystarczy mozna umówić się na MSTeams


INFORMACJE ORGANIZACYJNE:

Grupa 3: poniedziałek 12.15-13.45
Grupa 4: wtorek 10.30-12.00

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. (7/8.03.2022) Eksperymentalne badanie złożoności czasowej algorytmów, Termin: 14/15.03.2022

Wstęp

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) Wykonać podobne pomiary dla pozostałych funkcji, dobierając odpowiednie funkcje Fn. Funkcja Fn "dobrze" opisuje prawdziwy czas Tn danej funkcji, jeżeli ilorazy Fn/Tn są mniej więcej takie same dla wszystkich wartości n.

Jako rozwiązanie przesłać kod programu wykonującego pomiary z dołączonymi wynikami wygenerowanymi przez ten program dla wszystkich pięciu funkcji. Wyniki te można dołączyć np. jako komentarz na końcu kodu programu.
Dodatkowo proszę przesłać wykresy uwzględniające powyższe dane (zmienna x = rozmiar wejścia. y = czas wykonanaia), odpowiednio dla każdej funkcji. Można je wykonać np. za pomocą programu gnuplot


2. (14/15.03.2022) Sortowanie przez kopcowanie, Termin: 21/22.03.2022

Za tydzień (21/22.03) sprawdzian z heapsort.

Sortowanie przez kopcowanie (Heap-sort)

Zadanie z2.1 Sprawdź, czy ciąg (23, 17, 14, 6, 13, 10, 1, 5, 7, 12) ma własność kopca typu max?

Zadanie z2.2 Zademonstruj kolejne kroki działania procedury budującej kopiec z elementów ciągu A = [28, 6, 11, 12, 17, 8, 7, 18, 12, 14, 23]. Następnie zilustruj kilka obrotów pętli sortującej przy sortowaniu kopcowym Heapsort. Użyj drzewiastej reprezentacji kopca. Zaznaczaj, które elementy kopca są ze sobą zamieniane.

Zadanie z2.3 Oszacuj czasy działania algorytmu sortowania przez kopcowanie dla ciągu A, o długości n, w którym (a) wszystkie elementy są takie same, (b) są posortowane malejąco, (c) są posortowane rosnąco.

Zadanie z2.4 (5 pkt.)

  1. Zaimplementuj omawiany na wykładzie algorytm sortowania przez kopcowanie.(4 pkt.)
  2. Zmodyfikuj funkcję Heapify tak, aby używała iteracji zamiast rekursji. (1 pkt)

Wejście. Liczby zapisane są w kolejnych wierszach pliku tekstowego.

Wyjście. Posortowane liczby z pliku wejściowego zapisane w kolejnych wierszach pliku wyjściowego.



3. (21/22.03.2022) Sortowanie szybkie, Termin: 4/5.04.2022

Sprawdzian z heapsort
Zadania
Za 2 tygodnie (4/5.04) sprawdzian z quicksort.

USTAWIENIE LIMITU REKURSJI I WĄTKÓW ( niestety może ono powodować zaburzenia w wykonywaniu programu i tym samym wpływać na wyniki szybkości wykonywania poszczególnych algorytmów, dlatego zaleca się niekorzystanie z wątków przynajmniej dla danych losowych)

import sys # trzeba dodać 2 biblioteki
import threading

sys.setrecursionlimit() # w nawiasach podać jakaś dużą liczbę, np 100000
threading.stack_size() # podobnie

def sortowanie_szybkie():
# tutaj kod sortowania, funkcje quicksort i partition

sortowanie = threading.Thread(target=sortowanie_szybkie) # juz poza ciałem funkcji sortwanie_szybkie
sortowanie.start()


4. (28/29.03.2022) Sortowanie szybkie - kontynuacja

Sprawdzian z quicksort za tydzień
Zadanie tablicowe z quicksorta
Zakończenie sprawdzania programów z heapsortem

5. (4/5.04.2022) Listy dowiązaniowe, Termin: 11/12.04.2022

Zadania

6. (11/12.04.2022) Tablice z haszowaniem, Termin: 25/26.04.2022

Zadania

7. (25/26.04.2022) Haszowanie z adresowaniem otwartym, Termin: 9/10.05.2022

Sprawdzian z adresowania otwartego za 2 tygodnie

Zadania

8. (9/10.05.2022) Drzewa poszukiwań binarnych BST, Termin: 23/24.05.2022

Zadania

1. Zadanie 7.1

2. Sprawdzian za tydzień

3. Sprawdzanie zadań z haszowania



UWAGA: Proszę dokładnie zapoznać się z nowym harmonogramem laboratoriów, mogą jeszcze zajść jakieś zmiany

9. Grupa 3: (16.05.2022), Najdłuższy wspólny podciąg (NWP), Nowy termin: 6.06.2022

  1. Sprawdzian z drzew binarnych

  2. Zadanie 9.1

  3. Zadania

  4. Sprawdzanie zadań z haszowania

9. Grupa 4: (27.05.2022), Zajęcia online na Teams, 12.15, Najdłuższy wspólny podciąg (NWP), Termin: 7.06.2022
Link: https://teams.microsoft.com/l/meetup-join/19%3a0e5836caa864470aa4fe98e81c70ca04%40thread.tacv2/1613654164904?context=%7b%22Tid%22%3a%222d9a5a9f-69b7-4940-a1a6-af55f35ba069%22%2c%22Oid%22%3a%22f03d1fc3-048f-4f35-9ab6-ccbae865178c%22%7d

  1. Zadanie 9.1

  2. https://webwhiteboard.com/board/AIMD9TUkf9qh0epyLZ0hS3tzxweTl4gg/

  3. Zadania

  4. Sprawdzanie zadań z haszowania

10. Grupa 3: (30.05.2022), Najdłuższy wspólny podciąg (NWP) c.d.

  1. Sprawdzian z NWP

  2. Sprawdzanie zadań z BST

10. Grupa 4: (31.05.2022), Najdłuższy wspólny podciąg (NWP) c.d.

  1. Sprawdzian z drzew binarnych

  2. Sprawdzian z NWP

  3. Sprawdzanie zadań z BST

11. (6/7.06.2022) Grafy

1. Sprawdzanie zadań z NWP

12. (13/14.06.2022) Grafy, Wystawianie ocen

\ Oceny:
5, >= 41
4.5, >= 36.5
4, >= 32
3.5, >= 27,5
3, >= 23