Yleisiä linkkejä:

Hajautusfunktiosta: http://www.strchr.com/hash_functions

Verkoista: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/index.html

Laajahkoja tiedostoja testausta varten: http://pizzachili.dcc.uchile.cl/texts.html

Trie: http://en.wikipedia.org/wiki/Trie

Tiedon koodaus / pakkaus: http://www.binaryessence.com/dct/en000003.htm

Puut ja muut tietorakenteet

Sanaindeksi

Sanaindeksiohjelma saa syötteenä yhden tai useamman tekstitiedoston. Tiedostojen sanoista muodostetaan yksi hakupuu, jolloin on helppoa hakea tietyn sanan esiintymiskohdat tiedostoissa.  Vertaili ohjelmaa kahdella eri puun totetuksella:  punamusta ja trie. Oma aputietorakenne. Parhaimpaan arvosanaan vaaditaan, että ohjelma voi lukea sisään n tiedostoa yhteen puuhun ja haun voi suorittaa m sanalla / sananalulla.

Kekovertailu

Toteuta ja vertaile seuraavia kekoja: Binomi, Binääri ja Fibonacci. Vaikeutta lisää saa työhön toteuttamalla myös Brodal Queue.

Puita ja niiden karsintaa

Jokaisen puun kohdalla toteutetaan puun läpikäynti: pre-order, in-order ja level-order. Puita: Trie, binäärihaku, AVL, punamusta, AA, Splay, etc. Kolmen eri puun toteutus, lisähaasteena toteutetaan Alpha-Beta pruning tai Mini-Max (Johdatus tekoälyyn materiaalia)

Verkot

A* vs Dijsktra

A* ja Dijsktra – havainnollista miksi A* on yleensä parempi, esitä myös esimerkki jossa A* ei ole parempi. Vertaa tila- ja aikavaativuuksia toteutuksissasi. Ainakin yksi oma apu-tietorakenne ja graafinen kuva (etsinnän aikana päivittyvä kuva paras) etsintäalueesta ja lopullisesta polusta. Kahdella eri heuristiikalla, esim. Manhattan ja Euklidinen. Vain yksi toteutus kummastakin sekä A* että Dijsktra algoritmistä, pitää toimia kahdella eri heuristiikalla (eli älä kovakoodaa naapureiden määrittelyä/etsintää. Toteuta niin että voidaan arvioida n-määrä naapuria). Sivun alareunan linkistä pääset Matti Luukkaisen A*-ohjeeseen, siellä on hyvä opastus miten teet kuvasta (bittikartta) A*:ille labyrintin. Lisähaastetta saat työhön toteuttamalla kaksi eri versiota PriorityQueue-tietorakenteesta (esim. minimikeko, fibonaccikeko ja järjestyksessä oleva lista).

Verkon virittävät puut

Vertaile kahta algoritmiä: Prim ja Kruskal. Graafinen tulostus lähtötilanteesta sekä lopputuloksesta (kannattaa tutustua käsitteisiin digraph sekä dot-notaatio, jos ei itse halua alkaa tekemään piirtoa). Toteuta kaksi eri versiota PriorityQueue-tyyppisestä tietorakenteesta (esim minimikeko ja järjestetty lista). 

Kauppamatkustajan ongelman approksimaatio tai tarkka ratkaisu

Toteutus vähintään kahdella eri algoritmillä. Täältä löytyy tietoa ja esimerkkejä verkoista: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/index.html

Verkon maksimivirtaus

Vertaile kahta verkon maksimivirtausta tutkivaa algoritmiä.

Pelit, tekoälyt, muut aiheet

Hexed-palapeli

Pelin tekijöiden väitös: Tietokone vahvistaa, 2339 tapaa ratkaista peli. Onko näin?
http://populaari.blogspot.fi/2007/05/hexed.html

Kuutiopalapeli - kuinka monta tapaa ratkaista?

2-ulotteiset palat, 3-ulotteiset palat, yleistys aiheesta - kuinka monta laatikkoa eri typpejä mahtuu konttiin

http://en.wikipedia.org/wiki/Soma_cube

Matriisilaskin

Matlab tai Octave osaavat tehdä matriisilaskentaa. Javassa ei ole valmista kalustoa matriisilaskennalle. Toteuta tämä itse!

Esimerkkejä: http://www.bluebit.gr/matrix-calculator/ http://www.math.ubc.ca/~israel/applet/mcalc/matcalc.html

Sännöllisten lauseiden tulkki

Säännölliset lausekkeet: http://linux.fi/wiki/S%C3%A4%C3%A4nn%C3%B6llinen_lauseke ja http://en.wikipedia.org/wiki/Regular_expression

Pelin tekoäly

Shakki, 4/5/n-suora, ehdota omaa! Itse kehitetty logiikka ja ehkä jokin puu-rakenne. Tarpeen mukaan myös Alpha-Beta-Pruning ja MiniMax (tms.)

Konveksin peitteen algoritmit (convex hull algorithms)

Selostus tulossa

Monen merkkijonon etsintä: Aho-Corasick

Selostus tulossa

Tiedon pakkaus

Huffmanpakkaus

Toteutus Trie-rakenteella =  O (n log n). Haastetta lisää tuo tehokkaampi ratkaisu:  van Emde Boas puu = O (n log log n) http://en.wikipedia.org/wiki/Huffman_coding

LempelZiv-78

Nopea ja tehokas toteutus, monipuolisesti tutkittu mahdollisuuksia tallentaa. Voi toimia valinnan mukaan monella tiedostotyypillä. Vertaa omaa ohjelmaasi esimerkiki gzip-ohjelman toimintaan. Korkean tason selostus aiheesta: http://marknelson.us/1989/10/01/lzw-data-compression/ SEKÄ http://en.wikipedia.org/wiki/LZ77_and_LZ78

LempelZiv-78 ja Huffman

Toteuta työssä ensin Huffman-koodauksella lyhyemmät bittijonot tavuille ja sitten LempelZiv-78 pakkaa nämä. http://en.wikipedia.org/wiki/LZ77_and_LZ78 SEKÄ http://en.wikipedia.org/wiki/Huffman_coding

Deflate algoritmi

Gzip- ja 7-zip-ohjelmat käyttävät pohjautuvat Deflate algoritmiin. Työssä tulet tutustumaan sekä LempelZiv-7-7 sekä Huffman-algoritmiin. http://en.wikipedia.org/wiki/DEFLATE

Muita aihe-ehdotuksia ja tarkempia kuvauksia aiheista: