Datastructuren voor AI - practicum
Opzet
Het practicum datastructuren voor AI bestaat in 2016 uit twee delen waarvoor je een cijfer krijgt. Je mag de onderdelen in teams van twee doen.
- Een plenaire opdracht: een stapsgewijze opgave over hashtables en andere dictionary-achtige datastructuren. Je moet ze eerst bouwen en dan hun performance vergelijken. De deliverables zijn je sourcecode en een verslag met bediscussiering van je resultaten. Inlevering geschiedt per blackboard en de deadline is vrijdag 19 Februari 2016 om 23:59.
- Een keuzeopdracht waarin je een AI-case mag kiezen en die uitprogrammeert naar hoe jou goed lijkt. Deliverables zijn je sourcecode en een presentatie aan het eind van het vak. Inlevering geschiedt per blackboard en de deadline is vrijdag 18 Maart 2016 om 23:59. We gaan je ook interviewen over je code en je keuzes voor datastructuren, dat gebeurt op donderdag 24 maart.
Plenaire Opdracht
1) We hebben een enorme lijst van engelse woorden die we willen gebruiken als woordenboek, om te kijken of de woorden uit de samplebestanden goed geschreven zijn. De eerste stap is dus een programma schrijven voor het inlezen van de woordenlijst, en deze in een primitive array in het werkgeheugen op te slaan (dus geen ArrayList o.i.d.). Dat is meteen je eerste datastructuur. Daarna lees je één voor één de samplebestanden in, en kijk je of de woorden uit deze samplebestanden in de woordenlijst voorkomen. Je programma moet aan het eind terug geven hoeveel van de woorden correct waren, in het format <goed> / <totaal>, en that's it. Registreer hoeveel woorden er wel/niet in de woordenlijst voorkomen, en hoeveel tijd (in nanoseconden) het verifieren van zo'n samplebestand kost. Maar: alleen het verificatieproces zelf, dus niet het inlezen, uitprinten of opstarten. Pas dan krijgen we een goed beeld van hoe efficient onze datastructuur is.
2) We gaan het anders doen. In plaats van een array om de woorden in op te slaan, maak je nu een hash table met open adressing. Belangrijk: je mag alleen primitieve types gebruiken! Als dat nog niet in college is behandeld geeft dat niks, gebruik gewoon google en begin eraan. Het kiezen van een goede hashfunctie is heel belangrijk, een dynamische resize is leuk, maar het allerbelangrijkst is dat je hashtable werkt. Lees weer alle bestanden in en meet hoeveel tijd het nu kost om ieder samplebestand te verifieren. Vergelijk de performance met de array uit punt 1. Als je dit punt grondig wil doen, probeer dan eens grotere of kleinere array achter de hashfunctie, en verifieer nogmaals de samplebestanden. Documenteer je resultaten goed, want je moet het straks inleveren.
3) Naast een hashtable met open adressing bestaat er nog een belangrijke hashtablevariant: de hash table met collision chaining. Maak zo'n hash table (de eventuele uitbreidingen weer uit primitieve types) en lees opnieuw de samplebestanden in een kijk hoe lang het duurt om de samplebestanden te verifieren. Als je nog tijd hebt, kijk dan eens of er verschil is tussen de bestanden, of probeer een extra hashfunctie.
4) Misschien dat een trie nog wel beter presteert dan beide hashtables. Of misschien heb je zelf wel een idee voor een datastructuur. Maak een trie, of een andere datastructuur naar keuze, (wederom uit primitieve types). Lees weer alle samplebestanden in, en meet hoe lang het verificatieproces duurt.
5) Maak een overzicht van de tijdconsumptie van de verschillende datastructuren die je in punten 1-4 hebt gemaakt voor alle samplebestanden. Is er verschil? Hoeveel? Is het verschil te relateren aan de samplebestanden? Hoe? Maak duidelijke grafieken en/of tabellen en bediscussieer je resultaten. Niet meer dan 4 pagina's, maar wel precies zijn in je resultaten en alleen opschrijven wat je zeker weet. Lever je verslag en je code in voor de deadline.
Keuzeopdracht
| CitiSearch | Jaeva's Word Puzzle | Did you mean ... ? |
|---|---|---|
 Dude, where's my city? |
 Word puzzle extreme |
 Spellchecking & URLchecking |
| RentaRoom | Rush Hour | Sliding Triangles |
 Old game, new rules |
 Spitsuur! |
 Een schuifpuzzel. |
| Legends of Arborea | SimpleChess | Leeuwen & Lammetjes |
 Fantasy & Flanking. |
 Chess with fewer rules. |
 The lamb that whoops the lion's manes. |
Ik wil een hoog cijfer!
Heel goed, dat moedigen we aan. Programmeer om te beginnen netjes. Gebruik deze [style guide van Google] om je code netjes te maken, daar scoor je punten mee. Extra functionaliteit scoor je ook extra punten mee, maar beter weinig functies die goed werken, dan veel functies die buggy zijn! We gebruiken ook een rubrics maar die hanteren we vrij losjes.
Overigen
Het open-source boek van de cursus.
