Algorithms and Data Structures Samenvatting

ADS Samenvatting
Auteur: Versie:
Joost Sijm V1.1




27 september 2021

,INLEIDING Deze samenvatting is bedoeld voor het vak Algorithms
and Data Structures van de Hogeschool van Amsterdam. De inhoud is
gebaseerd op de vak dat in het leerjaar 2020-2021 is gegeven. Hier in
probeer ik op mijn eigen manier de stof van het vak uit te leggen. Mijn mo-
tivatie voor het schrijven van deze samenvatting is om mijn eigen kennis
van het vak te testen.
Het is mijn streven om voor de besproken algorithmes code voorbeel-
den te geven, zowel als in pseudocode en eventueel echte programmeer-
talen. Het formaat van deze PDF samenvatting is A5, zo dat het gemakke-
lijk te lezen is op bijvoorbeeld een E-Reader.


Inhoudsopgave

1 OOP 2
1.1 Objectgeoriënteerd programmeren . . . . . . . . . . . . 2
1.1.1 Systemen . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Modularisatie . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Fundamentele eigenschappen . . . . . . . . . . . . 2
1.1.4 Klasse . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.5 Objecten . . . . . . . . . . . . . . . . . . . . . . 2
1.1.6 Relaties . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Abstractie . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Abstracte klasse. . . . . . . . . . . . . . . . . . . 3
1.2.2 Interface . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Abstracte data types . . . . . . . . . . . . . . . . . . 3
1.3.1 Generics . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 Java Collections API . . . . . . . . . . . . . . . . . 4
1.3.3 Iterable. . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Primitive types . . . . . . . . . . . . . . . . . . . . . 5
1.5 Recursie . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5.1 Methode aanroepen . . . . . . . . . . . . . . . . . 5
1.5.2 Gebruik . . . . . . . . . . . . . . . . . . . . . . 5
1.5.3 Types . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Comparable . . . . . . . . . . . . . . . . . . . . . . 5
1.6.1 Comparator . . . . . . . . . . . . . . . . . . . . . 6



1

, 1.7 Builder patern . . . . . . . . . . . . . . . . . . . . . 6
1.7.1 StringBuilder . . . . . . . . . . . . . . . . . . . . 6

2 Efficiency 6
2.1 Birthday paradox . . . . . . . . . . . . . . . . . . . . 7
2.2 Efficiëntie array. . . . . . . . . . . . . . . . . . . . . 7
2.3 Algoritmische complexiteit . . . . . . . . . . . . . . . . 7
2.4 JVM . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.5 Big O . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Datatypes 8
3.1 List . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1.1 ArrayList . . . . . . . . . . . . . . . . . . . . . . 8
3.1.2 LinkedList . . . . . . . . . . . . . . . . . . . . . 9
3.1.3 Vergelijking . . . . . . . . . . . . . . . . . . . . . 9
3.2 Stack . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Queue . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3.1 Heap . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Set. . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4.1 TreeSet. . . . . . . . . . . . . . . . . . . . . . . 10
3.5 HashSet . . . . . . . . . . . . . . . . . . . . . . . . 10
3.6 Map . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.6.1 Map interface . . . . . . . . . . . . . . . . . . . . 10
3.6.2 TreeMap . . . . . . . . . . . . . . . . . . . . . . 11
3.7 HashMap . . . . . . . . . . . . . . . . . . . . . . . 11

4 Hashing 11
4.1 Java hashing . . . . . . . . . . . . . . . . . . . . . . 11
4.1.1 Equals . . . . . . . . . . . . . . . . . . . . . . . 11
4.1.2 HashCode . . . . . . . . . . . . . . . . . . . . . 12
4.2 Index berekenen . . . . . . . . . . . . . . . . . . . . 12
4.3 Collisions. . . . . . . . . . . . . . . . . . . . . . . . 12
4.3.1 Open addressing . . . . . . . . . . . . . . . . . . 12
4.3.2 Separate chaining . . . . . . . . . . . . . . . . . . 12




2

, 5 Search Algorithms 13
5.1 Linear Search . . . . . . . . . . . . . . . . . . . . . 13
5.2 Binary search. . . . . . . . . . . . . . . . . . . . . . 13

6 Sort Algorithms 13
6.1 Selection Sort. . . . . . . . . . . . . . . . . . . . . . 13
6.2 Insertion Sort. . . . . . . . . . . . . . . . . . . . . . 13
6.3 Bubble Sort. . . . . . . . . . . . . . . . . . . . . . . 13
6.4 Divide and Conquer . . . . . . . . . . . . . . . . . . . 14
6.5 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . 14
6.6 Quicksort . . . . . . . . . . . . . . . . . . . . . . . 14

7 Functional Interface 14
7.1 Aanroepen . . . . . . . . . . . . . . . . . . . . . . . 14
7.1.1 Traditioneel . . . . . . . . . . . . . . . . . . . . 15
7.1.2 Statische methode . . . . . . . . . . . . . . . . . . 15
7.1.3 Instantie methode . . . . . . . . . . . . . . . . . . 15
7.1.4 Lambda expressie . . . . . . . . . . . . . . . . . . 15
7.2 Lambda . . . . . . . . . . . . . . . . . . . . . . . . 15
7.2.1 Java lambda . . . . . . . . . . . . . . . . . . . . 15
7.3 Predicate . . . . . . . . . . . . . . . . . . . . . . . . 15
7.4 Overzicht. . . . . . . . . . . . . . . . . . . . . . . . 16
7.5 Advanced map operators. . . . . . . . . . . . . . . . . 16
7.6 Compositie . . . . . . . . . . . . . . . . . . . . . . . 17
7.7 Default methods . . . . . . . . . . . . . . . . . . . . 17

8 Streams 17
8.1 Lazy . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8.2 Method chaining . . . . . . . . . . . . . . . . . . . . 17
8.3 Mapper . . . . . . . . . . . . . . . . . . . . . . . . 17
8.4 Reducer . . . . . . . . . . . . . . . . . . . . . . . . 18
8.4.1 Reducer methode . . . . . . . . . . . . . . . . . . 18
8.5 Collector . . . . . . . . . . . . . . . . . . . . . . . . 18
8.5.1 Collect to Map . . . . . . . . . . . . . . . . . . . 19




3