Cvičeni ADS1, LS 2017/18, Ut 14:00 S6


Náhradní příklady na konci a/nebo v samostatnem souboru.


zadano  27.2	20.3	17.4
            6.3     27.3    25.4
	1   2   3   4   5   6	SUM/6
Iniciály
OA	1   4	3   3	4   5-	20	ZAP 21.5.
LC	5   5	4m  5-m	4+m	23	ZAP
JC	4   4	5-  5-	4	22	ZAP
MH      2*  4*  3*  2*  3-* 4*  18 +nahr 25.5.	
SK
LK	5   4	5-  5-	4-+	23	ZAP
JK	5   5-	5-m 4m*	4-	23	ZAP
MK	2   2	2   3	2	11	...todo
PM	4   5-	2   3	1   5-m	20	ZAP
NM	5   4	5-  4	4-m	22	ZAP
TM
DN	.   1m	1m  3m	3m  4m	12	7.6.m
GMN	1m  1m	5-m 5-m	4-m 5-m	21	ZAP
JP		4m  4-m		 8	... todo
SS	5   4	3m  4	4-m	20	ZAP
AS	5-  5	5-  2	4-	21	ZAP
PS	5-m 4	5-  4	4-  5-	27	ZAP
MS	5   4			 9
SU	    1m			 1
MV	3-  5-	5-	4-- 5- 	22	ZAP
PVe	5-  4	4-  3	4-m	20	ZAP
SV	5	1m  4	4-  4-	18
LZ	5-  3	4m  5-m	    1*	18*
PVi   	    5	3   4m	4-m 5-*	21*	24.5.
---------------------------------------
	18  20	19  19  17  10


Maily zpracovány nn.5.

Pokud odevzdavate mailem, do souboru, tj. přílohy, napište:
- ADS1
- celé vaše jméno
- číslo úkolu (nebo datum zadání)


Ulohy: 0-5 bodu
Celkem: 30 bodu, (po DC6 max. 30b, pozadavek 20b)
Na zapocet: 20 bodu (2/3 z moznych bodu)

-: malé minus, typicky drobna nepresnost a/nebo formulace
m: mailem
*: zapsáno dodatečně
(default datum pro SIS: 21.5.2018)


    zadano
DC1 27.2.	f+g = Theta(max(f,g))
DC2 6.3.	f=o(g) -> f+g = Theta(g)
DC3 20.3.	4/90: nejvetší housenka ve strome
DC4 27.3.	bludiště se 4 druhy klíčů a dveří
DC5 17.4.	druha nejmensi kostra
DC6 24.4.na 15.5. Operace index(k) v BVS
 

Komentare 
DC5: (~caste/vybrane chyby)
KnDNK ~ Kandidat na Druhou Nejmensi Kostru
- musite kontrolovat vic moznosti: Najit najmensi nepridanou hranu nestaci
  (#b<="2b")
- chcete kontrolovat KnDNK pro vsechny hrany z kostry (~O(n)), nikoli pro 
  vsechny hrany mimo kostru (az O(n^2))  (-> "4-" bodu)
- na pozmenenem grafu/kostre chcete hledat vhodnou hranu (nebo cyklus a na nem 
  hranu) typicky pomoci DFS, nechcete nezavisle hledat n nejmensich koster 
  (-> "4-" bodu)
-- po odebrani jedne hrany z kostry jste v podobne situaci jako kdyz Boruvkuv 
  alg. spojuje posledni dve komponenty (jak nekdo poznamenal)

DC6:
- pridana operace index(k)
 -- operace Find zustava
 -- časová složitost O(log n) včetně údržby přidaných dat
- dve moznosti: a) pridam pocet prvku c(v) v celem podstrome, b) pridam pocet 
  prvku l(v) v levem podstrome; tradeoff: pristupy vs. scitani vs. popis update 
- kdyz jdu doprava, odecitam od k hodnotu l(v)+1 nebo c(v.Levy)+1
- spotreba pameti *navic* O(n) nebo O(1) na vrchol (nikoli "o trochu")
- chybi popis udrzby l(v) pro rotace
- prochazeni podle poradi ma slozitost O(k+log n), pri dobre implementaci
 -- stavove programovani (misto rekurzivniho) pro popis prochazeni (misto 
  naslednika) je vic nizkourovnove (a pracnejsi, tj. nachylne k chybam)
- priklady (a obrazky) jsou vhodne pro vysvetleni (napr. na prednasce), ne pro 
  programovani


-------------
Pokud nemate dost bodu (v sloupci SUM), vyreste (spravne) nahradni priklady.
Poslete do 8.6.2018 (Patek, konec druheho tydne zkouskoveho)

Nahradni priklady, kazdy za 2 body: (cisla prikladu ..budou.. v prikladech)