Tietorakenteet ja algoritmit 2		24.1.2006

Harjoitus 2

Ohjaus 23.1. poikkeavasti jo 12.15-13.40, paikka sama T/B178.

Seuraava X1 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ää
harjoituspäivän aamuun klo 08.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_X1_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_X1_tunnus sjuva < tunnus.java

missä tunnus on cs-käyttäjätunnuksesi ja tunnus.java on ohjelmatiedosto
joka sisältää vastauksesi. Koska main() metodin sisältävä luokka on
public static, on luokan nimen myös oltava oma käyttäjätunnuksesi.  Tämä
ensimmäinen X-tehtävä on samalla harjoitus X-tehtävien lähettämisestä.
Ratkaisun pisteytys lasketaan suoraan mukaan kurssin pisteisiin.

X1) Kirjoita algorimi joka saa parametrinaan kaksi järjestämätöntä
    binääripuuta (tra.BTree) ja tutkii, onko puissa täsmälleen samat
    alkiot.  Huomaa, että samat alkiot voivat olla puussa useassa eri
    järjestyksessä.  Aikavaativuus? Kirjoita myös pääohjelma jolla
    testaat algoritmia.

 9) Kirjoita ohjelma joka testaa operaation tra.Set.union
    aikavaativuuden. Mikä näyttäisi olevan aikavaativuuden kertaluokka?
    Onko aikavaativuus optimaalinen?

10) Piirrä kaikki erilaiset korkeintaan 2-solmuiset suunnatut verkot
    joissa ei ole moninkertaisia kaaria (useaa kaarta rinnakkain saman
    solmuparin välillä samaan suuntaan). (Vihje: n. 11 kpl)

11) Piirrä kaikki erilaiset tasan 3-solmuiset suunnatut verkot joissa ei
    ole moninkertaisia kaaria eikä silmukoita (kaaria solmusta
    itseensä).  (Vihje: n. 17 kpl)

12) Piirrä kaikki erilaiset tasan 4-solmuiset vahvasti yhtenäiset
    (kaikista solmuista polku kuhunkin muuhun solmuun) suunnatut verkot
    joissa ei ole useita kaaria samansolmuparin välillä (samaan eikä eri
    suuntaan) eikä silmukoita (kaaria solmusta itseensä). (Vihje: n. 6
    kpl??).