Discrete Mathematics

Question 1

8.1 Wat is een Linked List?

Answer 1

= Een lineaire collectie van data elementen (‘nodes’), waarbij de lineaire volgorde is gegeven door een verwijzingen (‘by means of a field of pointers’).

Question 2

8.1 Wat is het verschil tussen een Stack, een Queue en een Priority queue?

Answer 2

Stacks werken volgens LIFO (= Last in, First out).
Queues werken volgens FIFO (= First in, First out).
Bij Priority queues gaan de elementen met de hoogste prioriteit als eerste eruit.

Question 3

8.1 Wat is een Stack?

Answer 3

= Een lineaire lijst waarbij insertions en deletions maar aan één einde kunnen gebeuren, namelijk de ‘top’ van de lijst.

Question 4

8.1 Wat is een Queue?

Answer 4

Een lineaire lijst waarin deletions alleen aan de voorkant gebeuren en waarin insertions alleen aan de achterkant gebeuren.

Question 5

8.2 Wat zijn vertices en edges?

Answer 5

Vertices = Knooppunten
Edges = Zijkanten/randen/de lijnen tussen vertices

Question 6

8.2 Wanneer is een Graph een Multigraph?

Answer 6

Wanneer er tussen 2 knooppunten meerdere edges zijn.

Question 7

8.2 Wat houdt de Degrees van een Vertex in?

Answer 7

= Het aantal edges in G waarin de Vertex zich bevindt.

Question 8

8.2 Wat is een Trivial Graph?

Answer 8

= Een enkel knooppunt met Deg(knooppunt) = 0

- Oftewel een isolated vertex

Question 9

8.4 Wat is een path?

Answer 9

= Een afwisselend patroon van vertices en edges.

Question 10

8.4 Wat is de lengte van een path?

Answer 10

= Het aantal edges

Question 11

8.4 Wat is een simple path?

Answer 11

= Een path waarin alle knooppunten uniek zijn.

Question 12

8.4 Wat is een trail?

Answer 12

= Een path waarin alle edges uniek zijn.

Question 13

8.4 Wanneer is een Graph verbonden?

Answer 13

“A graph G is connected if there is a path between any two of its vertices.”

Makkelijk gezegd: als er 2 grafieken los van elkaar te zien zijn, dan is de gehele grafiek G niet verbonden.

Question 14

8.4 Is een geïsoleerd knooppunt een verbonden component van een Graph?

Answer 14

Ja.

Question 15

8.4 Wat houden distance en diameter in?

Answer 15

Distance = de lengte van het kortste pad tussen 2 knooppunten
Diameter = De maximale afstand tussen 2 knooppunten in de Graph G.

Question 16

8.4 Wat zijn Cutpoints en Bridges?

Answer 16

Cutpoint:
= Als je een knooppunt van een Graph verwijdert en de Graph hierdoor ontbonden raakt, dan is dat knooppunt een Cutpoint.
Bridges:
= Een edge waarvan het verwijderen ervan ervoor zorgt dat de Graph ontbonden raakt.

Question 17

8.11 Wat zijn de 2 standaard methodes om een Graph in het geheugen van een computer te onderhouden?

Answer 17

1. “Sequential representation”
   - Tekenen
2. “Linked representation” / “Adjacency structure”
   - Matrix

Question 18

8.11 Wanneer is een Graph “dense” of “sparse”?

Answer 18

m = knooppunten, n = edges

Dense als m = O(n^2)
Sparse als m = O(h) of O(n log n)
of
Dense, als het aantal knooppunten exponentieel groeit in verhouding met het aantal edges.
Sparse, als het aantal knooppunten recht evenredig blijft in verhouding met het aantal edges.
of
Als je meer dan 1 lijn moet tekenen tussen 1 of meerdere tweetal punten, dan is de grafiek waarschijnlijk dense.

Question 19

8.11 Wanneer gebruik je “Sequential” en “Linked” representation voor een Graph?

Answer 19

Sequential als de Graph dense is, maar Linked als de Graph sparse is.

Makkelijk te onthouden:
Zou je een Graph van 100 knooppunten liever willen tekenen of als een matrix noteren? (Het antwoord is als een matrix).

Question 20

10.2 Wat is een binary tree?

Answer 20

= Een set van data elementen (nodes) waarbij er 1 node de root is en de resterende nodes een geordend paar van subbomen vormen.

Question 21

10.2 Weet je wat een successor is?

En een terminal node?

Answer 21

Successor = een node met minimaal 1 niet-lege subboom

Terminal node = een node waarvan beide subbomen leeg zijn.

Question 22

10.2 Wanneer zijn 2 binary bomen vergelijkbaar?

Answer 22

Als ze dezelfde structuur (maar verschillende inhoud) hebben.

Question 23

10.3 Wanneer is een boom compleet?

Answer 23

Als alle levels zijn gevuld met nodes én als alle nodes op het laatste level zo links mogelijk staan.

Question 24

10.3 Wat is een extended binary tree?

Answer 24

= Een binary tree waarbij elke node precies 0 óf 2 children heeft.

0 children => external node,
2 children => internal node

Question 25

10.5 Wat zijn de 3 manieren om een binary tree af te leggen?

Answer 25

1. Preorder
   = Root -> Linker subboom -> Rechter subboom
2. Inorder
   = Rechter subboom -> Root -> Linker subboom
3. Postorder
   = Linker subboom -> Rechter subboom -> Root

Question 26

10.6 Wat is een binary search tree?

Answer 26

= Een binary tree waarbij voor elke node N geldt dat de waarde van N groter is dan alle waardes in de linker subboom en kleiner is dan de waardes in de rechter subboom.

Question 27

10.6 Ben je bekend met de algoritmes voor het toevoegen aan en het verwijderen van elementen uit een binary search tree?

Answer 27

Toevoegen => kijk per Node of de Node een hogere of lagere waarde dan de toe te voegen waarde heeft. N > waarde, ga in de linker subboom verder
N < waarde, ga in de rechter subboom verder

Verwijderen => Gebruik het vorige algoritme om de juiste Node te vinden

• De node heeft geen children = vervang N met “null”
• De node heeft 1 kind = vervang N met kind
• De node heeft 2 kinderen = Vind de inorder successor S(N) van N. Verwijder S(N) en vervang N met S(N)

Question 28

10.7 Wat zijn 2 manieren om een priority queue in het geheugen te onderhouden?

Answer 28

1. Linear array
   - Element is gemakkelijk toe te voegen, maar zoeken duurt lang.
2. Sorted lineair array
   - Grootste element is de eerste of de laatste. Gemakkelijk om te verwijderen, maar inserten en deleten betekent dat elk ander element bewogen moet worden.

Question 29

10.7 Wat is een heap / maxheap?

En wat is dan een minheap?

Answer 29

= Een complete binary boom waarbij elke node N een gelijke of grotere waarde heeft dan elk kind van N.

Minheap
= Hetzelfde, maar N heeft een gelijke of LAGERE waarde dan elke afstammeling van N.

Question 30

10.7 Hoe voeg je items toe aan een heap en herstel je de heap-structuur?

Answer 30

Je voegt het item zo toe dat de binaire boom compleet blijft.
Dan vergelijk je de parent van het nieuwe item ([item]) met de parent Node P. Als P < [item], dan verwissel je ze.
Dit doe je totdat P >= [item].
De heap-structuur is hersteld.

Question 31

10.7 Hoe voeg je items toe aan een heap en herstel je de heap-structuur?

Answer 31

Je voegt het item zo toe dat de binaire boom compleet blijft.
Dan vergelijk je de parent van het nieuwe item ([item]) met de parent Node P. Als P < [item], dan verwissel je ze.
Dit doe je totdat P >= [item].
De heap-structuur is hersteld.

Question 32

10.7 Hoe verwijder je een element uit een Heap?

Answer 32

1. Sla de root op in een tijdelijke variabele [Item]
2. Vervang de root met de laatste Node L van de Heap H.
3. Vergelijk L met het grootste kind. Als het kind > L, wissel ze om. Herhaal dit tot kind < L.

Question 33

10.7 Waarom is een Heap een efficiëntere manier om een Priority Queue toe te voegen dan en (geordende) lineaire array?

Answer 33

Bij een heap zit het te verwijderen element altijd bovenaan (grootste waarde = grootste prioriteit).

Daarnaast hoef je steeds maar 1 element (de oorspronkelijke laatse Node) te wisselen met 1 child node.

Bij een (geordende) lineaire array moet je alle elementen bewegen wanneer je 1 element verwijdert.

Question 34

H1 gaat over de basis, deze moet je kennen:

• Machtsverzameling / Power set
• Fundamental Products
• Vereniging en doorsnede
• Wat is een set en hoe noteer je een set?
• Partitions
• Duality, (in)finite sets, (un)countable, Venndiagrammen, disjoint union, de diverse tekens

Answer 34

Alles hierover is samengevat in het schrift.

Question 35

2.2 Wat is het cartesisch product?

Answer 35

A X B, waarbij de resulterende set alle combinaties (a, b) bevat met a van A en b van B.

Question 36

2.3 Wat is een relatie?

Answer 36

Een subset (van A X B).

Question 37

2.3 Wat zijn het domein, bereik / range en codomein van R?

Answer 37

Domein = Alle waarden van A die als eerste waarde in de geordende paren van R zitten
Bereik = Hetzelfde, maar dan alle waarden van B.
Codomein = Alle waarden in B.

Question 38

2.4 Weet je wat een matrix en graaf zijn?

Answer 38

Matrix:
Rechthoekige reeks van rijen en kolommen, waarbij rijen => waardes A en kolommen => waardes B.
0 als er geen relatie is, 1 als er wel een relatie is.

Graaf:
Waardes in eclipsen met pijlen verbonden (“Arrow diagram”).

Question 39

2.5 Wat zijn samengestelde relaties?

Answer 39

Als er een relatie is van aRb en bRc, dan is er een relatie van aRc.

Question 40

2.6 Wat is een reflexieve relatie?

Answer 40

Een relatie is reflexief als er voor ELKE a in A geldt dat aRa.

Question 41

2.6 Wanneer is een relatie irreflexief? En wat is het verschil met een niet-reflexieve relatie?

Answer 41

Irreflexief als er voor GEEN ENKELE a in A geldt dat aRa.

Niet-reflexief als er voor minstens 1, maximaal (n(A)-1) niet geldt dat aRa.

Question 42

2.6 Wanneer is een relatie symmetrisch, antisymmetrisch en niet-symmetrisch?

Answer 42

Symmetrisch, als aRb dan bRa (voor alle (a, b)).

Antisymmetrisch,als aRb en bRa, dan a = b (voor alle (a, b))

Asymmetrisch, als niet symmetrisch én niet antisymmetrisch (onzeker)

Question 43

2.6 Wanneer is een relatie transitief of niet-transitief?

Answer 43

Transitief, als voor elke aRb waarvoor ook een bRa bestaat, er een aRc is.

Niet-transitief wanneer het niet transitief is.

Question 44

2.8 Wanneer is een relatie een equivalentie relatie?

Answer 44

Wanneer de relatie transitief, symmetrisch én reflexief is.

Question 45

2.7 Wat zijn closure properties?

Answer 45

Geen idee, maar ze geven aan wat een relatie mist om een bepaald soort relatie te zijn.

Reflexive closure = R verenigd met de geordende paren die R mist om een reflexieve relatie te zijn.

Question 46

3.2 Wat is een functie?

Answer 46

Een relatie waar bij ELKE a uit A een unieke b uit B hoort.

• f: A -> B
• Domein van een functie is altijd de hele set A (omdat elk element a uit A gebruikt moet worden!)
• Beeld => b = f(a)
• Bereik = alle beelden

Question 47

3.2 Wat is een functie?

Answer 47

Een relatie waarbij ELK element a van A bij een uniek geordend paar (a, b) hoort.

• f: A -> B
• Beeld => b = f(a)
• Bereik = alle beelden
• Een relatie is geen functie als een element uit a 2x als eerste element voorkomt!!!!!!!!!!!!

Question 48

3.2 Wanneer zijn 2 functies gelijk aan elkaar?

Answer 48

Als f(a) = g(a), voor elk element a uit A.

Question 49

3.2 Wat zijn compositie/samengestelde functies?

Answer 49

Functies waarbij het codomein van de ene functie het domein van de ander is. Dit is letterlijk hetzelfde als samengestelde relaties, alleen gaat het nu om een functie (wat een relatie is, met bepaalde voorwaarden).

Question 50

8.11 Wat zijn enkele nadelen van een adjacency matrix?

Answer 50

• Als G schaars is, zal er veel ruimte verspild worden aan de nullen (ongebruikt).
• ## Kleine toevoegingen / aanpassingen kunnen ervoor zorgen dat de gehele matrix opnieuw geordend moet worden.