Algorytmy i struktury danych

Zagadnienia do Egzaminu z algorytmów

Listy zadań na rok 2013

• Lista 1
  
• Lista 2
  
• Lista 3
  
• Lista 4
  
• Lista 5
  
• Lista 6
  

Proste algorytmy

• Sito Erastotenesa - Przykład
• Wyszukiwanie binarne
• NWD
• Współczynniki Newtona
• Ciąg Fibbonacciego

Algorytmy sortujące

• Algorytmy sortujące w czasie O(n²)
• Algorytmy sortujące w czasie O(n log(n))
• Program testujący (bardzo stary)
• Szybka implementacja algorytmu MergeSort
• Selekcja w czasie liniowym

Podstawowe struktury danych

• Tablice
• Listy
• Drzewa binarne (zastosowanie rekurencji)

Zastosowanie struktur danych w implementacji klas C++

• Stos - implementacja za pomocą listy linkowanej
• Stos - implementacja za pomocą tablicy
• Kolejka dwukierunkowa - implementacja za pomocą listy podwójnie linkowanej w wersji z wartownikiem

Zaawansowane struktury danych

słowniki

• Drzewa czerwono-czarne prezentacja
• Drzewa czerwono-czarne implementacja w C++ (bez wskaźnika parent)
• Drzewa czerwono-czarne implementacja w C++
• B-drzewa
• Tablice z haszowaniem

Zadania z poprzednich lat

• Listy zadań z roku 2005: Lista 2005/2, Lista 2005/3, Lista 2005/4, Lista 2005/5,
• Listy zadań z roku 2007: Lista 2007/1, Lista 2007/2, Lista 2007/3a, Lista 2007/3b, Lista 2007/4,
• Listy zadań na rok 2008: Lista 2008/1, Lista 2008/2, Lista 2008/3, Lista 2008/4, Lista 2008/5, Lista 2008/6,
• Listy zadań na rok 2009: Lista 2009/1 , Lista 2009/2 ,
• Zadania zebrane
• Listy zadań na rok 2012: Lista 1, Lista 2, Lista 3, Lista 4.