Sorting And Searching Theory

Front 1

Binary Search Tree kenmerken

Back 1

1. Data is te ordenen (Comparable)

2. Data opslaan in een boom om sneller te zoeken

Hint 1

2

Front 2

Gerichte boom kenmerken

Back 2

1. Er is precies een knoop met ingraad 0 (root)

2. Alle andere knopen hebben ingraad 1

3. Van elke knoop is er een pad van de wortel naar de knoop

Hint 2

3

Front 3

Wat is een gewogen graaf?

Back 3

Een graaf waarin alle lijnen een gewicht wordt toegekend.

Front 4

Wat is een Spanning tree?

Back 4

Een opspannende boom T van graaf G is een subgraaf van G die alle knopen van G bevat en die geen cycles heeft.

Front 5

Wat is een Minimum Spanning Tree (MST)?

Back 5

Een spannende boom T van graaf G waarbij de som van alle gewichten van lijnen in T minimaal is.

Front 6

Wat is het Greedy MST algoritme?

Back 6

Maakt snedes waar lijnen niet zijn gemarkeerd.

Front 7

Prim's algoritme kenmerken

Back 7

1. Begint met een willekeurige knoop en kiest de lijn met de kleinste gewicht

2. Gaat door totdat alle knopen zijn geweest

Hint 7

2

Front 8

Kruskal algoritme kenmerken

Back 8

1. Kiest lijn met de kleinste gewicht

2. Geen cycles mogen gevormd worden

Hint 8

2

Front 9

MST voorwaarden

Back 9

1. Graaf is samenhangend

2. Graaf is ongericht

3. Gewichten mogen 0 of negatief zijn

Hint 9

3

Front 10

Shortest pad: Dijkstra algoritme werking

Back 10

1. Kiest startpunt en lijn met de kortste afstand

2. Verlengd de pad met de kleinste totale afstand naar startpunt

Hint 10

2

Front 11

Shortest pad: A* kenmerk

Back 11

Maakt geen overschatting. Kosten van pad moet niet hoger dan de optimale kosten uitkomen (admissible)

Front 12

Balanced Search Tree kenmerk

Back 12

Een boom is gebalanceerd als de subbomen van de knopen alleen 1 in lengte verschillen.

Front 13

2-3 Tree kenmerken

Back 13

1. 1 of 2 keys per node

2. 2-node is 1 key met 2 children

3. 3-node is 2 keys met 3 children

Hint 13

3

Front 14

DFA vs. Regex

Back 14

DFA: een Deterministic Finite- State Automata is een machine dat een bepaalde string herkent in een set.

Regex: een bepaalde manier om een set van strings te omschrijven.

Front 15

Kleene's theorie over DFA en Regex?

Back 15

1. Voor elke DFA bestaat een Regex dat dezelfde set van strings omschrijft.

2. Voor elke Regex bestaat een DFA dat dezelfde set van strings herkent.

Hint 15

2

Front 16

Waarom geen negatieve gewicht in een gerichte gewogen graaf?

Back 16

Een negatieve gewicht leidt tot een onjuiste berekening van de kortste pad.

Front 17

Wat gebeurt er als Huffman codes niet prefix-vrij zijn?

Back 17

Er zijn meer manieren om een tekst te expanderen/decoderen.

Front 18

Compressietechniek maakt gebruik van opeenvolging van bits/karakters

Back 18

Run Length Coding

Front 19

Zoekalgoritme maakt gebruik van een eindige automaat die gebaseerd is op het patroon dat gezocht wordt.

Back 19

Knuth Morris Pratt

Front 20

Compressietechniek die gebruikmaakt van een tabel van patronen van variabele lengte met codes van vaste lengte

Back 20

LZW