pantonczyk/Algorytmy

Implementacja w C# bardzo wielu algorytmów i struktur danych - patrz README.md

Algorytmy

Znajduje się tutaj dosyć spore repo z kodem i materiałami pomocnymi przy zaliczaniu przedmiotu Algorytmy i Danych Struktury. Jest parę wybrakowanych kodów, z czasem te repozytorium stanie się trochę deprecated, więc aby przeciwdziałać wszechobecnej rosnącej entropii zachęcam do aktualizacji tegoż kodu poprzez Forkowanie projektu i tworzenie Pull requestów.

Teorya - >>KLIK<<

Teoria, tzn. krótkie notatki, screeny z prezentacji, są dostępne tutej: >>KLIK<<

Kolos nr 2

• Zadania przykładowe
• Kolos z poprzedniego roku (zima 2016/2017)
• Kolos właściwy (zima 2017/2018)

---

Lab 8 - Lista, Stos, Kolejka

• Stos (LIFO)
  • Sprawdzenie poprawności nawiasów w wyrażeniu za pomocą stosu
• Kolejka (FIFO)
  • Kolejka (zbudowana za pomocą dwóch stosów)
• Lista jednokierunkowa
  • Lista posortowana (jednokierunkowa)
• Lista dwukierunkowa

Lab 9 - Drzewa, Drzewa binarne

• Drzewo
  • Drzewo potomków Adama
• Drzewo binarne
• Drzewo Trie
• Do dokończenia Drzewo Huffmana - >>ZOBACZ OPIS<< - rodzaj drzewa binarnego, gdzie znakom które występują najczęściej powinniśmy przyporządkować kody najkrótsze, które występują najrzadziej kody dłuższe.

Lab 10 - Kopiec binarny

• Kopiec binarny - implementacja tablicowa (budowanie kopca, liczenie wysokości, ilości liści, itp)
• Sortowanie przez kopcowanie - implementacja tablicowa
• Kopiec binarny - implementacja jako drzewo binarne
• Kolejka Priorytetowa

Lab 11 - Drzewa BST

• Drzewo BST - 500 linii kodu w tej zdradzieckiej strukturze... ;)

Lab 12 - Zbiory, Hashowanie

• Zbiór na wektorze charakterystycznym z adresowaniem bezpośrednim
• Zbiór na tablicy z haszowaniem z metodą łańcuchową - korzysta z wbudowanego GetHashCode()
  • Zbiór na tablicy z haszowaniem (własnym) z metodą łańcuchową - korzysta z własnej implementacji funkcji hashującej
• Zbiór na tablicy z haszowaniem z adresowaniem otwartym - korzysta z wbudowanego GetHashCode()
• Zbiór na Hashtable z .NET - zbiór oparty o wbudowaną strukturę danych (z .NET) Hashtable
• Do dokonczenia Struktura Union-Find na tablicy z ustalonym przedziałem
  • Do dokonczenia Union-Find na liście dowiązaniowej
  • Do dokonczenia Union-Find jako drzewo

Lab 13 - Grafy

• Graf nieskierowany - (macierz sąsiedztw, listy sąsiedztwa, BFS, DFS)
• Algorytm Dijkstry - rozwiązanie Karwosia
• Do dokonczenia Algorytm Prima - minimalne drzewo rozpinające

---

Sortowanie - to do

• MergeSort (sortowanie przez scalanie)
• QuickSort (sortowanie szybkie)
• Sortowanie przez wybieranie(selection sort)
• Sortowanie przez wstawianie
• BubbleSort (sortowanie bąbelkowe)
• Sortowanie przez zliczanie

Niezmienniki, O(n), złożoność algorytmów

Rekurencja, dziel i zwyciężaj

Programowanie dynamiczne vs zachłanne

• to do

---

Teoria

Krótkie notatki są dostępne tutej: >>KLIK<<