Samenvatting IPRO2: Programmeren van complexe vraagstukken

IPRO2 – Samenvatting

Week 1 – BigO
Wat is de BIG-O notatie:

- Een manier om over de performance van een algoritme te praten.
- Het is de worst-case complexiteit, dus in het slechtste geval.
o Kan over tijd of ruimte gaan.
- Er zijn andere notaties voor best-case en average-case complexiteit.



Definitie O (n)-notatie:

- Een algoritme heeft een worst-case tijdscomplexiteit O(f(n)), als de looptijd van het algoritme voor
grote n kleiner is dan c*f(n).
- Voorbeeld: code die 3*n tijd nodig heeft is O(n).



Hoe bepaal je de O(n) complexiteit?

- Analyseer je code en tel hoeveel stappen je maakt, bijvoorbeeld het aantal loops.
- Voorbeeld:
o 5n² + 7n + 8 stappen -> O(n²)
o 42 stappen -> O(1)
o 6 + 2n³ - n² + 8n stappen -> O(n³)
- In het voorbeeld wordt luie wiskunde gebruik, dus je zoekt naar het grootste gedeelte: n² of n³



Big O in je code:

,Week 1 – Problem Solving Theorie
Waarom problem solving:

- Moeilijk om uit ‘warrige’ probleemomschrijving de essenties te halen.
- Probleem niet begrepen, dat kan resulteren in verkeerde code.
- Het probleem begrijpen voordat je begint.
- Oplossingen bedenken voordat je begint met coderen.
- Dus: niet direct de code in duiken.



Problem Solving stappen:

1. Lees het probleem minsten tweemaal door.
2. Los het probleem handmatig op met drie sets van voorbeeld data:
a. Input
b. Proces
c. Output
3. Optimaliseer de handmatige oplossing.
4. Schrijf de handmatige oplossing uit in pseudo-code.
5. Zet de pseudo-code om in echte code.
6. Optimaliseer de code.
7. Test de code.

Als je vast loopt kan je de stappen herhalen, denk ik oplossingen en niet in problemen. Begin NIET met
programmeren, maar denk na over wat je moet doen. Onthoud dat het niet altijd in 1x goed gaat.



Week 1 – Binair zoeken
Binair zoeken:

- Zoeken in een gesorteerde lijst, als je weet hoe de data in elkaar ziet wordt binair zoeken
makkelijker, zoek de letter F.




1. Zoek het midden, als dat niet kan ga je voor de linker kant. Dit is plaats 4, dus de letter H.
2. Omdat je weet dat de F kleiner is dan H weet je dat hij aan de linkerkant moet zitten. Nummer 5
(K) t/m 9 (Z) kan je weggooien, het probleem is gehalveerd.
3. Je houdt 0 (A), 1 (D), 2 (F), 3 (G) over, ook hier kies je weer het midden (tussen 1 en 2) en vervolgens
de linkerkant. Dit is de 1 (D) en dat is kleiner dan F.
4. Nu zoek je tussen de 4 (H) en 1 (D) in, dus 2 (F) en 3 (G). Ook dit halveer je en kies de linkerkant.
Dit is 2, de F.
- In totaal zijn het maar drie stappen: kijken naar de H, kijken naar de D en vervolgens de F.
- Binair zoeken is relatief snel omdat je al vrij snel een groot deel van je data weg kan doen.
- Er zitten 10 waardes in bovenstaande array en we hebben maar 3 stappen nodig gehad om de F
te vinden.

, In pseudo-code ziet dat er als volgt uit:
Functie zoekBinair(lijst, doel):
Zolang getal niet gevonden:
Check midden van de lijst
Te groot? Zoek verder in linkerdeel
Te klein? Zoek verder in rechterdeel
Gelijk? Gevonden!

De code kan er als volgt uit zien (dit werkt niet helemaal):
zoekBinair(lijst, doel):
min = 0
max = lijst.size -1

while min <= max:
midden = (max + min)/ 2
if lijst[midden] > doel:
max = midden -1

else if lijst[midden] < doel:
min = mid +1

else
return midden

Best case binair zoeken: 1 stap

Worst case: O(log n)

Waarom: je halveert telkens je probleem, dat is log₂ (n) stappen

Andersom: rij verdubbelen is 1 stap extra.



Week 2 – debuggen
Debuggen kan met:

- Het toevoegen van printstatements.
- Het gebruiken van de IDE debugger.
- Unit testing. Met kleine stukjes code verschillende situaties testen.



Week 3 – Bubble Sort
Er is een lijst met getallen:

65318724

Bubble Sort pakt de eerste twee getallen en vergelijkt dit met elkaar, het kleinste getal wordt als eerste
neergezet:

65318724>56318724

Dit gaat zo door:

56318724>53618724