Algorytmy i Struktury Danych 2023/24 – Ćwiczenia

Podstawowe informacje

Kurs ten przeznaczony jest dla studentów 2 roku (4 semestru) studiów I stopnia na kierunku Informatyka Algorytmiczna. Są to ćwiczenia do wykładu dra Zbigniewa Gołębiewskiego.


Zajęcia odbywają się w środy w godzinach 1515–1655 w sali 34 bud. C-4.


Listy zadań, zasady zaliczenia oraz literatura podane są na stronie kursu.

Opis kursu (karta przedmiotu): INP002263Wcl.pdf

Zasady zaliczenia ćwiczeń

Na ćwiczeniach obowiązują następujące zasady ustalone wspólnie z wykładowcą.

  1. Zasadniczym celem ćwiczeń jest ułatwienie studentom samodzielnej pracy nad opanowaniem materiału w czasie całego semestru. Ocena z ćwiczeń jest oceną jakości i intensywności pracy studenta w czasie semestru.
  2. Wykładowca ogłasza z odpowiednim wyprzedzeniem listy zadań do samodzielnego rozwiązania przed zajęciami. Na ćwiczeniach studenci prezentują rozwiązania zadań. W trakcie rozwiązywania wyjaśniane są wątpliwości dotyczące rozwiązania oraz przedstawiane są alternatywne rozwiązania.
  3. Za zaprezentowanie poprawnego rozwiązania zadania na ćwiczeniach student otrzymuje od 1 do 4 pkt. z aktywności, w zależności od jakości rozwiązania lub trudności zadania. Punkty z aktywności doliczane są do końcowej punktacji z ćwiczeń.
  4. W przypadku braku chętnych do zaprezentowania rozwiązań, decyzję odnośnie wyboru zadań do rozwiązania podczas zajęć podejmuje prowadzący ćwiczenia.
  5. Na ćwiczeniach odbędą się kartkówki przeprowadzane w czasie zajęć i punktowane w skali od 0 do 100 pkt. Materiałem obowiązującym na kartkówkach jest materiał z wszystkich poprzednich ćwiczeń od początku semestru. Kartkówki mogą być przeprowadzane bez uprzedniej zapowiedzi. Nieusprawiedliwiona nieobecność na kartkówce daje 0 pkt. W przypadku usprawiedliwionej nieobecności, zaległą kartkówkę należy napisać w najbliższym możliwym terminie wskazanym przez prowadzącego.
  6. Odpowiedzi na kartkówkach, których autorstwa prowadzący nie może ustalić (przypadek, gdy studenci porozumiewają się w trakcie kartkówki bądź przedkładają rozwiązania zadań o identycznej formie), nie mogą być punktowane i są traktowane jako "brak odpowiedzi".
  7. Podstawą do obliczenia końcowej punktacji z ćwiczeń (w zakresie 0–100 pkt.) jest średnia arytmetyczna punktów z kartkówek. Średnia może być podwyższona w zależności od aktywności studenta na ćwiczeniach (można uzyskać ponad 100 pkt) – patrz punkt 3.
  8. Na koniec semestru prowadzący ćwiczenia przekazuje wykładowcy końcową punktację uzyskaną przez studentów. Punktacja z ćwiczeń nie podlega poprawianiu po zakończeniu zajęć.
  9. Punktacja z ćwiczeń stanowi 25% końcowej punktacji z grupy kursów. Skala ocen oraz zasady zaliczenia grupy kursów podane są na stronie wykładowcy.

Puntky z kartkówek i aktywności

Wyniki kartkówek przeprowadzanych na ćwiczeniach oraz informacje o punktach z aktywności będą przekazywane przez platformę MS Teams (zakładka "Oceny").


UWAGA nr 1.
Z wynikami kartkówek można się nie zgadzać osobiście w trakcie konsultacji, na czacie w Teamsach, ewentualnie mailowo lub – w szczególnych przypadkach – po zakończeniu zajęć. Jeśli będzie taka potrzeba, to na zajęciach po sprawdzeniu zadań będę omawiał za co odejmowałem punkty oraz przekazywał najważniejsze uwagi.


UWAGA nr 2.
Jeśli w Teamsach brakuje jakiś punktów (kartkówki, aktywność) lub punkty nie zgadzają się ze stanem faktycznym, wszelkie uwagi proszę zgłaszać na czacie (preferowany sposób), ewentulanie mailowo, po zajęciach lub na konsultacjach.

Literatura i materiały do ćwiczeń

  • S. Dasgupta, Ch. Papadimitriou , U. Vazirani, Algorithms, 1st edition, McGraw-Hill Education, 2006
  • J. Kleinberg, E. Trados, Algorithm Design, 1st edition, Pearson, 2005
  • Lecture Slides for Algorithm Design by Jon Kleinberg and Éva Tardos
  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022
  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa 2013 – polskie wydanie podręcznika
  • Introduction to Algorithms, 4th edition by T.H. Cormen et al. – book website (The MIT Press)
  • R. Sedgewick, K. Wayne, Algorithms, 4th edition, Addison-Wesley, 2011
  • Algorithms, 4th edition by R. Sedgewick and K. Wayne – book website at Princeton University (containing some additional resources, lecture notes from selected chapters, etc.)
  • D. Knuth, The Art of Computer Programming, Vol. 1-4A, Addison-Wesley, 2011
  • D. Knuth, Sztuka Programowania, wszystkie tomy, Wydawnictwa Naukowo-Techniczne WNT
  • Slajdy do wykładów dra Marcina Kika z Algorytmów i Struktur Danych (z lat ubiegłych)

Tematy ćwiczeń i omawiane zagadnienia (w przybliżeniu)

  1. zajęcia (28.02.2024.)
    • informacje wstępne – wprowadzenie do kursu, omówienie zasad zaliczenia
    • zadania 1–2 z Listy 1
    • omówione zagadnienia:
      • informacje wstępne, zasady zaliczenia, wprowadzenie do zajęć
      • złożoność czasowa i pamięciowa algorytmów – wprowadzenie
      • porównywanie asymptotycznego tempa wzrostu funkcji – wprowadzenie
  2. zajęcia (06.03.2024.)
    • zadania 3–4 z Listy 1
    • omówione zagadnienia:
      • notacja asymptotyczna \(f = O(g)\), \(f = \Omega(g)\), \(f = \Theta(g)\), \(f = o(g)\), \(f = \omega(g)\) – definicje, przykłady i podstawowe własności
      • porównywanie asymptotycznego tempa wzrostu funkcji
      • dodatkowe materiały: notacja \(f = O(g)\) – notatki prof. Jacka Cichonia
  3. zajęcia (13.03.2024.)
    • zadania 1–3 z Listy 2
    • omówione zagadnienia:
      • badanie złożoności obliczeniowej (złożoność czasowa) prostych programów
      • notacja asymptotyczna – dalsze przykłady, zastosowanie do określania złożoności algorytmów
  4. zajęcia (20.03.2024.)
    • zadania 4–7 z Listy 2, zadanie 1 z Listy 3
    • omówione zagadnienia:
      • różne techniki rozwiązywania równań rekurencyjnych – asymptotyczne oszacowania górne dla rekurencji
      • metodologia konstruowania algorytmów "divide & conquer"
      • proste algorytmy typu dziel i rządź – przeszukiwanie tablic "w stylu" binary search, mnożenie liczb, scalanie posortowanych tablic
  5. zajęcia (27.03.2024.)
    • zadania 2, 3, 5, 6 z Listy 3
    • Kartkówka 1 – rozwiązywanie równań rekurencyjnych (ograniczenia górne)
    • omówione zagadnienia:
      • metodologia konstruowania algorytmów "divide & conquer"
      • algorytm MergeSort i jego warianty
      • przeszukiwanie tablic "w stylu" binary search
      • równania rekurencyjne opisujące złożoność algorytmów "divide & conquer"
  6. zajęcia (03.04.2024.)
    • zadania 4, 7, 10 z Listy 3
    • omówione zagadnienia:
      • metodologia konstruowania algorytmów "divide & conquer" – ciąg dalszy
      • algorytm QuickSort i jego modyfikacje
      • wyznaczanie najczęściej powtarzającego się elementu w tablicy rozmiaru \(n\) – algorytm "divide & conquer" o złożoności \(O(n \log n)\); algorytm Boyer'a-Moore'a (majority vote) o złożoności \(O(n)\)
      • sortowanie w czasie liniowym
  7. zajęcia (10.04.2024.)
    • zadania 8, 9 z Listy 3, zadania 2, 3, 4 z Listy 4
    • omówione zagadnienia:
      • metodologia konstruowania algorytmów "divide & conquer" – ciąg dalszy
      • wyznaczanie spójnego przedziału liczb w tablicy rozmiaru \(n\) spełniającego podany warunek – algorytm o złożoności \(O(n \log n)\)
      • wyznaczanie mediany z dwóch posortowanych tablic rozmiaru \(n\) – algorytm o złożoności \(O(\log n)\)
      • algorytmy zliczania liczby nieporządków w danym ciągu (tablicy) \(n\) liczb o złożoności \(O(n \log n)\)
      • dowodzenie asymptotycznych ograniczeń dolnych na złożoność algorytmów – dolna granica na złożoność sortowania oraz wyszukiwania w posortowanych tablicach w comparison model
  8. zajęcia (17.04.2024.)
    • zadania 5, 6, 7 z Listy 4
    • omówione zagadnienia:
      • algorytm Select oraz jego modyfikacje – analiza złożoności czasowej
      • algorytm dla wariantu problemu range count (zliczanie liczby wartości z zadanego przedziału w zbiorze danych) wykorzystujący ideę algorytmu Counting Sort
      • drzewa przeszukiwań binarnych (BST) – wprowadzenie
      • nierekurencyjne algorytmy wypisywania kluczy w drzewie BST
  9. zajęcia (24.04.2024.)
    • zadania 1, 7 (uzupełnienie), 8 i 9 z Listy 4
    • omówione zagadnienia:
      • wpływ sposobu wyboru pivota w algorytmie Quicksort na prawdopodobieństwo uzyskania "zbalansowanego" podziału tablicy w stosunku \(\alpha n\) do \((1-\alpha) n\) dla \(\alpha \in (0,\frac{1}{2})\) – wybór losowego elementu oraz reguła median-of-3
      • algorytm Morris Tree Traversal wypisywania kluczy w drzewie BST w porządku inorder
      • wybrane własności drzew BST
      • zbalansowane drzewa BST – patrz komentarz do zadania 9. na grupie ćwiczeniowej w Teamsach