A common sense guide to data structures and algorithms

Question 1

CH9. Wat zijn Abstract Data Types?

Answer 1

Een data structuur waarbij het niet boeit hoe data wordt opgeslagen, alleen hoe het bewerkt en gebruikt wordt.

Een stack is bijvoorbeeld een array met regels die je zelf moet coderen. Maar het kan net zo goed een lijst zijn.

Question 2

CH9. Waarom zou je een Stack gebruiken als een Stack een aangepaste array is?

Answer 2

1. Het voorkomt bugs, omdat de programmeur zich moet houden aan de regels van de stack.
2. Het mentale model van een stack helpt bij het gebruiken en toepassen van een LIFO mindset.
3. Het is duidelijk voor andere programmeurs dat ze werken met een LIFO-gebaseerd algoritme.

Question 3

CH1. Wat is belangrijk bij het maken van code, naast dat het werkt?

Answer 3

• Onderhoudbaarheid
• Modulariteit
• Leesbaarheid
• Organisatie
• Code-efficiëntie

Question 4

CH1. Wat zijn de 4 basis operations van data structuren?

Answer 4

1. Lezen => Iets lezen op een specifieke plek
2. Zoeken => Een specifieke waarde zoeken
3. Toevoegen / ‘insert’
4. Verwijderen / ‘delete’

Question 5

CH1. Waarom wordt de snelheid of efficiëntie van een data structuur in stappen en niet in tijd gemeten?

Answer 5

• Een programma kan op de nieuwste supercomputer sneller (seconden) werken dan op een computer uit 1990.
• Een programma zal de ene keer langzamer runnen en de andere keer sneller (vertraging door internet, wat runt de computer op de achtergrond, errors/bugs/server problemen, etc.)

Question 6

CH1. Waarom kan een computer de waarde op een specifieke plek (index) in een array binnen 1 stap lezen, maar niet in een linked list?

Answer 6

Een array heeft een plek in het geheugen, van begin tot eind 1 reeks. De elementen van een linked lijst verwijzen naar elkaar, omdat zij niet ‘naast elkaar’ worden opgeslagen in het geheugen.

Question 7

CH1. Wat is het verschil in efficiëntie tussen lezen en zoeken in een array?

Answer 7

Lezen gebeurt in 1 stap, zoeken in min. 1, max. N (aantal elementen in de array).

Question 8

CH1. Hoeveel stappen kost elke basis operation bij een normale array?

Answer 8

Best case scenario: Worst case scenario
Lezen => 1:-
Zoeken =>  1:N
Insertion => 1:N+1
Deletion => 1:N

Question 9

CH1. Wat is het verschil tussen een set en een array?

Answer 9

In een set komen er geen duplicaten voor. In een array wel.

Question 10

CH1. Hoeveel stappen kost elke basis operation bij een normale set?

Answer 10

Best case scenario: Worst case scenario
Lezen => 1:- (onduidelijk)
Zoeken =>  1:N
Insertion => N+1:2N+1
Deletion => 1:N

Question 11

CH2. Wat is een algoritme?

Answer 11

Een verzameling/reeks instructies voor het voltooien van een specifieke taak.

Question 12

CH2. Waarom is linear search in een geordende array sneller dan bij een normale array?

Answer 12

De elementen van een geordende array hebben een volgorde. Als je 22 zoekt en je bent bij 30 gekomen in een array die van laag naar hoog is gesorteerd, dan weet je al dat 22 niet meer te vinden zal zijn. Je kan de search vroeger beëindigen dan in een normale array.

Question 13

CH3. Wat is de Big O Notation?

Answer 13

De Big O Notation geeft in CS aan hoe het aantal stappen toeneemt in verhouding met het aantal elementen.

Linear search: O(N)
Binary search: O(log N)
Er is ook O(N^2), O(sqrt(N)), etc.

Question 14

CH3. Als een programma altijd hetzelfde aantal stappen neemt, wat is dan de Big O Notation?

Answer 14

O(1), ook als het aantal stappen meer dan 1 is.

Het zijn beide rechte, horizontale lijnen die tonen dat het aantal stappen niet toeneemt naarmate er meer data wordt toegevoegd.

Zelfs als het aantal stappen een miljoen is, blijft het O(1), want het is een constante. O(N) zal altijd bij een bepaalde hoeveelheid data minder efficiënt zijn dan O(1).

Question 15

CH3. Wat is belangrijk om te onthouden bij het noteren van de Big O Notation?

Answer 15

Tenzij anders wordt vermeldt, ga je uit van het Worst Case Scenario.

Question 16

CH3. Wat is log 8?
En log 64?
En log3 81?

Answer 16

log 8 = 3
log 64 = 6
log3 81 = 3

Question 17

CH10. Wat zijn successors en terminal nodes?

Answer 17

Successor is een synoniem (onzeker) voor children nodes.

Een terminal node heeft precies 0 successors.

Question 18

CH10. Wanneer zijn 2 binary bomen vergelijkbaar (‘similar’) en wanneer zijn het kopieën?

Answer 18

Vergelijkbaar als ze dezelfde structuur hebben. Kopieën als ze vergelijkbaar zijn én als de dezelfde inhoud hebben op dezelfde plekken.

Question 19

CH10. Wat is de hoogte van een boom?

Answer 19

Het maximale aantal knooppunten in het langste pad van de boom.

Question 20

CH10. Wat is een binaire boom?

Answer 20

Een boom waarvan elk knooppunt maximaal 2 children kan hebben.

Question 21

CH10. Wanneer is een boom compleet?

Answer 21

Als alle levels (op mogelijk de laatste na) het maximale aantal knooppunten bevatten en de laatste zo veel mogelijk links gevuld is.

Question 22

CH10. Hoe kan je makkelijk berekenen op welke plek de kinderen van een knooppunt in een binaire boom staan?

Answer 22

Als K = de index van het huidige knooppunt, dan is 2k het linkerkind en 2k+1 het rechterkind.

Question 23

CH10. Hoe kan je makkelijk de diepte/hoogte van een complete boom berekenen?

Answer 23

dn = [log2 n + 1]

Question 24

CH10. Wat is een extended tree (of 2-tree)?

Answer 24

Een boom waarin elk knooppunt precies 0 (external node) of 2 (internal node) kinderen heeft.

Question 25

CH10. Wat is het verschil tussen Sequential en Linked representation van binary trees?

Answer 25

Linked representation gebruikt meerdere, parallelle arrays. Sequential representation gebruikt 1 array.

Question 26

CH10. Hoe is een linked representation van een Binary Tree opgebouwd?

Answer 26

1) INFO[K] = data node N
2) LEFT[K] = Locatie linker kind N
3) RIGHT[K] = Locatie rechter kind N
4) ROOT = pointer 1e element

Question 27

CH10. Wat houdt Sequential Representation in en wanneer is het handiger dan Linked Representation?

Answer 27

Sequential Representation is 1 single linear array binaire boom. Dit is handig voor (bijna-)complete bomen. Hier kan je 2K en 2K+1 gebruiken om de kinderen van een node N te vinden.

END bevat de locatie van het laatste knooppunt.

Question 28

CH10. Wat zijn de 3 standaard manieren om door een binaire boom te gaan?

Answer 28

1. Preorder
= Root, links, rechts
2. Inorder
= Links, root, rechts
3. Postorder
= Links, rechts, root

Opmerkingen:

• Links gaat ALTIJD vóór rechts.
• De naam geeft aan wanneer de Root aan de beurt is.

Question 29

CH10. Wat is een binary search tree?

Answer 29

Een binaire boom waarbij voor ELK knooppunt N geldt dat elk knooppunt links van N kleiner is dan N en elk knooppunt rechts van N groter is dan N.

Question 30

CH10. Wanneer is een boom gebalanceerd?

Answer 30

Als de hoogtes van de subbomen met maximaal 1 verschillen.

Question 31

CH10. Wat is een Heap?

Answer 31

Een heap (of maxheap) is een complete binaire boom waarbij voor elk knooppunt N geldt dat de waarde groter dan of gelijk is aan de waarde van al zijn kinderen.

Question 32

CH10. Hoe voeg je een element toe aan een heap?

Answer 32

1. Voeg het ITEM toe op END+1

2. Wissel het ITEM om met de ouder van ITEM (P(ITEM)) zolang ITEM > P(ITEM).

Question 33

CH10. Hoe verwijder je een element uit een heap?

Answer 33

1. Sla de ROOT op in ITEM.
2. Vervang de ROOT met het laatste ITEM L in de heap en END = END - 1.
   3a. Pak het grootste kind Large(L) van L. Als L < Large(L), wissel ze om.
   3b. Herhaal totdat L >= Large(L).

Question 34

CH10. Hoe voeg je een element toe aan een binaire zoekboom?

Answer 34

1. Vergelijk ITEM met Root N
   2a. Item > N, ga naar rechts
   2b. Item < N, ga naar links
2. Herhaal, totdat je ITEM vindt (ofwel ITEM is een duplicaat) óf totdat je een lege subboom tegenkomt.

Question 35

CH10. Hoe verwijder je een element uit een binaire zoekboom?

Answer 35

1. Zoek het te verwijderen element.
   2a. Als het element N geen kinderen heeft, verwijder N.
   2b. Als het element N 1 kind M heeft, verwijder N en vervang het met M.
   2c. Als het element N 2 kinderen heeft, vind dan eerst de inorder successor S(N) van N.
   Verwijder S(N).
   Vervang N met S(N).

Question 36

CH9. Wat is het nut van een ADT als het ingebouwde datastructuren gebruikt? Waarom zou je die ingebouwde datastructuren niet gewoon gebruiken?

Answer 36

• Je voorkomt bugs / fouten, doordat de regels geforceerd worden.
• Je denkt op een andere manier na.
• Het maakt duidelijk op welke manier de code werkt, aan jezelf en anderen.

Question 37

CH14. Wat zijn nodes?

Answer 37

Verbonden gegevens die door het geheugen zijn verspreid, worden knooppunten genoemd

Question 38

CH14. Wat is het verschil tussen hoe een array en linked list data opslaan?

Answer 38

Een array zoekt bij het aanmaken een stuk op waar opeenvolgende ‘cellen’ vrij zijn in het geheugen. Hierin wordt de data opgeslagen.

Een linked list verspreidt de data over cellen waar deze vrij zijn en elk element verwijst naar het volgende.

Question 39

CH14. Wat weet je over nodes, specifiek m.b.t. linked lists?

Answer 39

Elke node bevat een stukje data en een pointer naar de locatie van het volgende element. Een linked list gebruikt dus 2 cellen per element (1 voor data, 1 voor pointer).

De laatste node heeft een null pointer.

Question 40

CH14. Wat is de Big O notatie van Linked List bij lezen, zoeken, invoegen en verwijderen?

Answer 40

1. Lezen => O(N)
2. Zoeken => O(N)
3. Invoegen => O(1 in het beste geval) of O(N + 1) in het ergste geval
4. Verwijderen => O(1 in het beste geval) of O(N) in het ergste geval

Question 41

CH14. Wat is bijzonder aan het verwijderen van nodes in linked lists?

Answer 41

Je verwijdert de node niet echt, maar je zorgt ervoor dat geen enkele andere node meer naar de te verwijderen node verwijst.

Het is zo goed als verwijderd qua effect.

Question 42

CH14. Wanneer is een linked list handiger dan een array?

Answer 42

1. Als je elementen aan het begin gaat toevoegen of verwijderen (denk aan stacks en queues).
2. Als je veel elementen moet gaan verwijderen midden in een verzameling.

Arrays verschuiven na elke verwijdering alle elementen, maar een linked list verandert gewoon de pointerwaarde.

Question 43

CH14. Wat is de perfecte onderliggende data structuur voor queues?

Answer 43

Doubly linked lists, omdat ze met O(1) tijdcomplexiteit elementen kunnen toevoegen en verwijderen aan beide uiteindes.

Question 44

CH15. Wat is een binary search tree?

Answer 44

Een boom waarvan elke node maximaal 1 linker- en 1 rechterkind heeft.
Ook moet elk linkerkind van elke node kleiner zijn dan de node, en elk rechterkind moet groter zijn dan de node.

Question 45

CH15. Wanneer is een boom gebalanceerd?

Answer 45

Wanneer de subbomen van de nodes dezelfde hoeveelheid nodes bevatten.

Question 46

CH15. Wat is de time complexity van een binary search tree? En hoe weet je dat?

Answer 46

O(log N), omdat je bij elke node de helft wegstreept.

Question 47

CH15. Hoeveel levels heeft een perfect gebalanceerde boom nodig om N aantal nodes te bevatten?

Answer 47

log(N) levels, want per level verdubbel je het aantal nodes vergeleken met het vorige level.

Question 48

CH15. Waarom zou je een binary search tree over een ordered array gebruiken, als ze allebei O(log N) time complexity hebben voor het zoeken van elementen?

Answer 48

Omdat een binary search tree sterker is in het toevoegen van elementen dan een ordered array.

Question 49

CH15. Wat is de time complexity van insertion in een Binary Search Tree en hoe kan dit?

Answer 49

O(log N), omdat je net zoals bij zoeken bij elke stap de helft van de elementen kan wegstrepen. Je doet daar niks meer mee.

Question 50

CH15. Wanneer zou je een binary search tree over een ordered array gebruiken?

Answer 50

Als je verwacht dat de data veel veranderingen zal ondergaan, dan gebruik je een binary search tree.

Question 51

CH15. Waar moet je voor oppassen bij het maken van een Binary Search Tree?

Answer 51

Het maken van een BST van gesorteerde data zorgt ervoor dat een boom extreem ongebalanceerd wordt gemaakt, waardoor search O(N) duurt i.p.v. O(log N).

Meestal krijg je een redelijk gebalanceerde boom als je willekeurig ‘gesorteerde’ data toevoegt.

Question 52

CH15. Hoe verwijder je een element uit een BST?

Answer 52

1. Heeft de node geen kinderen => Verwijder het.
2. Heeft de node 1 kind => Vervang het met het kind
3. Heeft de node 2 kinderen => Vervang de node met de laagste (als in kleinste) van de grotere waardes van de node.
   3b. Als deze vervangende node een rechterkind heeft, plaats deze dan op de oude plek van de vervangende node.

Question 53

CH15. Wat is Tree Traversal, waarvoor gebruik je het en welke Time Complexity heeft het?

Answer 53

Tree Traversel is het ‘bezoeken’ van elke node in een boom a.d.h.v. een recursieve methode die op een bepaalde manier (pre-, in- of postorder) de nodes langsgaat.

Time Complexity is O(N), omdat je langs elke node gaat.

Question 54

CH16. Wat is een Heap?

Answer 54

Een complete binaire boom waarvan elke node groter is dan alle afstammelingen.

Question 55

CH16. Wat betekent het als een boom ‘complete’ is?

Answer 55

Dat houdt in dat elke rij volledig gevuld is met nodes, op de laatste na. In de laatste rij mag er geen node voorkomen na een lege plek.

Question 56

CH16. Bij het verwijderen van een element uit de heap, mag je alleen de root node verwijderen. De last node wordt dan de nieuwe root node en moet omlaag ‘druppelen’.

Waarom moet dit ‘druppelen’ richting het grootste kind van de nieuwe root node gebeuren?

Answer 56

Als je de nieuwe root node met het kleinere kind omwisselt, klopt de heap structuur niet meer. Het grotere kind is dan groter dan de nieuwe root node.

Question 57

CH16. Waarom worden heaps als de betere keuze gezien vergeleken met geordende arrays?

Answer 57

Geordende array | Heap
Insertion: O(N) | O(log N)
Deletion: O(1) | O(log N)

De heap is in het consistent snel, terwijl de array soms héél snel en soms héél langzaam is.

Question 58

CH16. Waarom is het belangrijk dat een heap compleet en gebalanceerd blijft?

Answer 58

Zodat bepaalde operaties O(log N) time complexity kunnen hebben.

Question 59

CH16. Wanneer zou je een binary search tree boven een heap gebruiken?

Answer 59

BST => Search

Heap => Insert/Delete