Propozycje tematów projektów zaliczeniowych

UWAGI OGÓLNE

W celu zaliczenia ćwiczeń z AiSD należy:
(1) zaliczyć 10 zestawów zadań,
(2) zaliczyć dwa kolokwia,
(3) zaliczyć projekt programistyczny w C++ [kod plus dokumentacja (PDF, README.md, HTML); minimum 100 wierszy kodu; nie używać 'using namespace std;'; Makefile do kompilacji z flagami -Wall -std=c++11].

Możliwe sposoby przesyłania rozwiązań zestawów zadań:
(1) email z linkiem do repozytorium w serwisie GitHub, gdzie składowane są kody źródłowe programów,
(2) email z linkiem do archiwum ZIP w chmurze UJ,
(3) email z archiwum ZIP w załączniku.

TEMATY PROJEKTÓW

• Implementacja wielomianów na bazie list powiązanych pojedynczo (szablon, współczynniki typu T). Działania na wielomianach: dodawanie (operator+), odejmowanie (operator-), mnożenie (operator*), obliczanie wartości wielomianu (algorytm Hornera), porównywanie (operator==, operator!=), wyświetlanie. Wielomiany są równe, gdy ich różnica jest wielomianem zerowym. Klasa Term przechowuje jeden niezerowy wyraz wielomianu (c*x^n). Klasa Poly przechowuje łącze do posortowanej listy powiązanej wyrazów i implementuje działania. Przydają się funkcje clear(), is_zero(), operator[] (odczyt współczynnika przy danej potędze x), degree() (stopień wielomianu).
• Implementacja wielomianów na bazie tablic (szablon, współczynniki typu T). Działania na wielomianach: dodawanie (operator+), odejmowanie (operator-), mnożenie (operator*), obliczanie wartości wielomianu (algorytm Hornera), porównywanie (operator==, operator!=), wyświetlanie. Wielomiany są równe, gdy ich różnica jest wielomianem zerowym. Klasa Poly przechowuje tablicę współczynników i implementuje działania. Przydają się funkcje clear(), is_zero(), operator[] (odczyt współczynnika przy danej potędze x), degree() (stopień wielomianu).
• Implementacja kwaternionów podobnie do std::complex [https://en.wikipedia.org/wiki/Quaternion]. Działania na kwaternionach: dodawanie (operator+), odejmowanie (operator-), mnożenie (operator*), sprzężenie, moduł, porównywanie (operator==, operator!=), wyświetlanie.
• Obliczanie wielomianu szachowego [https://en.wikipedia.org/wiki/Rook_polynomial].
• Implementacja list z przeskokami (szablon, elementy na liście typu T) [https://en.wikipedia.org/wiki/Skip_list].
• Drzewa AVL.
• Drzewa czerwono-czarne (red-black trees).
• Drzewa splay.
• Drzewa ukorzenione o dowolnym stopniu rozgałęzień. Cormen str. 245, reprezentacja na lewo syn, na prawo brat.
• Drzewo przedziałowe, czyli drzewo binarne do przechowywania danych o przedziałach liczbowych. Cormen str. 351.
• Kopiec trójkowy.

  ---

  int heap_parent(int n) { return (n-1) / 3; }
  int heap_left(int n) { return (3 * n + 1); }
  int heap_middle(int n) { return (3 * n + 2); }
  int heap_right(int n) { return (3 * n + 3); }
  

  ---

• Wyznaczanie otoczki wypukłej, np. Graham, Jarvis, quickhull [https://en.wikipedia.org/wiki/Convex_hull].
• Implementacja drzewa czwórkowego [https://en.wikipedia.org/wiki/Quadtree].
• Program do obsługi biblioteki (użytkownicy, książki, wypożyczanie).
• Program symulujący konta w banku. Operacje: zakładanie i usuwanie konta, wpłata, wypłata, przelew, zapis i odczyt bazy z pliku. Nie należy używać serwerów dużych baz danych, można użyć biblioteki SQLite.
• Program do rezerwacji biletów lotniczych.
• Baza danych książek, płyt, filmów, itp. (jeden typ elementów, wystarczy jedna tabela). Operacje: dodawanie, usuwanie, wyszukiwanie rekordu, wypisywanie zawartości bazy, zapis i odczyt bazy z pliku.
• Generowanie labiryntu, np. Wilson, Aldous-Broder, Kruskal, Prim [https://en.wikipedia.org/wiki/Maze_generation_algorithm]. Labirynt rozumiemy jako drzewo rozpinające dla pewnej sieci kwadratowej n × m [https://en.wikipedia.org/wiki/Lattice_graph]. Labirynt należy na końcu wyświetlić na ekranie w formie przyjaznej dla użytkownika lub zapisać do pliku, najlepiej graficznego.
• Obliczanie mediany kroczącej (ang. running median) [https://en.wikipedia.org/wiki/Moving_average#Moving_median].
• Implementacja systemu T9 (predictive text), stosowanego w telefonach komórkowych do łatwiejszego pisania tekstów za pomocą klawiatury 3x4 [https://en.wikipedia.org/wiki/T9_(predictive_text)]. Używa się 8 przycisków znaczących 2-9. Jeżeli wyświetli się kilka wyrazów, ale pierwszy nie jest tym właściwym, to klawisz '*' daje przejście do następnego wyrazu.

  +------+------+------+
  |1     |2 abc |3 def |
  +------+------+------+
  |4 ghi |5 jkl |6 mno |
  +------+------+------+
  |7 pqrs|8 tuv |9 wxyz|
  +------+------+------+
  | *    | 0    | #    |
  +------+------+------+