Algorytmy i struktury danych - Bioinformatyka


Zajęcia laboratoryjne kończą się zaliczeniem, na którego ocenę składają się oceny z 5 zadań (programy i sprawozdania) oraz 2 kolokwiów (waga 2x większa niż dla zadań). Zadania studenci wykonują w grupach 2-osobowych.
Za każdy program mozna uzyskać max. 3 punkty, za sprawozdanie max. 2 punkty. SpóŸnienie z oddaniem programu karane jest -0.5 punkta za każdy tydzień, a z oddaniem sprawozdanie -0.1 za każdy dzień spóznienia.
Obie osoby z grupy muszą być obecne przy oddawaniu każdego zadania (wyjątek - usprawiedliwienie lekarskie). Prowadzący wybiera, która osoba będzie odpowiadała na pytania związane z programem lub/i sprawozdaniem.

Plan zajęć

Wymagania do sprawozdań


Zadania zaliczeniowe


Zadanie pierwsze (Algorytmy sortowania)

Termin zaliczenia programu (+ wykresy):19.03.2018; sprawozdanie dostarczone mailem (pdf): 26.03.2018
Dla 10 różnych wartości n (dobrane wartości tak, żeby można było dokonać pomiaru czasu) utwórz następujące wykresy t=f(n) Zaimplementuj algorytm quicksort rekurencyjnie. Porównaj różne sposoby wyboru klucza do porównania: skrajnie prawego lub losowo wybranego elementu ciągu. Utwórz 2 wykresy porównujące efektywność działania algorytmów w zależności od wyboru różnego klucza.
Do sprawozdania: Jaka jest złożoność badanych algortymów? Czy rozkład danych wejściowych wpływa na działanie algorytmu (najgorsze, najlepsze przypadki)?

Zadanie drugie (Złożone struktury danych)

Termin zaliczenia zadania + wykresy - 16.04.2018; sprawozdanie dostarczone mailem (pdf) -23.04.2018
Wygeneruj n-elementowe ciągi liczb naturalnych (10 różnych wartości n, które mają być tak dobrane, żeby można było dokonać pomiaru czasu). Liczby mają być losowo ułożone i nie mogą się powtarzać.

Zaimplementuj poszczególne funkcje operujące na listach: Zaimplementuj poszczególne funkcje operujące na drzewach AVL: Dokonaj pomiaru czasu następujacych operacji Utwórz 3 wykresy t=f(n) (dla każdej operacji osobny) porównując czas działania poszczególnych operacji na różnych strukturach dynamicznych: w liœcie oraz w wyważonym drzewie poszukiwań binarnych (AVL).
DO SPRAWOZDANIA: Sformuuj wnioski dotyczące operacji wykonywanych na różnych strukturach. Oszacuj złożoność obliczeniową poszczególnych operacji dla wszystkich struktur. Jakie zastosowanie mogą znaleźć drzewa BST i AVL? W jakim celu wyważa się drzewa?

Zadanie trzecie (Algorytmy grafowe)

Termin zaliczenia zadania + wykres - 07.05.2018; sprawozdanie mailem z wykresami (pdf)- 14.05.2018


Zadanie czwarte (Algorytmy z powracaniem)

Termin zaliczenia zadania + wykresy; sprawozdanie mailem (pdf)-
Należy wykonać obie części zadania: A oraz B

Część A Szukanie cyklu Hamiltona i Eulera w grafie hamiltonowskim (i eulerowskim)
Część B - należy wykonać jeden z dwóch wariantów
Cykl Eulera jest to cykl przechodzący przez wszystkie krawędzie grafu dokładnie jeden raz, natomiast cykl Hamiltona jest to cykl przechodzący przez wszystkie wierzchołki grafu dokładnie jeden raz.

Zadanie piąte (Problem plecakowy)

Termin zaliczenia zadania (program + wykresy)

Wyjeżdżając na wycieczkę musisz spakować plecak o maksymalnej pojemności C. Do plecaka spakuj takie przedmioty, aby ich wartość była jak największa, a jednocześnie ich objętość nie przekroczyła pojemności plecaka. Wyznacz te elementy za pomocą algorytmu programowania dynamicznego oraz algorytmu brute force.