Závěrečná úloha
Completion requirements
Opened: Monday, 8 February 2021, 12:00 AM
Due: Friday, 14 May 2021, 11:59 PM
Vyřešte alespoň jednu z následujících úloh a odevzdejte:
1. Matice: Máte matici NxN s kladnými a zápornými čísli. Najděte pod-matici mxm, která má největší součet. Viz prříklad:
| 3 | -10 | -6 |
| -1 | 1 | 1 |
| 2 | 5 | 8 |
Součet celé matice je 3. Avšak součet pravého dolního rohu je 15. Jakou má vaše řešení obtížnost časovou a prostorovou?
2. Text V dlouhém textu zkuste najít pro libovolná dvě slova jejich nejmenší vzdálenost na počet slov (např. v 'Ahoj Krabe, řekla ryba' je 'Ahoj' a 'ryba' vzdaleno 2 slova. Dokážete to i napsat, aby to bylo casove narocne O(1)?
3. Graf Navrhněte a napište v čistém Pythonu nový typ - vyvážený binární strom.
Závěrečný termín je jen motivační, lze odevzdávat i potom. Po úloze následuje rozmluva s přednášejícím.