Algoritmen en Datastructuren
Inhoud
Algoritmen en Datastructuren ...................................................................................................................... 1
week 1 ........................................................................................................................................................... 5
Inleiding ..................................................................................................................................................... 5
Faculteit ................................................................................................................................................. 5
Cryptografie............................................................................................................................................... 7
Waarom werkt cryptografie? ................................................................................................................ 7
Log() ........................................................................................................................................................... 7
Log() op de rekenmachine .................................................................................................................... 7
Algoritmen en complexiteit ...................................................................................................................... 9
Factoren: ............................................................................................................................................... 9
Complexiteit ........................................................................................................................................ 10
Big-Oh Notatie ......................................................................................................................................... 11
Typen algoritmen ................................................................................................................................ 12
Verhogen van N ................................................................................................................................... 14
Tijdsduur algoritme ............................................................................................................................. 14
Sieve of Eratosthenes .............................................................................................................................. 15
Voorbeeldcode c# (console) ............................................................................................................... 15
Maxmum Contiguous subsequence sum ................................................................................................ 16
Logaritmische complexiteit. .................................................................................................................... 16
O(log N) ............................................................................................................................................... 17
Binary search voor gesorteerde reeks ................................................................................................ 17
O ( N log N ) ......................................................................................................................................... 17
Bekende functies ..................................................................................................................................... 19
Zoeken: .................................................................................................................................................... 19
Sorteren:.................................................................................................................................................. 19
Week2 – Basis Datastructuren .................................................................................................................... 20
List ........................................................................................................................................................... 20
Arraylist ................................................................................................................................................... 22
Bewerkingen Arraylist (big-O) ............................................................................................................. 22
LinkedList................................................................................................................................................. 23
Implementatie linkedlist(code) ........................................................................................................... 23
Gebruik (code) ..................................................................................................................................... 23
Bewerkingen linkedlist ........................................................................................................................ 24
, Typen linked list .................................................................................................................................. 26
Stack ........................................................................................................................................................ 27
Werking stack ...................................................................................................................................... 27
Toepassingen van de stack .................................................................................................................. 28
Postfix to Infix/infix to postfix ............................................................................................................. 28
Postfix to Infix...................................................................................................................................... 28
Infix to postfix...................................................................................................................................... 29
Implementatie stack............................................................................................................................ 30
Queue ...................................................................................................................................................... 31
Wat is een queue?............................................................................................................................... 31
Toepassingen van de queue ................................................................................................................ 31
Queue implementatie ......................................................................................................................... 32
Recursie ....................................................................................................................................................... 33
Regels voor recursie volgens Weiss ........................................................................................................ 33
Recursie en stack ..................................................................................................................................... 33
Reeks van Fibonacci ............................................................................................................................ 34
Sorteren....................................................................................................................................................... 35
Insertion sort ........................................................................................................................................... 36
Voorbeeld Java: ................................................................................................................................... 36
Voorbeeld C# ....................................................................................................................................... 36
Analyse Insertion sort ............................................................................................................................. 37
Shellsort................................................................................................................................................... 38
Wat is een goede increment sequence? ............................................................................................. 38
Voorbeeld Java .................................................................................................................................... 39
Voorbeeld C# ....................................................................................................................................... 39
Mergesort ................................................................................................................................................ 40
Algoritme mergesort ........................................................................................................................... 40
Pseudocode ......................................................................................................................................... 40
Voor en nadelen mergesort ................................................................................................................ 40
Opdelen voor Sorteren........................................................................................................................ 41
Samenvoegen mergen (lineair) ........................................................................................................... 41
Voorbeeldcode Java ............................................................................................................................ 42
Voorbeeldcode C# ............................................................................................................................... 43
Quicksort ................................................................................................................................................. 44
Pseudocode ......................................................................................................................................... 45
Hoe kiezen we de pivot? ..................................................................................................................... 45
Hoe splitsen we? ................................................................................................................................. 46
, Analyse Quicksort ................................................................................................................................ 46
Bomen ......................................................................................................................................................... 47
Toepassingen van bomen ....................................................................................................................... 47
Tree traversal (printen van volgorde) ................................................................................................. 48
Binaire bomen ..................................................................................................................................... 48
Binaire zoekbomen (BST) ............................................................................................................................ 50
Operaties op BST ..................................................................................................................................... 50
Binaire zoekboom: find ....................................................................................................................... 51
Binaire zoekboom: insert .................................................................................................................... 51
Binaire zoekboom: remove ..................................................................................................................... 52
Één child .............................................................................................................................................. 52
Node met twee children: .................................................................................................................... 52
AVL bomen .................................................................................................................................................. 53
binaire zoekboom VS AVL boom ............................................................................................................ 53
AVL bomen: insert ................................................................................................................................... 54
Single rotation (LL) & (RR) ................................................................................................................... 55
Double Rotation (LR & RL)....................................................................................................................... 56
Postfix Prefix notatie bomen................................................................................................................... 57
Priority queue met binary heap .................................................................................................................. 58
Operaties: ................................................................................................................................................ 58
Minheap / maxheap ................................................................................................................................ 58
Implementatie priority queue: de binary heap ...................................................................................... 59
Analyse operaties .................................................................................................................................... 59
Implementatie tree met een array ......................................................................................................... 59
Insert ....................................................................................................................................................... 60
Insert: Percolate up ............................................................................................................................. 60
Insert Code .......................................................................................................................................... 60
deleteMin: percolate down .................................................................................................................... 61
buildHeap ................................................................................................................................................ 62
Grafen.......................................................................................................................................................... 64
Representatie van grafen ........................................................................................................................ 64
Toepassingen .......................................................................................................................................... 64
Implementatie ......................................................................................................................................... 65
Adjacency matrix ................................................................................................................................. 65
Adjacency List ...................................................................................................................................... 65
Code voorbeeld ....................................................................................................................................... 66
Vertex-klasse ....................................................................................................................................... 66
, Edge-klasse .......................................................................................................................................... 66
Graph-klasse ........................................................................................................................................ 66
Kortste-pad algoritme ................................................................................................................................. 67
Gewogen en ongewogen .................................................................................................................... 67
Kortste-pad algoritme (ongewogen) ...................................................................................................... 68
Breadth-first in een graaf (1)............................................................................................................... 68
Algoritme ............................................................................................................................................. 69
Kortste pad algoritme (gewogen): Dijkstra ............................................................................................. 70
Stappen ............................................................................................................................................... 70
Voorbeeld ............................................................................................................................................ 71
Implementatie Dijkstra ....................................................................................................................... 72
Hashing ........................................................................................................................................................ 73
Hash tables .............................................................................................................................................. 73
Hash functions ......................................................................................................................................... 74
Collision ............................................................................................................................................... 74
Fout voorbeeld 1 ................................................................................................................................. 75
Fout voorbeeld 2 ................................................................................................................................. 75
Goed voorbeeld .................................................................................................................................. 76
37 ......................................................................................................................................................... 76
Separate chaining .................................................................................................................................... 77
Array of linked lists (met mod 10).................................................................................................... 77
Open addressing ..................................................................................................................................... 78
Linear probing (Vakje bezet? 1 stapje verder totdat er een plekje vrij is) ...................................... 78
Quadratic probing ( ............................................................................................................................. 79
Double hashing.................................................................................................................................... 80
Rehashing ............................................................................................................................................ 82
Algemene woordenlijst ............................................................................................................................... 83
Inhoud
Algoritmen en Datastructuren ...................................................................................................................... 1
week 1 ........................................................................................................................................................... 5
Inleiding ..................................................................................................................................................... 5
Faculteit ................................................................................................................................................. 5
Cryptografie............................................................................................................................................... 7
Waarom werkt cryptografie? ................................................................................................................ 7
Log() ........................................................................................................................................................... 7
Log() op de rekenmachine .................................................................................................................... 7
Algoritmen en complexiteit ...................................................................................................................... 9
Factoren: ............................................................................................................................................... 9
Complexiteit ........................................................................................................................................ 10
Big-Oh Notatie ......................................................................................................................................... 11
Typen algoritmen ................................................................................................................................ 12
Verhogen van N ................................................................................................................................... 14
Tijdsduur algoritme ............................................................................................................................. 14
Sieve of Eratosthenes .............................................................................................................................. 15
Voorbeeldcode c# (console) ............................................................................................................... 15
Maxmum Contiguous subsequence sum ................................................................................................ 16
Logaritmische complexiteit. .................................................................................................................... 16
O(log N) ............................................................................................................................................... 17
Binary search voor gesorteerde reeks ................................................................................................ 17
O ( N log N ) ......................................................................................................................................... 17
Bekende functies ..................................................................................................................................... 19
Zoeken: .................................................................................................................................................... 19
Sorteren:.................................................................................................................................................. 19
Week2 – Basis Datastructuren .................................................................................................................... 20
List ........................................................................................................................................................... 20
Arraylist ................................................................................................................................................... 22
Bewerkingen Arraylist (big-O) ............................................................................................................. 22
LinkedList................................................................................................................................................. 23
Implementatie linkedlist(code) ........................................................................................................... 23
Gebruik (code) ..................................................................................................................................... 23
Bewerkingen linkedlist ........................................................................................................................ 24
, Typen linked list .................................................................................................................................. 26
Stack ........................................................................................................................................................ 27
Werking stack ...................................................................................................................................... 27
Toepassingen van de stack .................................................................................................................. 28
Postfix to Infix/infix to postfix ............................................................................................................. 28
Postfix to Infix...................................................................................................................................... 28
Infix to postfix...................................................................................................................................... 29
Implementatie stack............................................................................................................................ 30
Queue ...................................................................................................................................................... 31
Wat is een queue?............................................................................................................................... 31
Toepassingen van de queue ................................................................................................................ 31
Queue implementatie ......................................................................................................................... 32
Recursie ....................................................................................................................................................... 33
Regels voor recursie volgens Weiss ........................................................................................................ 33
Recursie en stack ..................................................................................................................................... 33
Reeks van Fibonacci ............................................................................................................................ 34
Sorteren....................................................................................................................................................... 35
Insertion sort ........................................................................................................................................... 36
Voorbeeld Java: ................................................................................................................................... 36
Voorbeeld C# ....................................................................................................................................... 36
Analyse Insertion sort ............................................................................................................................. 37
Shellsort................................................................................................................................................... 38
Wat is een goede increment sequence? ............................................................................................. 38
Voorbeeld Java .................................................................................................................................... 39
Voorbeeld C# ....................................................................................................................................... 39
Mergesort ................................................................................................................................................ 40
Algoritme mergesort ........................................................................................................................... 40
Pseudocode ......................................................................................................................................... 40
Voor en nadelen mergesort ................................................................................................................ 40
Opdelen voor Sorteren........................................................................................................................ 41
Samenvoegen mergen (lineair) ........................................................................................................... 41
Voorbeeldcode Java ............................................................................................................................ 42
Voorbeeldcode C# ............................................................................................................................... 43
Quicksort ................................................................................................................................................. 44
Pseudocode ......................................................................................................................................... 45
Hoe kiezen we de pivot? ..................................................................................................................... 45
Hoe splitsen we? ................................................................................................................................. 46
, Analyse Quicksort ................................................................................................................................ 46
Bomen ......................................................................................................................................................... 47
Toepassingen van bomen ....................................................................................................................... 47
Tree traversal (printen van volgorde) ................................................................................................. 48
Binaire bomen ..................................................................................................................................... 48
Binaire zoekbomen (BST) ............................................................................................................................ 50
Operaties op BST ..................................................................................................................................... 50
Binaire zoekboom: find ....................................................................................................................... 51
Binaire zoekboom: insert .................................................................................................................... 51
Binaire zoekboom: remove ..................................................................................................................... 52
Één child .............................................................................................................................................. 52
Node met twee children: .................................................................................................................... 52
AVL bomen .................................................................................................................................................. 53
binaire zoekboom VS AVL boom ............................................................................................................ 53
AVL bomen: insert ................................................................................................................................... 54
Single rotation (LL) & (RR) ................................................................................................................... 55
Double Rotation (LR & RL)....................................................................................................................... 56
Postfix Prefix notatie bomen................................................................................................................... 57
Priority queue met binary heap .................................................................................................................. 58
Operaties: ................................................................................................................................................ 58
Minheap / maxheap ................................................................................................................................ 58
Implementatie priority queue: de binary heap ...................................................................................... 59
Analyse operaties .................................................................................................................................... 59
Implementatie tree met een array ......................................................................................................... 59
Insert ....................................................................................................................................................... 60
Insert: Percolate up ............................................................................................................................. 60
Insert Code .......................................................................................................................................... 60
deleteMin: percolate down .................................................................................................................... 61
buildHeap ................................................................................................................................................ 62
Grafen.......................................................................................................................................................... 64
Representatie van grafen ........................................................................................................................ 64
Toepassingen .......................................................................................................................................... 64
Implementatie ......................................................................................................................................... 65
Adjacency matrix ................................................................................................................................. 65
Adjacency List ...................................................................................................................................... 65
Code voorbeeld ....................................................................................................................................... 66
Vertex-klasse ....................................................................................................................................... 66
, Edge-klasse .......................................................................................................................................... 66
Graph-klasse ........................................................................................................................................ 66
Kortste-pad algoritme ................................................................................................................................. 67
Gewogen en ongewogen .................................................................................................................... 67
Kortste-pad algoritme (ongewogen) ...................................................................................................... 68
Breadth-first in een graaf (1)............................................................................................................... 68
Algoritme ............................................................................................................................................. 69
Kortste pad algoritme (gewogen): Dijkstra ............................................................................................. 70
Stappen ............................................................................................................................................... 70
Voorbeeld ............................................................................................................................................ 71
Implementatie Dijkstra ....................................................................................................................... 72
Hashing ........................................................................................................................................................ 73
Hash tables .............................................................................................................................................. 73
Hash functions ......................................................................................................................................... 74
Collision ............................................................................................................................................... 74
Fout voorbeeld 1 ................................................................................................................................. 75
Fout voorbeeld 2 ................................................................................................................................. 75
Goed voorbeeld .................................................................................................................................. 76
37 ......................................................................................................................................................... 76
Separate chaining .................................................................................................................................... 77
Array of linked lists (met mod 10).................................................................................................... 77
Open addressing ..................................................................................................................................... 78
Linear probing (Vakje bezet? 1 stapje verder totdat er een plekje vrij is) ...................................... 78
Quadratic probing ( ............................................................................................................................. 79
Double hashing.................................................................................................................................... 80
Rehashing ............................................................................................................................................ 82
Algemene woordenlijst ............................................................................................................................... 83
