Cvičení­ z algoritmů a datových struktu 1 2008/2009

Cvičení z ADSI je v učebně S10 v pátek v 9:00. Na cvičení se hlašte do grupíku - kapacita omezena na 25. Stránka přednášky. Zápočet bude za sepsání práce o algoritmu dle vlastní volby ze seznamu od Martina Mareše. Práce bude obsahovat popis algoritmu, důkaz správosti, složitost a nedílnou součástí je i implementace. Samozřejmě je fajn i dodat nějaká testovací data.

Prosím neposílejte mi object files a ani exe soubory. NEMÁM WINDOWS! Stejně tak projektové soubory od Visual Studia jsou mi k ničemu. (Makefile vítám) Podmínka na programy v C# je kompilace a běh v mono.

Deadline na odevzdání zápočtové práce je 31. července 2009

Tabulka přídělených zadání

Jméno Zápočet Práce
Tomáš Hurt Z Sčítání čísel ve Fibonnačiho číselné soustavě.
Lukáš Lánský Z Insert a Delete v červeno-černých stromech [O(log n)]
Tomáš GergelitsZ Editační vzdálenost řetězců
Jakub Sanek Z Slévání setříděných posloupností v konstantním pomocném prostoru [O(n)]
Lubomir SchmidtZ Přesmyčkový slovník
Denis Vald Z Strassenovo násobení čtvercových matic
Marek Linka Z Přihrádkové třídění řetězců
Bohuslav MacháčZ Insert a Delete v AVL-stromech [O(log n)]
Tomáš Hvorkový Z Hledání silně souvislých komponent orientovaného grafu [O(n+m)]
Dominik Škoda Hledání souborů na disku, které mají stejný obsah.
Martin DzurenkoZ Obarvěte rovinný graf šesti (pěti?) barvami. [O(n)]
Ondra Kupka Z Implementujte Treap:...
Vojtěch Hanáček Insert a Delete v (a,b)-stromech [O(b log_a n)]
Marta Bednářová V rovině leží množina obdélníků (hrany rovnoběžné s osami). Jaký je obsah (či obvod) jejich sjednocení?