- COMP.CS.300
- 6. Puut (esim. keot)
- 6.7 Aktiiviteetit
Aktiiviteetit¶
Activiteetit¶
Tehtävä 1a - Algoritmien tehokkuus - FindIfOutlier¶
Kotitehtävissä oli algoritmi FindIfOutlier, jonka pseudokoodi on alla. Mikä oli algoritmin tehokkuus, ja miten sitä voisi parantaa huomattavasti?
1 2 3 4 5 6 | FindIfOutlier(Vector v, int max_var):
FOR elem IN v:
IF max_var > |elem - Mean(v)|:
RETURN elem
END
END
|
Tehtävä 1b - Algoritmien tehokkuus - paranneltu versio¶
1 2 3 4 5 6 FindSpikes(Vector v, int max_var, int normal_trend_length): FOR index FROM 1 TO v.size: IF max_var > |v[index] - MeanOfRange(v, index, index+normal_trend_length)|: RETURN v[index] END END
Mikä on algoritmin FindSpikes() asymptoottinen tehokkuus, jos normal_trend_length-muuttuja on aina välillä [1,10]? Entä jos sen vaihteluväliä ei rajoitettaisi? Voiko FindSpikes-algoritmin tehokkuutta parantaa samalla tapaa kuin FindIfOutlier:n?
Tehtävä 2a - STL-algoritmien mukauttaminen¶
Tässä harjoituksessa sinulle annetaan vektori places
, jonka alkiot ovat
tyyppiä struct Place{ int x; int y; string name; }
. Tehtävänäsi on
mukauttaa saatavilla olevia STL-algoritmeja suorittamaan seuraavat toiminnot:
- Järjestä vektorin
places
alkiot seuraavien kriteerien mukaisesti:- ensin nousevaan järjestykseen x-koordinaatin perusteella,
- sitten nousevaan järjestykseen y-koordinaatin perusteella, jos kahdella alkiolla on samat x-koordinaatit,
- ja lopuksi sanakirjajärjestykseen nimen perusteella, jos sekä x- että y-koordinaatit ovat samat.
- Järjestä vektorin
places
alkiot seuraavien kriteerien mukaisesti:- ensin niiden etäisyyden perusteella origosta {0,0} nousevaan järjestykseen
- ja sitten sanakirjajärjestykseen nimen perusteella, jos etäisyydet origosta ovat samat.
Tehtävä 2b - STL-algoritmien mukauttaminen - jatkoa¶
Jatkoa tehtävälle 2a:
- Luo uusi vektori
nearby1
, joka sisältää kaikki ne alkiot, joiden etäisyys origosta on välillä 10 ja 20. - Luo uusi vektori
nearby1
, joka sisältää kaikki ne alkiot, joiden etäisyys origosta on välillä low ja high, missä low ja high ovat käyttäjän antamia parametreja. - Poista ne alkiot vektorista
places
, jotka sisältävät merkkijonon “Unlisted” nimessään tai joiden x- tai y-koordinaatti on alle 1.
Bonus: Kuinka monta vertailua tehdään järjestämiseen kohdissa a ja b?
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
Palautusta lähetetään...