Sorting and Searching algos

Programovani 2 Matematici, teoreticke cviceni
06.03.2024 st
07.03.2024 ct

1. Searching algos

1.2 Proč vlastně chceme řadit (i) pole?
(Dat struct ... orga)

1.4 Hledání v nesetřízeném poli 
- slozitost v nejlepsim nejhorsim a spocitat i v prumernem pripade

1.6 Hledání v setřízeném poli 
- slozitost v nejlepsim nejhorsim a spocitat 


1.10. Různé modifikace binárního vyhledávání:
- v setříděném poli určit počet výskytů dané hodnoty x
- v setříděném poli nalézt všechny prvky s danou hodnotou x (první a poslední index)
- v setříděném poli nalézt prvek s hodnotu x (pokud tam je) nebo nejbližší vyšší (pokud tam žádné x není).



3. Sorting algos
3.2 Proč řadit?

3.4 visualgo: https://visualgo.net/en
- bacha na ruzne implmentace

3.6 trackování algoritmů: insert/select/bubble sort

3.8 insert/select/bubble sort: jak vypadá: 
a] nejlepsi 
b] nejhorsi 
vstup vzhledem k poctu operaci/casove slozitosti a jake casove slozitosti to jsou

3.10
bubleSort: 
- jak rychle se a] nejvetsi prvek (když je první) a b] nejmensi (když je posledni) "dostane na své místo"? 
- buduje/obsahuje take serazenou a neserezenou posloupnost?
- je nutné mít swapp?

4. mergesortem setridte posloupnost: ...

5. 15 Sorting Algorithms in 6 Minutes (sound)
https://www.youtube.com/watch?v=kPRA0W1kECg


6.1 kolik maximalne prvku ma binarni strom v k-vrstve (vrstvy stromu vs hloubka stromu)
6.3 kolik maximalne prvku ma binarni strom o k-vrstvach
6.5 dokazte nebo vyvratte: mejme plne zaplneny binarni strom o k vrstvach; obsahuje k vrstva vice hodnot nezli cely strom bez k-te vrstvy?
6.6 Jaká je výška/hloubka plného binárního stromu obsahujících n prvků? 

6.8 Hloubka stromu mergesortu

7. Opakovani dukazu dolni sloz radicich algos zaloz na porovnani


Programování

Implementování základních algoritmů - binární vyhledávání a řazení
("aspoň jednou za život", hraní si s poli a +- jedničkové problémy)


1.1 Implementujte funkci binárního vyhledávání binarySearch(list, x)
(co funkce vrací, co vrací v případě nalezeného prvku a co v případě nenalezeného prvku?)

1.2 Pro funkci binárního vyhledávání diskutujme a navrhněme sérii testů/testovacích dat, které prověří funkčnost vaší implementace
(jaké případy chování testujeme? např: řadné vstupy, krajní meze, neplatné vstupy)
(assert: např. https://realpython.com/python-assert-statement/)
(lehká zmínka o automatickém testování, typy testů, konkrétně unit testy a knihovna unittest)


2. Implementujte funkci selectSort(list)