Tietorakenteet ja algoritmit 18.9.2003 Harjoitus 1 1) Saat tehtäväksesi käsipelissä lajitella A4-arkkeja arkilla olevan nimen mukaan aakkosjärjestykseen. Millä taktiikalla/menetelmällä ryhtyisit toimeen kun lajiteltavia arkkeja on a) 10 b) 100 c) 1000 d) 10000 Arvioi kuinka paljon kunkin pinon lajitteluun kuluu aikaa (minuutteina, tai muuna sopivana aikayksikkönä). Yritä laskea aika perustellen käyttämästäsi menetelmästä. Ajan arviointi on helpointa kun arvioit kuhunkin yksinkertaiseen toimenpiteeseen (yhden paperin käsittely) kuluvan ajan ja lasket kuinka monta kutakin yksinkertaista operaatiota tarvitaan kussakin vaiheessa. 2) Laske, kuinka kauan menisi kunkin tehtävän 1 pinon lajitteluun valintalajittelulla. Valintalajittelun kussakin vaiheessa etsitään jäljellä olevan pinon aakkosjärjestyksessä ensimmäinen paperi ja asetetaan se alassuin valmiiden pinoon. Käytä paperien selauksen nopeutena 1 sek/arkki. Mitkä ovat tämän algoritmissa parhaita ja pahimpia tapauksia ja kuinka kauan niissä menee aikaa? 3) Käytössä jälleen tehtävän 1 neljä pinoa. Kuinka paljon aikaa arvelet kuluvan annetun henkilön lomakkeen etsimiseen kustakin pinoista kun a) pinot ovat sekaisin b) pinot ovat aakkosjärjestykseen lajiteltuna Perustele taas aika-arviosi. Jos pinot ovat aluksi sekaisin, niin yhtä hakua varten niitä ei kannattane lajitella. Sensijaan tuhansia hakuja varten varmaankin kannattaa. Missä arvelet kunkin pinon tapauksessa menevän rajan, kuinka monta hakua joudutaan suorittamaan, ennenkuin olisi ollut järkevämpää aluksi lajitella pino? 4) Nyt kun matkapuhelinnumeron voi säilyttää operaattoria vaihtaessaa, ei puhelun operaattoria voi tietää pelkästään numeron alkun perusteella. Niinpä matkapuhelinoperaattorit ovat perustaneet yhteisen palvelun joka kertoo kunkin puhelinnumeron operaattorin. Suunnittele miten tallentaisit tälläisen palvelun tiedot tietokoneelle kun operaattoreita on n. 10, puhelinnumeroita n. 4.000.000, ja puhelinnumerot ovat muotoa 0412345678 tai 0512345678, missä 12345678 on mikä tahansa 8-numeroinen numerosarja. Siis minkälaista talletusrakennetta käyttäisit? Arvioi myös tarvittavat laitteistoresurssit (muisti, levytila, jne). 5) Kertaa yksiköt s, ms, ms, ns, MHz, GHz. Arvioi edellisen tehtävän palvelukutsusi kesto. Kuinka monta kyselyä tietokoneesi pystyy palvelemaan minuutissa? Moderni tietokone tekee yhden keskusmuistia käyttävän operaation noin 100 ns:ssa, ja muistia käyttämättömän noin 1 ns:ssa. 6) Aseta seuraavat funktiot kasvunopeuden mukaiseen järjestykseen: a) sqrt(n)/log(n) f) 42*loglog(n) k) (n^3)/log(n) p) (log(n))^2 b) cbrt(n) + sqrt(n) g) n^3/sqrt(n) + n^3 l) 2^n q) n! c) n^2.5 h) n^3 m) n*log(n) r) sqrt(n) + log(n) d) n^log(7) i) 2003 n) log(n^2) e) n j) (7/2)^n o) n^2 + n sqrt = neliöjuuri, cbrt = kuutiojuuri, log = 2-kantainen logaritmi, ^ = potenssiin valmistaudu perustelemaan peräkkäisten funktioiden järjestys.