Algoritmy a datové struktury I – cvičení LS 2015/16

Cvičení se koná ve čtvrtek od 9:00 v učebně S11 a přísluší k přednášce profesora Kučery.

Materiály k přednášce

Skripta Martina Mareše – skvělý studijní materiál v češtině, který pokrývá naprostou většinu témat probíraných na přednášce.
Videonahrávky přednášek Martina Mareše z roku 2014/2015.

Obsah cvičení

1. cvičení (25. 2.) Úvodní příklad se součtem podúseku a házení vajíček.
2. cvičení (3. 3.) Definice RAMu a zavedení asymptotické složitosti. Zadány domácí úkoly sqrt, ram, sum.
3. cvičení (10. 3.) Vyhledávácí stromy. Zadány domácí úkoly rebal a kmed.
4. cvičení (17. 3.) (a,b)-stromy a červeno-černé stromy. Zadán domácí úkol abjoin.
5. cvičení (24. 3.) Stromy a domácí úkoly.
6. cvičení (31. 3.) Úvod do grafových algoritmů. Zadány domácí úkoly dele a sink.
7. cvičení (7. 4.) Přehled dosud probrané látky.
8. cvičení (14. 4.) DFS a jeho aplikace. Zadány domácí úkoly nez a 6col.
9. cvičení (21. 4.) Dokončení příkladů z minula.
10. cvičení (28. 4.) Nejkratší cesty. Zadány domácí úkoly cesta, nejh, krit, 4cyk a ksled. Deadline jsou 3 týdny.
11. cvičení (5. 5.) Minimální kostry. Zadány domácí úkoly lmst, graf a mst2. Deadline jsou 3 týdny. Deadline pro mst2 prodloužen na konec akademického roku.
12. cvičení (12. 5.) Pokračování v minimálních kostrách.
13. cvičení (19. 5.) Úvod rozděl a panuj.
14. cvičení (26. 5.) Rozděl a panuj a Erathostenovo síto. Zadány domácí úkoly sito, divs, prank a addmin. Deadline je konec akademického roku.

Zápočet

Na zápočet potřebujete nasbírat 100 bodů, ty můžete získat za:

řešení domácích úkolů a
zápočtovou práci.

Úkoly přijímám pouze elektronicky na adrese husek+ads@iuuk.mff.cuni.cz, buď jako prostý text (tzn. přímo v mailu), nebo jako PDF (ideálně vyrobené (La)TeXem, ale to není povinné, jen silně doporučené). Nechci formáty .doc, .docx, .odt atp.

Úkolů bude vypsáno za cca 170 bodů, nebudou zadávány každý týden, spíš každých 14 dní. Po následující dva týdny od zadání za ně bude možno získat plný počet bodů, poté až do konce semestru můžete úlohy odevzdávat za polovinu bodů.

Zápočtová práce může být praktická (implementace algoritmu) či teoretická (popis algoritmu včetně pseudokódu, důkaz správnosti, analýza časové složitosti) a bude za ni možno získat podle náročnosti 20–40 bodů. Pár návrhů bude dostupných na webu, ale nejlepší je, když přijdete sami s něčím, co vás zajímá, rád vám vyjdu vstříc.

Body

Otazník znamená, že jsem něčemu neporozumněl a potřebuji to od vás vysvětlit. Políčka s otazníky jsou podbarvena červeně a součet je červený, pokud se v daném řádku vyskytuje nějaký otazník.

Přezdívka	sqrt	ram	sum	rebal	kmed	abjoin	dele	sink	nez	6col	cesta	nejh	krit	4cyk	ksled	lmst	graf	mst2	sito	divs	prank	addmin	Celkem
Maximum	7	10	8	10	7	9	9	10	10	10	9	9	9	9	9	9	9	13	10	12	10	10	208
*limak																							0
thegame	7	5	7			9	8		9.5	10	9	9	?	4.5				13			10		101
EJEKEJ	5	5	8		7	6	4.5		?	10	9	7	?	7.5				?	10	12	10		101
kuře	6	8	8	(8+2) / 2		4	6	10	10 / 2	6	8	9	9	7.5				?	10				101.5
prezývka	7		8				9	10	9.5	9	9	9	?					13	10		8		101.5
Badgie	3		6																				9
Obluda	7	10	8	8+2		9	9	10	10	10	9	9											101
Sebastian	7	5	8	(6+2) / 2	7		7.5		?	10	9	8	?	6	?			8	10		10.5		100