Tietorakenteet ja algoritmit I
Harjoitus 1

3. Suunnittele huolella algoritmi joka saa parametrinaan kaksi kokonaislukutaulukkoa A
ja B ja joka luo ja palauttaa uuden kokonaislukutaulukon jossa on kaikki ne alkiot jotka
löytyvät taulukosta A mutta eivät löydy taulukosta B (siis niiden erotuksen). Piirrä ensin
kuva ongelmasta, sitten kirjoita ylös ratkaisuperiaate selväsanaisesti suomeksi. Tämän
jälkeen ala täsmentämään ratkaisuperiaatetta täsmällisemmäksi algoritmiksi 1-3 vaiheessa
siten, että lopullinen ratkaisuperiaate on hyvin täsmällisesti kuvattu ja se on mekaanisesti
muutettavissa toimivaksi aliohjelmaksi. Älä muuta syötetaulukoita. Mikä on algoritmisi
aikavaativuus? Voisiko sitä parantaa?


Kuva: A: [5 4 2 4], B: [1 6 2] -> Tulos: [5 4 4]

Versio 1:
Muodostetaan uusi tulostaulukko. Käydään läpi taulukon A alkiot yksi
kerrallaan ja tarkastetaan löytyykö ko. alkiota taulukosta B. Jollei
löydy, lisätään ko. alkio tulostaulukkoon.

Versio 2:
Muodosta tulostaulukko (kokoa ??)
Kullekin taulukon A alkiolle x tee seuraavaa:
	Tarkasta löytyykö x taulukosta B
	Jos löytyi:
		älä tee mitään
	Jos ei löytynyt:
		Lisää x tulostaulukkoon
Palauta tulostaulukko

Versio 3:

aputulos = uusi taulukko (samankokoinen kuin A)
tulosmäärä = 0
Kullekin taulukon A alkiolle x tee seuraavaa
	löytyi = epätosi
	Kullekin taulukon B alkiolle y tee seuraavaa
		Jos x on sama kuin y
			löytyi = tosi, lopeta sisempi toisto
	Jos löytyi on epätosi
		Aseta x aputulostaulukkoon kohdalle tulosmäärä
		tulosmäärä = tulosmäärä + 1

Luo uusi lopullinen tulostaulukko jonka koko on tulosmäärä
Kopio taulukon aputulos tulosmäärä ensimmäistä alkiota lopulliseen
tulostaulukkoon.
Palauta lopullinen tulostaulukko

Versio 4:
Tarkennetaan vielä lopullisen tulostaulukon kopiointi:
tulos = uusi taulukko (kokoa tulosmäärä)
Toista i = 0..tulosmäärä-1:
	lopullinentulostaulukko[i] = aputulos[i]


Aikavaativuus: O(|A| * |B|)  (taulukoiden alkiomäärien tulo).
Kurssin edetessä opitaan tehokkaampi tapa selvittää onko alkio x
taulukossa B jolloin aikavaativuus saadaan muotoon O(|A| + |B|), eli
_huomattavasti_ tehokkaammaksi jos taulukot ovat suuria.