# Kolokwium

{% hint style="warning" %}

* [**Arkusz odpowiedzi dla wersji A kolokwium**](https://files.pw.karolpiczak.com/2019Z-AISDI-Kolokwium-A-odp.pdf)
* [**Arkusz odpowiedzi dla wersji B kolokwium**](https://files.pw.karolpiczak.com/2019Z-AISDI-Kolokwium-B-odp.pdf)
* [**Arkusz odpowiedzi dla wersji C kolokwium**](https://files.pw.karolpiczak.com/2019Z-AISDI-Kolokwium-C-odp.pdf)
* [**Arkusz odpowiedzi dla wersji D kolokwium**](https://files.pw.karolpiczak.com/2019Z-AISDI-Kolokwium-D-odp.pdf)<br>
* [**Arkusz oceniania dla wersji A/B kolokwium**](https://files.pw.karolpiczak.com/2019Z-AISDI-Kolokwium-Ocenianie-AB.pdf)
* [**Arkusz oceniania dla wersji C/D kolokwium**](https://files.pw.karolpiczak.com/2019Z-AISDI-Kolokwium-Ocenianie-CD.pdf)
  {% endhint %}

## Ćwiczenia 1

{% hint style="info" %}
Przykłady implementacji struktur listowych dostępne są w [repozytorium z materiałami do przedmiotu](https://github.com/karolpiczak-pw/2019Z-AISDI/tree/master/examples/01-list-bst).
{% endhint %}

### 1.1 **Tablica, std::array, std::vector**

{% tabs %}
{% tab title="1.1 Zakres materiału" %}

* podstawowe **operacje na tablicy/wektorze** i ich złożoność:
  * dostęp,
  * wstawianie elementu (na końcu/w środku),
  * usuwanie elementu (z końca/ze środka),
  * wyszukiwanie elementu o określonej wartości
* różnica między `std::vector::size()` a `std::vector::capacity()`,
* wykorzystanie **iteratorów**
  {% endtab %}
  {% endtabs %}

### 1.2 **Lista jedno- i dwukierunkowa**

{% tabs %}
{% tab title="1.2 Zakres materiału" %}

* podstawowe **operacje na liście** i ich złożoność:
  * dostęp,
  * wstawianie elementu,
  * usuwanie elementu,
  * wyszukiwanie elementu o określonej wartości
* **wyszukiwanie ze strażnikiem**
  {% endtab %}

{% tab title="1.2 Materiały pomocnicze" %}
{% hint style="info" %}
**Ogólne:**

* [Linked list data structure (Geeks for Geeks)](https://www.geeksforgeeks.org/data-structures/linked-list/)

**Wykorzystanie strażnika:**

* [Sentinel node (Wikipedia)](https://en.wikipedia.org/wiki/Sentinel_node)
* [Using sentinel nodes (Stack Overflow)](https://stackoverflow.com/a/5384593/308759)

**Wizualizacje:**

* [List (VisuAlgo)](https://visualgo.net/en/list)
  {% endhint %}
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="1.2 Zadania:" %}

{% endtab %}

{% tab title="1.2.1" %}
Dany jest następujący szkielet klasy listy jednokierunkowej:

```cpp
struct Node {
    Node* next;
    int value;
};

class LinkedList {
  public:
    int length;
    Node* head;

    LinkedList();

    void erase_after(int pos);  // usuwa elem. za pozycją pos
    void insert_after(int pos, int value);  // wstawia elem. za pozycją pos
    void pop_front();  // usuwa pierwszy element
    void push_front(int value);  // wstawia element na początek listy
};
```

Zaimplementuj brakujące metody.
{% endtab %}

{% tab title="1.2.2" %}
Zaimplementuj metodę, która dla listy jednokierunkowej zwróci trzeci element od końca. Załóż, że długość listy nie jest znana.
{% endtab %}

{% tab title="1.2.3" %}
Zaimplementuj metodę, która zwróci środkowy element listy jednokierunkowej. Załóż, że długość listy nie jest znana.
{% endtab %}

{% tab title="1.2.4" %}
Zaproponuj sposób odwracania listy jednokierunkowej w jednym przejściu bez tworzenia kopii wszystkich elementów.
{% endtab %}

{% tab title="1.2.5" %}
Zaproponuj sposób usuwania węzła mając tylko odwołanie do niego. Załóż, że nie jest to ostatni węzeł listy.
{% endtab %}

{% tab title="1.2.6" %}
Zaimplementuj uproszczony iterator (tylko operacje `->` i `++` ) po elementach listy. Jak wyglądałby taki iterator, gdyby miał zwracać najpierw elementy na rosnących pozycjach nieparzystych listy, a następnie na parzystych?
{% endtab %}
{% endtabs %}

### 1.3 **Kolejka (FIFO), stos (LIFO)**

{% tabs %}
{% tab title="1.3 Zakres materiału" %}

* pojęcie **abstrakcyjnego typu danych** (*abstract data type, ADT*),
* **kolejka** i **stos** jako przykłady ADT,
* implementacja funkcjonalności kolejki i stosu na bazie listy dwukierunkowej
  {% endtab %}

{% tab title="1.3 Materiały pomocnicze" %}
{% hint style="info" %}
**ADT:**

* [Queue ADT (Wikipedia)](https://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29)
* [Stack ADT (Wikipedia)](https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29)

**Wizualizacje:**

* [Queue (VisuAlgo)](https://visualgo.net/en/list?slide=5)
* [Stack (VisuAlgo)](https://visualgo.net/en/list?slide=4)
  {% endhint %}
  {% endtab %}
  {% endtabs %}

### 1.4 Binarne drzewo poszukiwań (BST)

{% tabs %}
{% tab title="1.4 Zakres materiału" %}

* **drzewo binarne**, definicja, podstawowe własności,
* **binarne drzewo poszukiwań** (*binary search tree*, *BST*):
  * podstawowe operacje i ich złożoność:
    * dostęp,
    * wyszukiwanie elementu,
    * wstawianie elementu,
    * usuwanie elementu
  * przechodzenie po węzłach drzewa:
    * in-order,
    * pre-order,
    * post-order
  * implementacja iteratora dla drzewa
    {% endtab %}

{% tab title="1.4 Materiały pomocnicze" %}
{% hint style="info" %}
**Ogólne:**

* [Binary tree (Wikipedia)](https://en.wikipedia.org/wiki/Binary_tree)
* [Binarne drzewo poszukiwań (Wikipedia)](https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84)
* [Binary search tree (Programiz)](https://www.programiz.com/dsa/breadth-first-search-tree)

**Przechodzenie drzewa:**

* [Tree traversal (Wikipedia)](https://en.wikipedia.org/wiki/Tree_traversal)
* [Binary search tree iterator (LeetCode)](https://leetcode.com/problems/binary-search-tree-iterator/solution/)

**Wizualizacje:**

* [BST (VisuAlgo)](https://visualgo.net/en/bst)
  {% endhint %}
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="1.4 Zadania" %}

{% endtab %}

{% tab title="1.4.1" %}
Narysuj binarne drzewo poszukiwań utworzone przez wstawienie w kolejności elementów:

`31, 72, 23, 44, 85, 106, 17, 28, 9, 30, 41`
{% endtab %}

{% tab title="1.4.2" %}
Zaimplementuj metody wstawiania i wyszukiwania węzła w drzewie BST.
{% endtab %}

{% tab title="1.4.3" %}
Zaimplementuj rekursywne przechodzenie po węzłach drzewa w kolejności "in-order".
{% endtab %}

{% tab title="1.4.4" %}
Zaimplementuj uproszczony iterator (tylko operacje `->` i `++` ), który będzie przechodził węzły drzewa w kolejności "in-order".
{% endtab %}

{% tab title="1.4.5" %}
Zaimplementuj w klasie drzewa BST funkcjonalność usuwania węzła o zadanej wartości.
{% endtab %}
{% endtabs %}

## Ćwiczenia 2

{% hint style="info" %}
Przykładowe implementacje omawianych algorytmów sortowania dostępne są w [repozytorium z materiałami do przedmiotu](https://github.com/karolpiczak-pw/2019Z-AISDI/tree/master/examples/02-sorting).
{% endhint %}

### 2.1 Algorytmy sortowania

{% tabs %}
{% tab title="2.1 Zakres materiału" %}
**Algorytmy:**

* sortowanie przez wybieranie (***selection sort***),
* sortowanie przez wstawianie (***insertion sort***),
* sortowanie bąbelkowe (***bubble sort***),
* sortowanie szybkie (***quicksort***),
* sortowanie przez scalanie (***merge*** ***sort***),
* sortowanie przez kopcowanie (***heapsort***),
* sortowanie kubełkowe (***bucket sort***)

**Dla przedstawionych algorytmów:**

* implementacja,
* złożoność czasowa (najlepsza, średnia, najgorsza),
* złożoność pamięciowa,
* stabilność
  {% endtab %}

{% tab title="2.1 Materiały pomocnicze" %}
{% hint style="info" %}
**Ogólne:**

* [Sorting algorithm (Wikipedia)](https://en.wikipedia.org/wiki/Sorting_algorithm)
* [Sorting stability (Wikipedia)](https://en.wikipedia.org/wiki/File:Sorting_stability_playing_cards.svg)
* [Sorting algorithms (O'Reilly)](https://www.oreilly.com/library/view/algorithms-in-a/9781491912973/ch04.html)

**Algorytmy:**

* [Selection sort (w3resource)](https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-5.php)
* [Bubble sort (w3resource)](https://www.w3resource.com/javascript-exercises/javascript-function-exercise-24.php)
* [Insertion sort (w3resource)](https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-6.php)
* [Quicksort (w3resource)](https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-9.php)
* [Merge sort (101computing)](https://www.101computing.net/merge-sort-algorithm/)
* [Heapsort (HackerEarth)](https://www.hackerearth.com/practice/algorithms/sorting/heap-sort/tutorial/)
* [Bucket sort (Programiz)](https://www.programiz.com/dsa/bucket-sort)

**Wizualizacje:**

* [Sorting (sorting.at)](http://sorting.at/)
* [Sorting (VisuAlgo)](https://visualgo.net/en/sorting)
* [Comparison sorting (USF)](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
* [Sorting algorithms (toptal)](https://www.toptal.com/developers/sorting-algorithms)
* [Bucket sort (USF)](https://www.cs.usfca.edu/~galles/visualization/BucketSort.html)
  {% endhint %}
  {% endtab %}
  {% endtabs %}

## Ćwiczenia 3

### 3.1 Drzewa

{% tabs %}
{% tab title="3.1 Zakres materiału" %}

* drzewa BST zrównoważone i niezrównoważone,
* **rotacje drzew,**
* **drzewa splay**:
  * implementacja i złożoność obliczeniowa:
    * operacja *splay*,
    * wyszukiwanie elementu,
    * wstawianie elementu,
    * usuwanie elementu,
  * zastosowania drzewa splay, zalety i wady
* **drzewa AVL**:
  * wysokość, współczynnik wyważenia,
  * operacje równoważenia drzewa AVL,
  * implementacja i złożoność obliczeniowa:
    * wyszukiwanie elementu,
    * wstawianie elementu,
    * usuwanie elementu
      {% endtab %}

{% tab title="3.1 Materiały pomocnicze" %}
{% hint style="info" %}
**Zrównoważenie drzewa BST:**

* [Wyważanie drzewa (Wikipedia)](https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84#Wywa%C5%BCanie_drzewa)

**Rotacje:**

* [Tree rotation (Wikipedia)](https://en.wikipedia.org/wiki/Tree_rotation)

**Drzewa splay:**

* [Drzewo splay (Wikipedia)](https://pl.wikipedia.org/wiki/Drzewo_splay)
* [Splay tree rotation (Stack Exchange)](https://cs.stackexchange.com/q/1229/8837)
* [Self-Adjusting Binary Search Trees paper (CMU)](https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf)
* [Splay trees lecture notes (Berkeley)](https://people.eecs.berkeley.edu/~jrs/61b/lec/36)

**Drzewa AVL:**

* [AVL tree (Wikipedia)](https://en.wikipedia.org/wiki/AVL_tree)
* [AVL trees (CodesDope)](https://www.codesdope.com/course/data-structures-avl-trees/)

**Wizualizacje:**

* [Splay tree (USF)](https://www.cs.usfca.edu/~galles/visualization/SplayTree.html)
* [AVL (VisuAlgo)](https://visualgo.net/en/bst?slide=14)
  {% endhint %}
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="3.1 Zadania:" %}

{% endtab %}

{% tab title="3.1.1" %}
Stwórz dwa drzewa BST przez wstawianie w kolejności następujących wartości:

`A: 40, 20, 60, 10, 30, 50, 70`

`B: 10, 20, 30, 40, 50, 60, 70`

Porównaj złożoność podstawowych operacji dla obydwu drzew.

Następnie dla drzewa niezrównoważonego **B** wykonaj kolejno operacje rotacji:

* `L(40)`
* `L(30)`
* `L(20)`
* `L(10)`
* `L(20)`

{% hint style="info" %}
Zapis `L(R)` oznacza rotację lewą, dla której korzeniem jest węzeł o wartości `R`.
{% endhint %}
{% endtab %}

{% tab title="3.1.2" %}
Dane jest drzewo splay o takiej samej strukturze jak drzewo A z zadania 1.

Wykonaj w kolejności następujące operacje:

* znajdź element o wartości `30`,
* znajdź element o wartości `50`,
* wstaw element o wartości `25`,
* wstaw element o wartości `22`,
* usuń element o wartości `50`,
* usuń element o wartości `25`.
  {% endtab %}

{% tab title="3.1.3" %}
Stwórz drzewo AVL przez wstawianie kolejno wartości:

`10, 20, 30, 40, 50, 60, 70`

Na stworzonym drzewie przeprowadź operacje:

* wstaw element o wartości `55`,
* wstaw element o wartości `52`,
* usuń element o wartości `52`,
* usuń element o wartości `70`.
  {% endtab %}
  {% endtabs %}

## Ćwiczenia 4

{% hint style="info" %}
Przykładowe implementacje omawianych kopców dostępne są w [repozytorium z materiałami do przedmiotu](https://github.com/karolpiczak-pw/2019Z-AISDI/tree/master/examples/04-heaps).
{% endhint %}

### 4.1 Kopce

{% tabs %}
{% tab title="4.1 Zakres materiału" %}

* kolejka priorytetowa (***priority queue***, *ADT*),
* **kopiec binarny**:
  * własność kopca ***min-heap***, ***max-heap***,
  * reprezentacja tablicowa kopca (*implicit data structure*),
  * implementacja i złożoność obliczeniowa operacji:
    * dostęp do najmniejszego elementu,
    * wstawianie nowego elementu,
    * usuwanie najmniejszego elementu,
    * budowa kopca:
      * metoda Williamsa (sukcesywne wstawianie elementów),
      * metoda Floyda (przywracanie własności kopca dla tablicy)
* **kopce** ***d*****-arne**:
  * *3*-heap (*ternary heap*) i *4*-heap (*quaternary heap*),
  * zalety i wady zastosowania arności wyższego rzędu,
* **kopiec dwumianowy**:
  * kopiec dwumianowy jako przykład kopca złączalnego (***mergeable heap***),
  * własności kopca dwumianowego,
  * implementacja i złożoność obliczeniowa operacji:
    * dostęp do najmniejszego elementu,
    * wstawianie nowego elementu,
    * usuwanie najmniejszego elementu,
    * scalanie kopców
* **kopiec Fibonacciego**:
  * implementacja i złożoność obliczeniowa operacji:
    * dostęp do najmniejszego elementu,
    * wstawianie nowego elementu,
    * usuwanie najmniejszego elementu,
    * scalanie kopców
      {% endtab %}

{% tab title="4.1 Materiały pomocnicze" %}
{% hint style="info" %}
**Ogólne:**

* [Priority queue ADT (Wikipedia)](https://en.wikipedia.org/wiki/Priority_queue)
* [Heap (Wikipedia)](https://en.wikipedia.org/wiki/Heap_%28data_structure%29)
* [Implicit data structure (Wikipedia)](https://en.wikipedia.org/wiki/Implicit_data_structure)

**Kopiec binarny:**

* [Binary heap (Wikipedia)](https://en.wikipedia.org/wiki/Binary_heap)
* [Building a heap in O(n) time (Stack Overflow)](https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity)
* [Binary heap (Brilliant)](https://brilliant.org/wiki/binary-heap/)

**Kopce** ***d*****-arne:**

* [D-ary heap (Wikipedia)](https://en.wikipedia.org/wiki/D-ary_heap)
* [Binary heap vs d-ary heap (Stack Overflow)](https://stackoverflow.com/questions/29126428/binary-heaps-vs-d-ary-heaps)
* [Ternary and quaternary heaps (Stack Overflow)](https://stackoverflow.com/questions/48843677/why-dont-we-use-ternary-or-quaternary-heaps)

**Kopiec dwumianowy:**

* [Binomial heap (Wikipedia)](https://en.wikipedia.org/wiki/Binomial_heap)
* [Binomial heap (Brilliant)](https://brilliant.org/wiki/binomial-heap/)
* [Binomial heap (Growing with the Web)](https://www.growingwiththeweb.com/data-structures/binomial-heap/overview/)

**Kopiec Fibonacciego:**

* [Fibonacci heap (Wikipedia)](https://en.wikipedia.org/wiki/Fibonacci_heap)
* [Fibonacci heap (Brilliant)](https://brilliant.org/wiki/fibonacci-heap/)
* [Fibonacci heap lecture notes (Princeton)](https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf)

**Wizualizacje:**

* [Heap (VisuAlgo)](https://visualgo.net/en/heap)
* [Heap (USF)](https://www.cs.usfca.edu/~galles/visualization/Heap.html)
* [Binomial heap (USF)](https://www.cs.usfca.edu/~galles/visualization/BinomialQueue.html)
* [Fibonacci heap (USF)](https://www.cs.usfca.edu/~galles/visualization/FibonacciHeap.html)
  {% endhint %}
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="4.1 Zadania:" %}

{% endtab %}

{% tab title="4.1.1" %}
Zapisz w reprezentacji tablicowej drzewo binarne następującej postaci:

![](/files/-LuZsfIqxE_WvFBFo9bA)
{% endtab %}

{% tab title="4.1.2" %}
Dla zapisu tablicowego:

`[95, 80, 85, 40, 70, 90, 50, 30, 10, 20]`

narysuj zupełne drzewo binarne. Czy drzewo to przedstawia kopiec typu *max-heap*?
{% endtab %}

{% tab title="4.1.3" %}
Do pustego **kopca binarnego** ***max-heap*** wstaw w kolejności elementy o wartościach klucza:

`43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40`

Następnie trzykrotnie wykonaj operację usunięcia największego elementu z kopca.

Zilustruj stan kopca po każdym kroku.
{% endtab %}

{% tab title="4.1.4" %}
Z podanej tablicy stwórz **kopiec binarny typu** ***max-heap*** metodą Floyda (przywracanie własności kopca kolejnym poddrzewom):

`[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]`

Zlicz ilość wykonanych operacji, porównaj z metodą tworzenia kopca przez wstawianie.
{% endtab %}

{% tab title="4.1.5" %}
Do pustego **kopca 3-arnego (*****ternary heap*****) typu** ***max-heap*** wstaw w kolejności elementy o wartościach klucza:

`43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40`

Następnie trzykrotnie wykonaj operację usunięcia największego elementu z kopca.

Zilustruj stan kopca po każdym kroku.
{% endtab %}

{% tab title="4.1.6" %}
Do pustego **kopca dwumianowego typu** ***min-heap*** wstaw w kolejności elementy o wartościach klucza:

`43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40`

Następnie trzykrotnie wykonaj operację usunięcia najmniejszego elementu z kopca.

Zilustruj stan kopca po każdym kroku.
{% endtab %}

{% tab title="4.1.7" %}
Do pustego **kopca Fibonacciego typu** ***min-heap*** wstaw w kolejności elementy o wartościach klucza:

`43, 24, 11, 47, 13, 67, 59, 95, 29, 17, 54, 40`

Następnie trzykrotnie wykonaj operację usunięcia najmniejszego elementu z kopca.

Zilustruj stan kopca po każdym kroku.

Porównaj stany przejściowe kopca stworzonego na bazie poniższego ciągu operacji:

* `push(43)`,
* `push(24)`,
* `push(11)`,
* `push(47)`,
* `pop()`,
* `push(13)`,
* `push(67)`,
* `pop()`,
* `push(59)`,
* `push(95)`,
* `pop()`,
* `push(29)`,
* `push(17)`,
* `pop()`,
* `push(54)`,
* `pop()`,
* `push(40)`.
  {% endtab %}
  {% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://pw.karolpiczak.com/dydaktyka/2019z-aisdi-cwiczenia/kolokwium.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.