Tehtävät2 - Algoritmit

HUOM! Varsinkin ensimmäiset tehtävät on helppo ratkaista generatiivisen tekoälyn avulla. Koeta kuitenkin itse hahmotella ratkaisua ennen kuin turvaudut tekoälyyn. Myös tekoälyn avulla koodia tekevältä ohjelmoijalta vaaditaan koodin ymmärtämistä ja kykyä omaan ajatteluun.

Tehtävä 1

Toteuta funktio collectFeed() joka kokoaa näppäimistöltä syöttämiäsi merkkejä merkkijonoon niin kauan kunnes syötät lopetusmerkin joka on #. Lopuksi merkkijono palautetaan, mutta ilman lopetusmerkkiä. Huomaa että merkkijonokin on tietorakenne, vähän kuin merkkejä sisältävä taulukko. Merkkijonolla (String) on JS-Api:ssa metodeja joista jotkin ovat samanlaisia mutta jotkin erilaisia kuin tavallisen taulukon metodit. Näppäimistösyötteen lukemiseen voit käyttää readline-sync -moduulia. Algoritmi on pääpiirteittäin seuraavanlainen:

1. Luodaan tyhjä merkkijono
   
2. Kysytään merkkiä jatkuvasti silmukassa
   
3. Jos merkki on #, poistutaan silmukasta. Muuten lisätään merkki merkkijonoon ja pysytään silmukassa.
   
4. Silmukasta poistumisen jälkeen palautetaan merkkijono.

Huomaa että koodia ei voi suorittaa VSCoden Code Runnerilla koska siinä käytetään näppäimistösyötettä, joten suorita se komennolla: node tiedostonnimi.  Lopputuloksen pitäisi näyttää tältä. Tee funktio tähän projektiin jossa olevan testin tulee mennä läpi.

Tehtävä 2

Tee edellisestä funktiosta toinen versio, collectFeedRec(str=''), jossa käytät rekursiota. Huomaa että parametri str='' on ns. oletusparametri. Eli jos jotain muuta argumenttia ei ole funktion kutsussa annettu, sisään menee tyhjä merkkijono. Algoritmi on pääpiirteittäin seuraavanlainen:

1. Funktion ensimmäisellä suorituskerralla on käytössä tyhjä merkkijono, str = ''
   
2. Kysytään merkkiä
   
3. Jos merkki on #, palautetaan merkkijono ja suoritus loppuu.
4. Muuten lisätään merkki merkkijonoon ja toistetaan algoritmi kutsumalla funktiota itseään (rekursio). Käytä return -avainsanaa rekursiokutsun edessä. Huomaa että uusilla kierroksilla, eli rekursioissa, merkkijonoa ei enää alusteta tyhjäksi vaan siinä pitää olla tallessa edellisillä kierroksella annetut merkit, eli rekursiossa kutsu on collectFeedRec(str).

Lopputulos on sama kuin edellisessä tehtävässä. Tee funktio tähän projektiin jossa olevan testin tulee mennä läpi.

Tehtävä 3

Toteuta algoritmi jolla etsit taulukossa useimmin esiintyvän alkion. Voit olettaa että alkiot ovat numeroita. Tee algoritmi funktioon findMostFreqBrute(arr). Käytä brute force -menetelmää eli vertaa kaikkien alkioiden arvoja toisiinsa:

1. Alusta kolme muuttujaa: suurin samojen alkioiden lkm, löydetty samojen alkioiden lkm, useimmin esiintyvän alkion arvo
2. Vertaa jokaista taulukon alkiota vuorollaan taulukon jokaiseen alkioon. Tämän voit toteuttaa kahdella sisäkkäisellä silmukalla joiden sisällä oleva if-lohko suorittaa vertailun. Jos alkiot ovat samat, lisätään löydettyä samojen alkioiden lkm:ää yhdellä.
3. Jos löydetty lkm on siihen asti suurin lkm, laitetaan löydetty suurimmaksi ja otetaan siitä indeksistä missä ollaan useimmin esiintyvän alkion arvo.
4. Aina kun yhtä alkiota on kerran verrattu kaikkiin muihin, pitää löydetty samojen alkioiden lkm alustaa. Jokainen vertailukierros tuottaa oman tuloksensa, emmekä voi lisätä uutta tulosta edellisen päälle.
   
5. Kun on poistuttu silmukoista, palauta lopullinen useimmin esiintyvän alkion arvo.

Yritä ensin tehdä algoritmi yllä olevan ohjeen avulla ja jos ei onnistu, niin katso mallia tästä. Algoritmin suorittaminen VSCoden Nodejs-debuggerilla helpottaa sen tekemistä ja ymmärtämistä huomattavasti.

Tee algoritmin testausta varten funktio createNumArr(n) joka palauttaa taulukon jossa on n kappaletta satunnaisesti arvottuja lukuja 1-9. Testaa algoritmia taulukoilla joissa on 100 ja 100000 alkiota. Miten suoritusnopeus muuttuu? Näet suoritusnopeuden konsolista kun ajat koodin VSCoden Code Runnerilla. Minkä arvelisit olevan algoritmin aikavaativuuden ja miksi?

Lopputulos voisi näyttää tältä. Tee funktiot tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 4

Toteuta saman tuloksen tuottava algoritmi kuin edellisessä tehtävässä funktioon findMostFreq(arr), mutta nyt dynaamisella menetelmällä käyttäen apuna Map -tietorakennetta:

1. Luo tyhjä Map -tietorakenne
2. Käy silmukalla taulukko läpi ja laita läpikäytävä alkio muuttujaan key (mapin avain)
3. Tutki samassa silmukassa, että jos Mapissa ei jo ole avainta key, luodaan mappiin uusi avain-arvo -pari "key, 1" eli asetetaan avaimen arvoksi 1. Muuten mapissa on jo sama avain jonka kohdalla ollaan. Tällöin otetaan avaimen arvo, kasvatetaan sitä yhdellä ja laitetaan uusi arvo Mappiin.
   
4. Kun Map -tietorakenne, jossa ovat avaimina alkiot ja arvoina niiden lukumäärät, on valmis, haetaan Mapista suurin arvo ja sitä vastaava avain joka palautetaan.

Testaa algoritmia taulukoilla joissa on 100 ja 100000 alkiota. Miten suoritusnopeus muuttuu? Minkä arvelisit olevan algoritmin aikavaativuuden ja miksi?

Voit käyttää samaa projektipohjaa kuin edellisessä tehtävässä. Jos ajat samat testit, muuta testeihin funktion nimi: findMostFreqBrute -> findMostFreq.

Tehtävä 5

Toteuta algoritmi jolla etsit pisimmän yhteisen alimerkkijonon kahdesta merkkijonosta. Tee se funktioon findLcsBrute(s1, s2). Esim. sanojen "kameli" ja "karamelli" pisin yhteinen alamerkkijono on "amel". Tee algoritmi ensin brute force -tekniikalla:

1. Kerää molemmista merkkijonoista kaikki alimerkkijonot kahteen taulukkoon. Alimerkkijonojen kerääminen onnistuu sisäkkäisiä silmukoita apuna käyttäen. Tätä varten kannattaa tehdä apufunktio getAllSubstrs(str) jota voit käyttää kaksi kertaa pääfunktiossa findLcsBrute.
2. Vertaile kahdessa taulukossa olevia alimerkkijonoja ja poimi yhteiset uuteen taulukkoon
3. Etsi taulukosta merkkijono jossa on eniten merkkejä ja palauta se

Tee algoritmin testausta varten funktio genString(charset, n), joka palauttaa merkkijonon jossa on n kappaletta satunnaisesti arvottuja merkkejä, jotka arvotaan charset -merkkijonosta. Voit käyttää merkkejä 'ATGC', jolloin etsit yhteisiä DNA-pätkiä kahdesta DNA-rihmasta.

Testaa algoritmia merkkijonoilla, joissa on 4, 100 ja 10000 merkkiä. Miten suoritusnopeus muuttuu? Minkä arvelisit olevan algoritmin aikavaativuuden ja miksi?

Lopputulos voisi näyttää tältä. Tee funktiot tähän projektiin jossa olevien testien tulee mennä läpi.

Tehtävä 6

Muunna edellisen tehtävän ratkaisua siten, että muutat kohdassa 1. tekemäsi kaksi alimerkkijonotaulukkoa ensin seteiksi ja sitten teet seteille leikkauksen (intersection), josta etsit pisimmän alimerkkijonon. Settien leikkaus on eri tyyppinen, ja nopeampi operaatio, kuin tehtävän 5 kohdassa 2 tehty alimerkkijonotaulukoiden vertailu ja yhteisten alkioiden poiminta uuteen taulukkoon.

Testaa algoritmia taulukoilla joissa on 4, 100 ja 10000 alkiota. Miten suoritusnopeus muuttuu?

Tehtävä 7

Kehitetään pisimmän yhteisen alimerkkijonon etsivää algoritmia edelleen. Tehdään uusi algoritmi funktioon findLcs(s1, s2). Hyödynnetään nyt dynaamista algoritmin suunnittelua. Käytetään kaksiulotteista taulukkoa eli matriisia säilyttämään merkkijonojen vertailun tulokset ja katsotaan pisin yhteinen alimerkkijono matriisista:

1. Alusta kolme muuttujaa: pisimmän yhteisen alimerkkijonon eli lcs:n pituus ( aluksi 0), merkkijonon s2 indeksi johon tallentuu lcs:n viimeinen merkki (aluksi 0) ja pisin yhteinen alimerkkijono (aluksi '').
   
2. Luo kaksiulotteinen taulukko, eli matriisi, jonka korkeus on sama kuin ensimmäisen merkkijonon pituus ja leveys sama kuin toisen merkkijonon pituus. kaikkien alkioiden arvo on aluksi 0.
   
3. Käy matriisi ja merkkijonot läpi sisäkkäisillä silmukoilla. Jokaista s1:n alkiota vertaillaan vuorollaan kaikkiin s2:n alkioihin ja samalla ollaan vastaavan matriisin solun kohdalla.
4. Merkkien vertailu. Jos ollaan matriisin ekalla rivillä tai sarakkeessa, ja s1:n ja s2:n merkit ovat samat, laitetaan matriisiin arvo 1. Jos ei olla matriisin ekalla rivillä tai ekassa sarakkeessa ja s1:n ja s2:n merkit ovat samat, lisätään matriisin edellisen rivin edellisen alkion arvoon 1 ja sijoitetaan saatu arvo matriisiin sille paikalle missä ollaan.
   
5. Joka kierroksella matriisiin sijoitetun alkion arvoa verrataan siihen asti suurimpaan lcs:n pituuteen. Jos uusi arvo on > siihen asti suurin, se sijoitetaan suurimmaksi ja otetaan samalla talteen indeksi johon tallentuu on lcs:n viimeinen merkki s2:ssa.
   
6. Kun silmukat on käyty läpi ja tiedetään pisimmän yhteisen alimerkkijonon eli lcs:n pituus ja indeksi johon tallentuu lcs:n viimeinen merkki s2:ssa, voidaan niistä tiedoista määrittää lcs, joka palautetaan funktiosta. Vihje: debuggerin näkymä, jossa näkyy merkkijonojen 'GTC' ja 'TC' vertailumatriisi.
   

Kokeile algoritmia samalla tavalla kuin edellisessä tehtävässä. Miten suoritusnopeus muuttuu?. Minkä arvelisit olevan tämän algoritmin aikavaativuuden ja miksi? Mitä sanoisit tämän algoritmin muistivaativuudesta verrattuna tehtävien 5 ja 6 ratkaisuihin?

Voit testata tätä algoritmia edelleen tehtävän 5 testeillä jos muokkaat testejä siten, että poistat getAllSubstrs -funktion testit ja muutat pääfunktion nimeksi findLcs. Periaatteessa voisi olla järkevää tehdä algoritmin osista omat funktionsa (esim. createMatrix, compare ja calculateLcs),
joita kutsuttaisiin pääfunktiossa. Tämä helpottaisi testausta. Tosin, jos funktiot eivät ole yleiskäyttöisiä, vaan vahvasti sidottuja toisiinsa, on hyöty hieman kyseenalainen.

Tehtävä 8

Bongobongon kansantasavallan väestö on kasvanut vuosina 1960-2010 seuraavasti:

1960: 2 miljoonaa
1970: 4 miljoonaa
1980: 6 miljoonaa
1990: 10 miljoonaa
2000: 18 miljoonaa
2010: 33 miljoonaa

Etsi npmjs.com:sta valmis regressioalgoritmi jolla voit arvioida mikä on väkiluku vuonna 2025, 2050 ja 2100 jos väestönkehitys jatkuu samanlaisena. Tee funktio joka ottaa kutsuttaessa argumentteina regressiotyypin ja vuosiluvun, ja palauttaa väkiluvun. Regression tyyppi on yksi tällä sivulla kohdassa 'Regression' esitellyistä regressiotyypeistä. Valitse oikea regressiotyyppi kokeilemalla ja/tai päättelemällä ja etsi tyyppiä vastaava algoritmi jolla ratkaiset tehtävän.

Tehtävä 9

Toteuta kolmen muuttujan logistinen regressio. Henkilöistä on saatavilla seuraavanlaista harjoitusdataa: ikä, sukupuoli, vuositulot, onko ostanut hilavitkuttimen vai ei. Harjoitusdata voisi näyttää tältä, mutta voit itse keksiä sitä lisää. Henkilön ominaisuuksien perusteella ennustat ostokäyttäytymistä eli todennäköisyyttä sille ostaako hän hilavitkuttimen vai ei. Huomaa että dataa on hyvin vähän ja korrelaatio on heikkoa, joten mallin tuottamat tulokset ovat vain suuntaa-antavia.

Käytä ratkaisun pohjana yhden muuttujan logistisen regression esimerkkiä. Ratkaisu onnistuu tekemällä esimerkkiin pieniä muutoksia. Tämän laskurin avulla voit havainnollistaa myös usean muuttujan logistista regressiota.

Tehtävä 10

Kokeile roskapostin havaitsemista Bayesin naiivin klassifikaation avulla. Käytä valmista algoritmia: bayes-classifier, jota harjoitat normaalilla postilla ja roskapostilla. Tutki algoritmin lähdekoodista ja web-lähteistä kuinka algoritmi pääpiirteissään toimii ja kirjoita kommentiksi sen toiminnan kuvaus. Miksi algoritmi on naiivi?

Tehtävä 11

Kokeile tehtävän 9 ratkaisemista päättelypuun eli decision treen avulla: decision-tree. Kommentoi millä tavalla tämä algoritmi eroaa logistisesta regressiosta. Voit piirtää päättelypuun rakenteen pääpiirteissään ASCII-merkeillä, jolloin piirroksesta selviää sen toimintaperiaate. Huomaa että näin pienestä ja "ristiriitaisesta" data-aineistosta päättelypuu ennustaa vielä huonommin kuin logistinen regressio, joten ei kannata huolestua huonoista tuloksista.

Lopuksi täytä kurssipalaute Peppi-järjestelmässä. Kurssilta ei voi saada arvosanaa, ennen kuin kurssipalaute on annettu.