Tietorakenteet ja algoritmit 2		24.2.2008

Harjoitus 7

Loppukoe to 26.2. 14.00 - 16.00 T2/D106.

Täytä opintojakson arviointilomake http://cs.joensuu.fi/~arvio/

37) Simuloi B-puun toimintaa käsin leveydellä t = 3 kun lisätään
    kirjaimia ja kaikki pienet kirjaimet ovat ennen isoja kirjaimia, eli
    a < z < A < Z. Lisää aluksi tyhjään puuhun järjestyksessä kirjaimet
    T i e t o r a k n j A l g m J O E c p u s y q. Kukin solmu jaetaan
    kahtia kun siihen on kertynyt 2t-1 avainta. Piirrä puu uudestaan
    kunkin solmun jakautumisen jälkeen. s:n lisäyksen jälkeen jakautuu
    ensin yksi lehtisolmu ja sen johdosta juurisolmu.

Seuraavissa tehtävissä toteutetaan kokonaislukujen (long) joukkoa
massamuistiin suljettua hajautusta käyttäen. Kunkin tietueen kotiosoite
on hashCode() % tietueiden_maara. Jos kotiosoite on varattuna, käytetään
seuraavia osoitteita. Jotta viimeistenkin alkioiden haku onnistuisin
yhdellä levyhaulla, jätetään tiedoston loppuun hieman tyhjää tilaa.
Tiedoston alussa on tallennettuna varsinaisten tallennuspaikkojen määrä
tietueiden_maara ja sen perään tietueiden_maara tietuetta (tyyppiä long)
ja lopuksi ylimääräinen talletusalue. Ota pohja www-sivulta. Pohjassa on
myös jonkinverran vihjeitä hajasaantitiedoston käyttöön.

Seuraava X4 tehtävä on pakollinen kaikille opiskelijoille. X-tehtävien
ratkaisujen pitää olla kunkin opiskelijan itse tekemiä. Saman ratkaisun
kopioita ei hyväksytä (versioitunakaan). Vastaukset pitää lähettää
maanantaina klo 20.00 mennessä sähköpostitse allaolevaa ohjetta
käyttäen. Saat automaattisen vastauksen pian onnistuneen lähetyksen
jälkeen. Vastauksen on sisällettävä lyhyt itsearviointi jossa arvioit
ratkaisun toimivuutta, aikavaativuutta ja mahdollisia
parannusmahdollisuuksia. Oikea itsearvointi (jonkinlaiseen ratkaisuun)
on yhden pisteen arvoinen.

Lähetä ratkaisusi cs:n käyttäjälle sjuva käyttäen viestin otsikkona
merkkijonoa TRA2_X4_tunnus missä tunnus on sinun cs-käyttäjätunnuksesi
(tai muu sähköpostiosoitteesi, esim. tunnus@cc). Helpointa lähettäminen
on cs:ltä käyttäen komentoa:

    /usr/ucb/mail -s TRA2_X4_tunnus sjuva < tunnus.java

missä tunnus on cs-käyttäjätunnuksesi ja tunnus.java on ohjelmatiedosto
(uudelleennimettynä LongHashFile_pohja) joka sisältää vastauksesi. cc
käyttäjillä luokan nimi ei toki voi sisältää @cc -osaa ja
vastaanottajana on oltava sjuva@cs. Vaihda luokan nimeksi siis oma
käyttäjätunnuksesi.

X4) Toteuta operaaiot add() ja member(). Täysiin pisteisiin oikeuttava
    vastaus lukee levyltä kerralla isomman lohkon, tarvittaessa useasti.

41-42) Toteuta uudelleenhajautus talletusalueen täyttyessä. Kun
    talletusalueesta on 2/3 käytössä, ota alkiot talteen toiseen
    tiedostoon, kaksinkertaista alkuperäinen tiedosto ja hajauta alkiot
    sinne uudelleen.