Niet officiele uitwerkingen
#Hash tables Wat is een hashtable?
Een hashtable is een datastructuur waarbij je aan de hand van een unieke sleutel "key" een waarde kan ophalen "value".
Wat is het doel van de hash functie?
De hashfunctie berekent een sleutel over hetgeen je wilt invoegen in de hashtable. De hashfunctie moet hetzelfde argument dezelfde uitkomst hebben.
Wat is een collision?
Wanneer je een element invoegt in een hashtable wordt er met behulp van de hashfunctie een plaats gekozen in de hashtable. Als er twee keer dezelfde plaats uit de hashfunctie komt vindt er een botsing plaats. Dit heet een collision.
#Dijkstra kortste pad
public void dijkstra(String startName) {
PriorityQueue<Path> pq = new PriorityQueue<Path>();
Vertex start = vertexMap.get(startName);
if (start == null) throw new NoSuchElementException("Start vertex not found");
clearAll();
pq.add(new Path(start, 0));
start.dist = 0;
int nodesSeen = 0;
while (!pq.isEmpty() && nodesSeen < vertexMap.size()) {
Path vrec = pq.remove();
Vertex v = vrec.dest;
if (v.scratch == 0) {
v.scratch = 1;
nodesSeen++;
for (Edge e : v.adj) {
Vertex w = e.dest;
double cvw = e.cost;
if (cvw < 0) throw new GraphException("Graph has negative edges");
if (w.dist > v.dist + cvw) {
w.dist = v.dist + cvw;
w.prev = v;
pq.add(new Path(w, w.dist));
}
}
}
}
}
Op regel drie wordt er een priority queue aangemaakt. Waarvoor wordt deze in de code gebruikt?
De priority queue wordt gebruikt om in op te slaan welke nodes er nog moeten worden behandelt (vanaf een bepaalde node) Om zo de kortste route te bepalen naar dat punt.
In de bovenstaande code wordt meerdere malen de Vertex en Edge klasse gebruikt. Wat is de Nederlandse vertaling voor deze twee klassen en waarvoor wordt deze klassen gebruikt in dit stukje code?
Vertex is een knooppunt en een edge is de verbinding/lijn tussen twee punten Deze klassen worden gebruikt om de graaf op te bouwen. De punten (vertices) worden verbonden door het gebruik van de verbindingen (edges)
Verklaar de conditie op regel 32 van de bovenstaande code?
if( w.dist > v.dist + cvw )
Deze regel vergelijkt de huidige kosten naar een bepaalde node (vanaf de startplaats) Met de kosten vanaf het tijdelijke punt + de kosten naar de bestemming
#AVL Tree
Teken de boom die ontstaat, wanneer je volgende getallen achtereenvolgens aan een AVL-boom toevoegt.
Teken ook alle tussenliggende bomen wanneer je een item toevoegt.
De getallen zijn:
1, 5, 8, 4, 7, 6, 2, 10, 9, 4
Om dit op te lossen heb ik een overzicht gemaakt van de rotaties.
Er zit een makkelijk patroon in dat niet goed in de sheets naar voren komt:
Elke keer als er een van die situaties is kan je roteren om de boom te balanceren. Vergeet niet om de kinderen aan de juiste knoop te plakken. K2 verliest altijd zijn kinderen omdat die in het midden terecht komt.
AVL Boom stap opgelost met behulp van AVL Visualisation:
#Sorteren
private static <AnyType extends Comparable<? super AnyType>> void unknownsort(AnyType[] a, int low, int high) {
if (low + 8 > high) {
insertionSort(a, low, high);
}
else { // Sort low, middle, high
int middle = /* Vraag b */;
if( a[ middle ].compareTo( a[ low ] ) < 0 ) {
swapReferences( a, low, middle );
}
if( a[ high ].compareTo( a[ low ] ) < 0 ) {
swapReferences( a, low, high );
}
if( a[ high ].compareTo( a[ middle ] ) < 0 ) {
swapReferences( a, middle, high );
}
// Place pivot at position high - 1
swapReferences( a, middle, high - 1 );
AnyType pivot = /* Vraag c */;
// Begin partitioning
int i, j;
for( i = low, j = high - 1; ; ) {
while( a[ ++i ].compareTo( pivot ) < 0 );
while(/* Vraag d */);
if( i >= j ) {
break;
}
swapReferences( a, i, j ); }
}
// Restore pivot
swapReferences( a, i, high - 1 );
unknownsort(a, low, i - 1); // Sort small elements
/* Vraag e */; // Sort large elements
}
}
public static final <AnyType> void swapReferences( AnyType [ ] a, int index1, int index2 ) {
AnyType tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}
Welk sorteringsalgoritme is hierboven beschreven?
Quicksort, kan je zien aan de pivot en het partitioneren
Welke code moet er ingevuld worden op regel 8 waar nu staat / Vraag b /?
int middle = low + (high - low) / 2
But why?.. Volgens mij zorgt dit ervoor dat als je een 2e helft (bijv. 3-6 van een array) kan partitioneren, dan is low bijv. 3 en gaat hij dus alles vanaf 3 doen.
Welke code moet er ingevuld worden op regel 19 waar nu staat / Vraag c /?
AnyType pivot = a[high-1];
Dit zorgt ervoor dat er in de for loop kan worden vergeleken met de waarde die de pivot heeft.
Welke code moet er ingevuld worden op regel 27 waar nu staat / Vraag d /?
while(a[j--].compareTo( pivot ) > 0)
Waarden groter dan de pivot moeten rechts worden gezet.
Welke code moet er ingevuld worden op regel 38 waar nu staat / Vraag e /?
unknownsort(a, i+1, high);
Zo gaat hij vanaf het midden tot het einde van de array (het bovenste gedeelte dus) sorteren.
##Mergesort De onderstaande cijfers moeten gesorteerd worden met behulp van mergesort. Teken de deel-array's tijdens de iteraties van mergesort. Laat zo zien hoe de array opsplitst en uiteindelijk weer tot een gesorteerde lijst wordt samengevoegd.
2 7 3 9 1 8 6 4 10 5
Eerst linkerhelft, dan rechterhelft
[2, 7, 3, 9, 1, 8, 6, 4, 10, 5]
[2,7,3,9,1] [8,6,4,10,5]
[2,7,3] [9,1] [8,6,4] [10,5]
[2,7] [3] [9] [1] [8,6] [4] [10] [5]
[2] [7] [3] [9] [1] [8] [6] [4] [10] [5]
[2,7] [3,9] [1] [8] [6] [4] [10] [5]
[2,3,7,9] [1] [8] [6] [4] [10] [5]
[1,2,3,7,9] [8] [6] [4] [10] [5]
[1,2,3,7,9] [6,8] [4,10] [5]
[1,2,3,7,9] [4,6,8,10] [5]
[1,2,3,7,9] [4,5,6,8,10]
[1,2,3,4,5,6,7,8,9,10]
#Compressie ###We gaan de volgende tekst comprimeren inclusief de spaties:
is Frans in het Frans ook Frans?
Laat de stappen zien die nodig zijn om de Huffmanboom op te stellen. Stel de frequentietabel op en teken de Huffmanboom. Vergeet niet om je tabel goed te sorteren en het totaal aantal tekens te tellen.
Huffmanboom maakt gebruik van frequentietabel.
| Letter | Aantal (turf) | Decimaal |
|---|---|---|
| i | II | 2 |
| s | IIII | 4 |
| F | III | 3 |
| R | III | 3 |
| A | III | 3 |
| N | IIII | 4 |
| _ | IIIIII | 6 |
| H | I | 1 |
| E | I | 1 |
| T | I | 1 |
| O | II | 2 |
| K | I | 1 |
| ? | I | 1 |
Na sorteren:
| Letter | Aantal (turf) | Decimaal |
|---|---|---|
| _ | IIIIII | 6 |
| s | IIII | 4 |
| N | IIII | 4 |
| F | III | 3 |
| R | III | 3 |
| A | III | 3 |
| i | II | 2 |
| O | II | 2 |
| H | I | 1 |
| E | I | 1 |
| T | I | 1 |
| K | I | 1 |
| ? | I | 1 |
Totaal: 32 tekens
is Frans in het Frans ook Frans?
| Letter | Bits |
|---|---|
| _ | 00 |
| s | 01 |
| n | 1000 |
| F | 1001 |
| r | 1010 |
| a | 1011 |
| i | 1100 |
| o | 11010 |
| h | 11011 |
| e | 11100 |
| t | 11101 |
| k | 11110 |
| ? | 11111 |
i s - F r a n s - i n - h e t -
1100 01 00 1001 1010 1011 1000 01 00 1100 1000 00 11011 11100 11101 00
F r a n s - o o k - F r a n s ?
1001 1010 1011 1000 01 00 11010 11010 11110 00 1001 1010 1011 1000 01 11111
Is:
1100010010011010101110000100110010000011011111001110100100110101011100001001101011010111100010011010101110000111111
115 bits
Stel nu de LZW array samen voor dezelfde tekst. Beschrijf het stappenplan voor het samenstellen van deze tabel. Beschrijf ook hoe lang de tabel over het algemeen zou blijven groeien als de tekst langer zou zijn. Beginnen bij 256 omdat de eerste 255 al door alle ASCII karakters zijn gevuld. Hierdoor wordt vanaf nu elk karakter met 12 bits geschreven.
is Frans in het Frans ook Frans?
| Iteratie | Current | Ouput | Nummer | Karakters |
|---|---|---|---|---|
| 1 | i | i | 256 | is |
| 2 | s | s | 257 | s_ |
| 3 | _ | _ | 258 | _f |
| 4 | f | f | 259 | fr |
| 5 | r | r | 260 | ra |
| 6 | a | a | 261 | an |
| 7 | n | n | 262 | ns |
| 8 | s_ | 257 (s_) | 263 | s_i |
| 9 | i | i | 264 | in |
| 10 | n | n | 265 | n_ |
| 11 | _ | _ | 266 | _h |
| 12 | h | h | 267 | he |
| 13 | e | e | 268 | et |
| 14 | t | t | 269 | t_ |
| 15 | _f | 258 (_f) | 270 | _fr |
| 16 | ra | 260 (ra) | 271 | ran |
| 17 | ns | 261 (ns) | 272 | ns_ |
| 18 | _ | _ | 273 | _o |
| 19 | o | o | 274 | oo |
| 20 | o | o | 275 | ok |
| 21 | k | k | 276 | k_ |
| 22 | _fr | _fr | 277 | _fra |
| 23 | an | an | 278 | ans |
| 24 | s | s | 279 | s? |
| 25 | ? | ? | 280 |
Hoeveel bits heb je nodig om deze zin LZW gecomprimeerd op te slaan? En hoeveel bits had Huffman nodig? Welke compressie algoritme heeft de tekst beter gecomprimeerd? Elk karakter wordt bij het LZW algoritme als 12-bits weggeschreven (0-255 is 8 bits, maar 0-4095 is 12 bits). Dus voor elke karakter 12 bits. Er wordt 25 keer een karakter weggeschreven 25 * 12 = 384
Huffman heeft er maar 115 nodig
Dat betekent dat Huffman beter heeft gecomprimeerd.
Eén van de twee boven genoemde algoritmes heeft een beter compressie bereikt. Dit hoeft niet altijd het geval te zijn, maar met welke soort tekst krijg je nu de beste compressie met het Huffman algoritme?
Teksten waarin het verschil tussen gebruik van karakters groot is. Hoe vaker het karakter voorkomt hoe kleiner het wordt om weg te schrijven. Het werkt het best bij teksten met weinig varierende karakters.
Met welke soort tekst krijg je nu de beste compressie met het LZW algoritme?
Het LZW heeft een goed effect op teksten waarin veel herhaling zit.
#Cryptografie
Cryptografie is nuttig zolang computers niet snel genoeg zijn om de versleuteling te kraken.”
Geef aan of de bovenstaande stelling juist is en beargumenteer waarom. Je antwoord mag maximaal 80 woorden zijn. Indien de argumentatie ontbreekt krijg je 0 punten. De stelling is juist. In theorie is een encryptie een lastig berekende versleuteling/som. Doordat er zoveel mogelijkheden zijn is het tot op heden lastig om goede encryptie algoritmes te kraken, omdat het zoveel tijd kost om te brute-forcen. Als computers hiervoor snelgenoeg zijn is dit dus wel mogelijk.
De stelling luidt: “Het stopprobleem is in de praktijk helemaal geen probleem.” Het stopprobleem is bij de praktische software geen probleem. Software die busines gericht is bijvoorbeeld. Bij academische software (juist bedoeld om zoiets als deze stelling te ontkrachten) kan dit wel een probleem zijn.
In de bovenstaande stelling wordt de term “stopprobleem” gebruikt. Leg uitgebreid uit wat deze term betekent met betrekking tot de bovenstaande stelling. Je antwoord mag maximaal 80 woorden zijn. Het stopprobleem is beschreven door Turing. Het houdt in dat een programma kan voorspellen of een programma eindig is, of dat het in oneindigheid doorgaat. Dit is volgens Turing niet mogelijk, doordat het programma zelf zijn uitkomst kan veranderen.
Geef aan of de bovenstaande stelling juist is en beargumenteer waarom. Je antwoord mag maximaal 80 woorden zijn. Indien de argumentatie ontbreekt krijg je 0 punten.
http://stackoverflow.com/questions/1111155/what-exactly-is-the-halting-problem