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:

1. 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.
2. 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:

1. Luo uusi vektori nearby1, joka sisältää kaikki ne alkiot, joiden etäisyys origosta on välillä 10 ja 20.
2. 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.
3. 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?