IPRO2 video colleges
samenvatting 22-23
Inhoudsopgave
Week 1...................................................................................................................................................2
1.2 Big O.............................................................................................................................................2
1.4 Problem solving............................................................................................................................3
1.6 Binair zoeken................................................................................................................................4
Week 2: Voorbeelden van debuggen & unit tests..................................................................................5
Week 3...................................................................................................................................................5
3.1 Bubble sort...................................................................................................................................5
3.2 Recursie........................................................................................................................................6
3.3 Merge sort....................................................................................................................................7
Week 4.................................................................................................................................................10
4.1 Single linked list..........................................................................................................................10
4.2 Double linked list........................................................................................................................11
Week 5.................................................................................................................................................14
5.1 Stack...........................................................................................................................................14
5.2 Queue.........................................................................................................................................15
5.3 Hash table...................................................................................................................................16
5.4 Test.............................................................................................................................................17
Week 6.................................................................................................................................................18
6.1 Bomen........................................................................................................................................18
6.2 Bijzondere bomen.......................................................................................................................19
6.3 Toevoegen in zoekboom.............................................................................................................20
Disclaimer:
Niet nagelopen op fouten
De missende colleges zijn voorbeelden in de ‘praktijk’.
,Week 1
1.2 Big O
Big-O notatie: Een manier om over de performance van een algoritme te praten.
Het gaat dan over de worst-case complexiteit (in ruimte of tijd)
Een algoritme heeft de worst-case tijdscomplexiteit O(f ( n )) als de looptijd voor grote n kleiner is
dan c∗f ( n)
n = de grote van je invoer
De O() bepaal je door te kijken hoeveel stapjes je code doet.
Je kijkt in de som welke n de grootste is en die zet je tussen de haakjes, het getal laat je weg.
, 1.4 Problem solving
Voor problem solving volg je de volgende stappen:
1. Lees het probleem minstens tweemaal volledig door
2. Los het probleem handmatig op met 3 sets van voorbeeld data
a. Input, proces, output
3. Optimaliseer de handmatige oplossing
a. Stappen vereenvoudigen
b. Andere oplosingen bekijken/zoeken
4. Schrijf de handmatige oplossing uit in pseudo-code
5. Zet de pseudo-code om in echte code
a. Probleem is opgelost, nu kunnen we gaan coderen
6. Optimaliseer de code
7. Test de code
Niet doen: direct programmeren
samenvatting 22-23
Inhoudsopgave
Week 1...................................................................................................................................................2
1.2 Big O.............................................................................................................................................2
1.4 Problem solving............................................................................................................................3
1.6 Binair zoeken................................................................................................................................4
Week 2: Voorbeelden van debuggen & unit tests..................................................................................5
Week 3...................................................................................................................................................5
3.1 Bubble sort...................................................................................................................................5
3.2 Recursie........................................................................................................................................6
3.3 Merge sort....................................................................................................................................7
Week 4.................................................................................................................................................10
4.1 Single linked list..........................................................................................................................10
4.2 Double linked list........................................................................................................................11
Week 5.................................................................................................................................................14
5.1 Stack...........................................................................................................................................14
5.2 Queue.........................................................................................................................................15
5.3 Hash table...................................................................................................................................16
5.4 Test.............................................................................................................................................17
Week 6.................................................................................................................................................18
6.1 Bomen........................................................................................................................................18
6.2 Bijzondere bomen.......................................................................................................................19
6.3 Toevoegen in zoekboom.............................................................................................................20
Disclaimer:
Niet nagelopen op fouten
De missende colleges zijn voorbeelden in de ‘praktijk’.
,Week 1
1.2 Big O
Big-O notatie: Een manier om over de performance van een algoritme te praten.
Het gaat dan over de worst-case complexiteit (in ruimte of tijd)
Een algoritme heeft de worst-case tijdscomplexiteit O(f ( n )) als de looptijd voor grote n kleiner is
dan c∗f ( n)
n = de grote van je invoer
De O() bepaal je door te kijken hoeveel stapjes je code doet.
Je kijkt in de som welke n de grootste is en die zet je tussen de haakjes, het getal laat je weg.
, 1.4 Problem solving
Voor problem solving volg je de volgende stappen:
1. Lees het probleem minstens tweemaal volledig door
2. Los het probleem handmatig op met 3 sets van voorbeeld data
a. Input, proces, output
3. Optimaliseer de handmatige oplossing
a. Stappen vereenvoudigen
b. Andere oplosingen bekijken/zoeken
4. Schrijf de handmatige oplossing uit in pseudo-code
5. Zet de pseudo-code om in echte code
a. Probleem is opgelost, nu kunnen we gaan coderen
6. Optimaliseer de code
7. Test de code
Niet doen: direct programmeren
