Studiewijzer onderwijsdeel Datastructuren en Algoritmen.

© Harry Broeders.

onderwijsdeel:	Datastructuren en Algoritmen.
onderwijseenheid:	SYSO1
code onderwijsdelen	SYSO1I0T1 en SYSO1I0P1
studiebelasting:	112 SBU
semester / kwartaal:	IH3 SYSO / 1
contacturen:	3 uur/week college en 2 uur/week practicum
toetsing:	tentamen (cijfer) en practicumbeoordeling (O/V)
benodigde voorkennis:	Programmeervakken uit H1 en H2.
verantwoordelijke docent:	Harry Broeders

Inleiding

In de vorige semesters heb je datastructuren zoals array en struct leren gebruiken. Deze datastructuren worden statisch genoemd omdat hun grootte tijdens het compileren wordt bepaald en vast is. In de praktijk heb je al snel behoefte aan zogenaamde dynamische datastructuren waarvan de grootte tijdens het uitvoeren van het programma kan wijzigen. In de vorige semesters heb je ook al kennisgemaakt met enkele dynamische datastructuren (string, vector, tree). Tijdens dit onderwijsdeel worden alle klassieke dynamische datastructuren behandeld. Daarbij ligt de nadruk op de eigenschappen en het gebruik van deze datastructen. Van enkele datastructuren wordt ook de implementatie behandeld. In de vorige semesters heb je al enkele bekende algoritmen leren kennen. In dit onderwijsdeel zul je leren hoe het met behulp van templates mogelijk is om algoritmen zoals zoeken en sorteren generiek te definiëren. Een generiek algoritme is een algoritme dat onafhankelijk is van de gebruikte datastructuur.

In H1 heb je de basisaspecten van object georiënteerd programmeren (OOP) geleerd aan de hand van de programmeertaal C++. In deze onderwijseenheid wordt dieper op deze programmeertaal ingegaan. Het opvangen van fouten door middel van exceptions wordt besproken en ook namespaces en run-time type information komen aan de orde.

In de C++ ISO/ANSI standaard is een verzameling generieke algoritmen en datastructuren opgenomen die in deze onderwijseenheid worden behandeld.

Je zult na afloop van het dit onderwijsdeel in staat zijn om standaard algoritmen en datastructuren te gebruiken. Je kunt programma's die gebruik maken van deze algoritmen en datastructuren ontwerpen, implementeren en testen. Je kunt uitgaande van de eisen die aan een programma gesteld worden de juiste standaard algoritmen en datastructuren selecteren.

Globale leerdoelen

Als je dit onderwijsdeel met een voldoende hebt afgesloten:

• snap je het nut van dynamische datastructuren (in plaats van statische datastructuren).
• snap je dat niet alleen code maar ook data recursief gedefinieerd kan worden.
• ken je het begrip "orde van een algoritme" en de big-O notatie.
• ken je de eigenschappen, voor- en nadelen van de meest gebruikte datastructuren.
• ken je een aantal toepassingen van de meest gebruikte datastructuren.
• kun je gebruik maken van als ADT's gedefinieerde datastructuren.
• kun je met behulp van templates eenvoudige datastructuren implementeren.
• weet je hoe in C++ onverwachte omstandigheden en fouten op een nette manier afgehandeld kunnen worden door het gebruik van exceptions.
• weet je hoe je software exception save kunt maken.
• ben je bekend met het begrip namespace en weet je hoe namespaces gebruikt kunnen worden om meerdere class libraries te combineren.
• heb je een overzicht van de in de ISO/ANSI standaard C++ opgenomen containers, algoritmen en iteratoren.
• kun je de in de ISO/ANSI standaard C++ opgenomen eenvoudige containers, algoritmen en iteratoren met behulp van je boek gebruiken.
• herken je bij het ontwerpen van een programma de mogelijkheden voor het gebruik van standaard algoritmen en datastructuren.
• kun je bij het ontwerpen van een programma een goed afgewogen keuze maken tussen de verschillende standaard algoritmen en datastructuren.

Literatuur

Data Structures and Problem Solving Using C++, 2/E, Mark Allen Weiss, ISBN: 0-201-61250-X, Addison Wesley, Copyright: 2000, 879 pp 

Broeders, Sheets en voorbeeldprogramma's.
De sheets zijn beschikbaar in het PDF formaat, verkleind tot 9 per pagina. De voorbeedprogramma's zijn opgenomen in een Borland C++ Builder 6 project group.

Broeders, Dictaat Algoritmen en Datastructuren. Dit dictaat is verkrijgbaar in de winkel van de THR en bevat:

• deze studiewijzer.
• een handleiding voor het practicum.

Toetsing en beoordeling.

Er worden voor deze onderwijseenheid twee deelresultaten vastgesteld waarbij het eerste resultaat (tentamen) een cijfer (1..10) is en het tweede resultaat (practicum) een O(nvoldoende) of V(oldoende) is. Het eindresultaat wordt dan het cijfer van het tentamen als het tweede resultaat een V is en een 1 als het tweede resultaat een O is. Bij het tentamen mag je boeken en het dictaat gebruiken. Het tentamen bestaat uit open vragen.

Het practicum wordt beoordeeld met Onvoldoende of Voldoende. Alle opdrachten worden afzonderlijk beoordeeld met een voldoende of onvoldoende aan de hand van:

• een demonstratie om de juiste werking aan te tonen.
• een inhoudelijk gesprek over opzet en uitvoering van de implementatie. Tijdens dit gesprek zal de docent enkele vragen stellen over de manier van aanpak en/of de werking van het programma. Als je deze vragen (over je eigen programma) niet kunt beantwoorden dan krijg je onvoldoende! Als bij jou een opdracht met onvoldoende wordt beoordeeld krijg je 1 keer de kans een vervangende opdracht te maken.

Om het practicum met een voldoende af te sluiten moeten alle opdrachten voldoende zijn.

Weekplanning theorie.

les	inhoud	boek
1	Inleiding	H6. Algorithm Analysis.
2	Overzicht datastructuren	-
3	Toepassingen van een stack	H12. Stacks and Compilers.
4	Implementaties van een stack	H16. Stacks and Queues.
5	Advanced C++ (o.a. vector, namespace)	nog niet in voorgaande semesters behandelde delen van H1 t/m H4 en Appendix A.
6	Advanced C++ (exceptions)	-
7	Advanced C++ (vervolg exceptions casting, RTTI).	-
8	Design Patterns (Functor, Adaptor, Iterator)	nog niet in voorgaande semesters behandelde delen van H5
9	STL inleiding (string, overzicht, sequentiële containers)	H7. The Standard Template Library.
10	STL container adapters en associatieve containers	H7. The Standard Template Library.
11	STL iterators, inleiding algoritmen	H7. The Standard Template Library.
12	STL algoritmen en functie objecten	H9. Sorting Algorithms.
13	Behandelen vraagstuk (galgje) of uitloop	-
14	Toepassingen: Spelletjes	H8. Recursie. H11. Fun and Games.
15	Toepassingen: Schaken (min-max algoritme, alpha-beta pruning)	H11. Fun and Games.
16	Toepassingen: Compressie	H13. Utilities.
17	Toepassingen: Simulatie Internet Provider 1	H14. Simulation.
18	Graphs	H15. Graphs and Paths.
19	Algoritmen voor graphs (kortste pad)	H15. Graphs and Paths.
20	Implementatie: Hashing 1	H20. Hash Tables.
21	Implementatie: Binary Heap1	H21. A Priority Queue: The Binary Heap.

¹ Deze onderwerpen zijn in het najaar van 2003 niet behandeld.

Globale planning practicum.

week	opdracht
1	Homemade gelinkte lijst (toepassen van dynamisch geheugen, recursieve data en recursieve algoritmen).
2	Vergelijken van bubble sort O(n2) en quick sort (n·log n). Bepalen van de orde van een zelf ontworpen functie om het meerderheidselement in een array te bepalen (toepassen van algoritme analyse).
3	Fouten afvangen bij een generieke stack (toepassen van exceptions).
4	Quick sort generiek maken (toepassen van templates, functiepointers en functors).
5	Opsporen van fraude (toepassen van map, iteratoren en algoritmen).
6	Boter Kaas en eieren (toepassen van minimax algoritme met alpha-beta pruning en transposition table).
7	Uitloop.

Gedetailleerde planning theorie.

Les 1. Algemene inleiding en algorithm analysis.

• Dictaat: studiewijzer, inleiding en hoofdstuk 1.
• Sheets: 1 t/m 7 en ES1.
• Boek: hoofdstuk 6:
  • Inleiding en 6.1 bestuderen.
    Inleiding over algorithm analysis en verklaring big-Oh notation.
  • 6.2 bestuderen.
    Enkele voorbeelden van algoritmen van verschillende ordes.
  • 6.3 overslaan.
    In deze paragraaf worden 3 oplossingen gegeven voor het zelfde probleem alle oplossingen zijn van een andere orde. Wij komen later nog genoeg van dit soort voorbeelden tegen.
  • 6.4 eerste deel (tot laatste 6 regels op blz. 209) overslaan.
    In dit deel worden de big-Omega, big-Theta en Little-Oh notaties besproken. Wij gebruiken alleen de big-Oh notatie.
  • 6.4 tweede deel (vanaf laatste 6 regels op blz. 209) bestuderen.
    De tabel in dit deel komt overeen met de tabel van sheet ES1.
  • 6.5 bestuderen behalveTheorem 6.5.
    In deze paragraaf wordt het wiskundige begrip logaritme uitgelegd. Het is heel belangrijk dat je begrijpt dat bij het telkens halveren van N elementen je na ²log N stappen nog maar 1 element over hebt.
  • 6.6 overslaan.
    Sequentieel en binair zoeken komen in les 2 aan de orde.
  • 6.7 bestuderen.
    Laat zien hoe je uit een reeks metingen van de executietijd (bij verschillende waarden van N) kunt bepalen wat de orde van het algoritme zou kunnen zijn.
  • 6.8 bestuderen.
    Behandeld de beperkingen van de big-Oh notatie.

Les 2. Overzicht van de belangrijkste datastructuren.

• Dictaat: hoofdstuk 2.
• Sheets: 8 t/m 10, 12 en ES2.
• Boek: hoofdstuk 6:
  •  6.6, 6.6.1 en 6.6.2 bestuderen.
    Sequentieel zoeken is O(n) en binair zoeken is O(n·log n).
• Boek: hoofdstuk 7:
  • inleiding en 7.1 bestuderen.
    Algemene inleiding over datastructuren.
  • 7.2 bestuderen
    Inleiding stacks en queues (nog zonder gebruik van de standaard C++ library).

Les 3. Toepassingen van een stack.

• Dictaat: hoofdstuk 3.
• Sheets: 10, 11, 13 t/m 18.
• Boek: hoofdstuk 12:
  • inleiding, 12.1 en 12.1.1 bestuderen.
    Hier wordt het algoritme van de balanced symbol checker besproken.
  • 12.1.2 mag je overslaan.
    Dit is de implementatie van het balanced symbol checker algoritme. Wij hebben een veel eenvoudigere implementatie besproken (paragraaf 3.1 van het dictaat). De implementatie in het boek kan gebruikt worden om haakjes in C++ programma's te controleren. Hierbij worden haakjes in commentaar of in letterlijke strings buiten beschouwing gelaten! Ook worden de regelnummers bijgehouden zodat in het geval van een foutmelding het betreffende regelnummer kan worden afgedrukt. Het basisalgoritme is echter hetzelfde als het door ons besproken algoritme. Vergelijk het programma uit paragraaf 3.1 van het dictaat met Figure 12.8 en 12.9 uit het boek.
  • 12.2, 12.2.1 en 12.2.2 bestuderen.
    Hier worden de algoritmen van de simple postfix calculator en van de infix naar postfix converter besproken.
  • 12.2.3 mag je overslaan.
    Dit is de implementatie van een infix calculator. Wij hebben een eenvoudige implementatie van een postfix calculator die kan optellen en vermenigvuldigen besproken (paragraaf 3.2.2 van het dictaat). De implementatie in het boek bevat ook een infix naar postfix converter en kan optellen, aftrekken, vermenigvuldigen, delen en machtsverheffen. Het basisalgoritme is echter hetzelfde als het door ons besproken algoritme. Vergelijk het programma uit paragraaf 3.2.2 van het dictaat met Figure 12.19 uit het boek.
  • 12.2.4 overslaan.
• Programma's:
  • Alle programma's voor les 3 t/m 13 in 1 zip bestand.

Les 4. Implementaties van een stack.

• Dictaat: hoofdstuk 4.
  In dit hoofdstuk worden vele C++ technieken toegepast. Waarschijnlijk moet je sommige delen uit het H1 C++ dictaat opnieuw bestuderen.
• Sheets: 19 t/m 28.
• Boek: hoofdstuk 16:
  • inleiding bestuderen.
    In de in het dictaat besproken implementaties van een stack is gekozen voor het gebruik van een gemeenschappelijke abstract base class. Det maakt het mogelijk om tijdens het uitvoeren van een programma te kiezen voor een bepaalde implementatie (paragraaf 4.3 van het dictaat). De in het boek besproken implementaties maken geen gebruik van een abstact base class. De keuze voor een bepaalde implementatie moet dus al tijdens het vertalen van het programma worden bepaald. In de later te bespreken standaard stack implementaties wordt ook geen gebruik gemaakt van een abstract base class. Toch is het erg leerzaam om dit eens een keer gezien te hebben.
  • 16.1 mag je overslaan.
    Bij deze array implementatie van een stack (en queue) is gebruik gemaakt van een standaard vector. Wij hebben een implementatie besproken (paragraaf 4.1 van het dictaat) die gebruik maakt van een array. De stack uit het boek "groeit" automatisch indien nodig door middel van de zogenaamde "array doubling" methode. Deze methode wordt ook in hoofdstuk 1 van het boek behandeld (bespreken wij in les 5). Deze stack "krimpt" echter nooit meer. Verder maakt deze implementatie gebruik van exceptions. Wij zullen exceptions pas in les 5 bespreken.
  • 16.2 mag je overslaan.
    Bij deze linked list implementatie van een stack (en queue) is gebuik gemaakt van een private struct ListNode. Wij hebben een implementatie besproken (4.2 van het dictaat) die gebruik maakt van een private class Node (met public datamembers). Omdat een struct in C++ hetzelfde is als een class met (default) public members is de implementatie uit het boek in principe gelijk aan die uit het dictaat. Er zijn 2 grote verschillen:
    1. De implementatie uit het boek maakt gebruik van exceptions. Wij zullen exceptions pas in les 5 bespreken.
    2. De implementatie uit het boek implementeert een assignment operator en copy constructor. De implementatie uit het dictaat heeft deze bewerkingen onmogelijk gemaakt (door ze private te declareren).
  • 16.3 bestuderen
    Vergelijkt de twee besproken implementatie methoden. Eventueel pas bestuderen na les 5 (waar array doubling) wordt besproken.
  • 16.4 overslaan.
    De in de C++ standaard opgenomen implementatie van stack zullen wij later bespreken.
  • 16.5 overlaan.

Les 5 Advanced C++ (o.a. vector, namespace).

• Dictaat: hoofdstuk 5.1.
• Sheets: 29 t/m 48 (34 t/m 38, 47 en 48 zelf bestuderen).
• Boek: hoofdstuk 1:
  • inleiding bestuderen.
  • 1.1 herhaling van wat je al weet (overslaan).
  • 1.2 bestuderen.
    De standaard class string hebben we al in H1 besproken de standaard class vector niet. Je hebt echter al wel kennis gemaakt met array's in Java (vergelijkbaar met vector in C++). Paragraaf 1.2.1 t/m 1.2.4 bevatten nieuwe stof en paragraaf 1.2.5 t/m 1.2.8 zijn een herhaling.
  • 1.3 herhaling van wat je al weet (overslaan).
  • 1.4 herhaling van wat je al weet (overslaan).
    Op blz. 22 wordt het begrip "stale pointer" besproken. Je weet al lang wat dat is maar je wist misschien nog niet dat het zo genoemd wordt.
  • 1.5 herhaling van wat je al weet (overslaan).
  • 1.6 herhaling van wat je al weet (overslaan).
    Op blz. 30 worden de begrippen "indigenous data" en "exogenous data" besproken. Je weet al lang wat dat is maar je wist misschien nog niet dat het zo genoemd wordt.
    Op blz. 30 worden de begrippen "shallow copy" en "deep copy" besproken. Je weet al lang wat dat is maar je wist misschien nog niet dat het zo genoemd wordt.
• Boek: hoofdstuk 2:
  Dit hele hoofdstuk is een herhaling van wat je al weet (overslaan), behalve:
  • 2.4.2 bestuderen.
    Static class members in C++ zijn nog niet behandeld (maar wel in Java).
  • 2.4.3 bestuderen.
    Een enum is in C++ een alternatief voor const static datamembers.
  • 2.5 bestuderen.
    Exceptions in C++ zijn nog niet behandeld (maar wel in Java). Het boek gaat hier niet diep op in. Wij wel in de volgende les (paragraaf 5.2. van het dictaat).
• Boek hoofdstuk 3:
  Dit hele hoofdstuk is een herhaling van wat je al weet (overslaan), behalve:
  • 3.6.2 bestuderen.
    Default template parameters hebben wij niet besproken (maar spreekt voor zich als je default functie parameters hebt gehad).
• Boek hoofdstuk 4:
  Dit hele hoofdstuk is een herhaling van wat je al weet (overslaan), behalve:
  • 4.1 gedeeltelijk bestuderen.
    Figuur 4.1 en 4.2 geven twee voorbeelden van het gebruik van overerving in de standaard C++ library. Figuur 4.1 sluit goed aan bij paragraaf 5.2.3 van het dictaat die in de volgende les wordt behandeld.
  • 4.4.1 bestuderen.
    Wij hebben ook al eens besproken dat overerving en overloading niet goed samengaan (vanwege de hiding rule zie eventueel 4.4.3) deze paragraaf geeft nog een tweede probleem bij de combinatie van overerving en overloading. Vooral de problemen die bij het optreden van het overloaden van de operator<< kunnen optreden en de oplossing daarvoor zijn belangrijk.
  • 4.4.2 bestuderen.
    Hier blijkt dat default functie parameters en overerving ook niet goed samengaan.
  • 4.4.4 bestuderen.
    Covariant return types for overridden methods maakt het klonen van honden mogelijk.
  • 4.4.5 overslaan.
  • 4.5 overslaan.
• Boek: Appendix A:
  Dit hele hoofdstuk is een herhaling van wat je al weet (overslaan), behalve:
  • A.4.3 bestuderen.
    Met behulp van de standaard class istringstream kunnen we met de operator>> lezen uit een string (op dezelfde manier als lezen uit een file of vanaf het toetsenbord). Met behulp van de standaard class ostringstream kunnen we met de operator<< schrijven in een string (op dezelfde manier als schrijven in een file of naar het beeldscherm).
  • A.5 bestuderen.
    Namespaces worden ook in paragraaf 5.1 van het dictaat besproken.

Les 6. Advanced C++ (exceptions).

• Dictaat: grootste deel van 5.2.
• Sheets: 49 t/m 59.

Les 7. Advanced C++ (vervolg exceptions, casting, RTTI).

• Dictaat: rest van 5.2 en 5.3.
• Sheets: 60 t/m 70.

Les 8. Design Patterns (Functor, Adaptor, Iterator).

• Sheets: 71 t/m 82.
• Boek: hoofdstuk 5:
  • inleiding en 5.1 herhaling van wat je al weet (overslaan). Misschien moet je het "Design Patterns" boek dat in H2 behandeld is er nog eens op naslaan.
  • 5.2 bestuderen.
    Functor is een design pattern dat in de standaard C++ library veel wordt gebruikt.
  • 5.3 gedeeltelijk bestuderen
    Als voorbeeld van een wrapper (adapter) zullen we de C++ standaard auto_ptr template class bespreken (blz. 64 7 regels van onder t/m blz. 166 15 regels van onder). Dit sluit ook mooi aan bij het eerder besproken exception save programmeren. De rest van deze paragraaf mag je overslaan. Het adapter design pattern staat ook in het GoF (Gang of Four) boek wat jullie het vorig semester hebben gebruikt.
  • 5.4 herhaling van wat je al weet (overslaan).
  • 5.5 bestuderen.
    De in de C++ standaard pair class template is geen composite (in tegenstelling tot wat het boek beweerd).
  • 5.6 herhaling van wat je al weet (overslaan).

Les 9. STL inleiding (string, overzicht, sequentiële containers).

• Dictaat: paragraaf 6.1.
• Sheets: 83 t/m 95.
• Boek: hoofdsuk 1:
  • 1.2.1 t/m 1.2.4 hebben we al gedaan in les 5.
• Boek: hoofdstuk 7:
  • inleiding, 7.1 en 7.2 hebben we al gedaan in les 2.
  • 7.3 bestuderen.
    Algemene eigenschappen van containers en iteratoren. De verschillende soorten iteratoren komen in les 11 uitgebreider aan de orde.
  • 7.4 nu overslaan, wordt behandeld in les 11 en 12.
  • 7.5 overslaan.
    De implementatie van een vector is niet zo belangrijk. Het is veel belangrijker dat je een vector kunt gebruiken!
  • 7.6 t/m 7.6.1 bestuderen.
• Boek: hoofdstuk 17:
  • 17.5 Als je geïnteresseerd bent in de implementatie van het in de STL gedefinieerde list container kun je deze paragraaf bestuderen. Ik behandel dit niet omdat voor ons als HBO-ers de toepassingen van containers belangrijker zijn dan de implementaties.

Les 10. STL container adapters en associatieve containers.

• Dictaat: paragraaf 6.2 t/m 6.5.
• Sheets: 96 t/m 105.
• Boek: hoofdstuk 7:
  • 7.6.2 bestuderen.
    Container adapters: stack en queue. Je kunt eventueel het Adapter Design Pattern uit het "Design Patterns" boek dat in H2 behandeld is er nog eens op naslaan. Weiss beweert in de laatste zinnen van paragraaf 7.6.2: "The queue does not use standard names such as enqueue en dequeue. Instead it uses push, pop and top. Thus there is no compelling reason to use the queue; these names are more misleading than the names in the list class. Seemingly, then, only the stack is worth using." De schrijver is in dit geval wat eigenzinnig (komt vaker voor ;-). Ik ben het echter niet met hem eens. Volgens het design pattern boek is een van de redenen van het gebuik van een adapter dat er een restrictie (beperking) kan worden opgelegd aan de interface van de adaptee. In dit geval garandeerd het gebruik van de queue FIFO gedrag. Natuurlijk kun je met een list (of deque) ook FIFO gedrag bereiken (door aan een kant toe te voegen (push_back) en aan de andere kant te verwijderen (pop_front) maar je kunt dat niet garanderen omdat ook push_front, pop_back, insert, of erase gebruikt kunnen worden. Een queue heeft echter alleen een pop en een push met FIFO gedrag. Het voordeel van het gebruik van deze (inderdaad ongebruikelijke) namen is dat je nu een programmadeel dat werkt met een LIFO container = stack heel eenvoudig kunt omzetten naar een een programmadeel dat werkt met een FIFO container = queue omdat de memberfuncties dezelfde namen hebben. De naam van de memberfunctie om het element dat aan de beurt is te benaderen is dan jammer genoeg weer wel verschillend. Bij een stack heet deze memberfunctie top maar bij een queue heet de vergelijkbare memberfunctie front.
  • 7.7 en 7.8 bestuderen.
    Associatieve containers: set en map. In de les worden ook de multiset en multimap besproken.
    Weiss beweert: "Thus for an iterator itr, *itr is of type pair<KeyType, ValueType>". Dit moet zijn: pair<const KeyType, ValueType> zodat je een key niet via een iterator kunt veranderen! De gesorteerde binaire zoekboom (die gebruikt wordt om de map te implementeren) moet natuurlijk wel altijd op key gesorteerd blijven!
  • 7.9 bestuderen.
    Container adapter: priority_queue. Let op: de versie uit figuur 7.16 is niet de STL implementatie. Halverwege pagina 255 schrijft Weiss: "We close by mentioning that the STL priority_queue uses different conventions than presented here". Hij geeft twee redenen voor zijn eigenzinnigheid: In de STL wordt een adapter gebruikt en sommige compilers hebben problemen met default template parameters. Dit is geen goede reden want deze problemen treden alleen op bij compilers uit de vorige eeuw (zoals de Borland C++ compiler die jullie in de P fase hebben gebruikt. C++ Builder versie 5 die we nu gebruiken heeft deze problemen niet. Als tweede reden geeft hij de ongebuikelijke benamingen van de memberfuncties push, pop en top. Deze namen zijn inderdaad ongebruikelijk maar hebben als voordeel dat een programmadeel dat met een LIFO buffer = stack werkt, eenvoudig omgezet kan worden naar een programmadeel dat met een prioriteits buffer = priority_queue werkt.
• Boek: hoofdstuk 19:
  • 19.7 Als je geïnteresseerd bent in de implementatie van het in de STL gedefinieerde set en map containers kun je deze paragraaf bestuderen. Ik behandel dit niet omdat voor ons als HBO-ers de toepassingen van containers belangrijker zijn dan de implementaties.
• Boek: hoofdstuk 21:
  • 21.4 Als je geïnteresseerd bent in de implementatie van het in de STL gedefinieerde priority_queue container adapter kun je deze paragraaf bestuderen.

Les 11. STL iterators, inleiding algoritmen.

• Dictaat: paragraaf 6.6 t/m 6.8.
• Sheets: 106 t/m 115.
• Boek: hoofdstuk 7:
  • 7.4 t/m 7.4.1 bestuderen.

Les 12. STL algoritmen en functie objecten.

• Dictaat: paragraaf 6.9 t/m 6.12.
• Sheets: 116 t/m 123.
• Boek: hoofdstuk 7:
  • 7.4.2 en 7.4.3 bestuderen.
• Boek: hoofdstuk 9:
  • 9.6 Als je geïnteresseerd bent in de implementatie van het in de STL gedefinieerde sort algoritme kun je deze paragraaf bestuderen. Ik behandel dit niet omdat voor ons als HBO-ers de toepassingen van algoritmen belangrijker zijn dan de implementaties.
  • 9.7 Als je geïnteresseerd bent in de implementatie van het in de STL gedefinieerde nth_element algoritme kun je deze paragraaf bestuderen.

Les 13. Behandelen vraagstuk (galgje) of uitloop.

• Sheets: 124 t/m 128.

Les 14. Toepassingen: Spelletjes.

• Sheets: 129 t/m 133.
• Boek: hoofdstuk 11:
  • 11.1 bestuderen.
• Programma's:
  • Alle programma's voor les 14 t/m 19 in 1 zip bestand (inclusief woordenboek webster.txt).
  • Word Search Puzzle: WordSrch.cpp Maakt gebruik van Matrix.h
  • Hulpprogramma voor het sorteren van het woordenboek en het bepalen van de maximale woordlengte: SortStrings.cpp
  • Hulpprogramma voor het genereren van een puzzle: GenPuzzle.cpp De waarschijnlijkheid waarmee een letter wordt gekozen is recht evenredig met de frequentie van de letter in het woordenboek.

Les 15. Toepassingen: Schaken (min-max algoritme, alpha-beta pruning).

• Sheets: 134 t/m 141.
• Handouts: Een deel van de zoekboom: ttt.pdf
• Boek: hoofdstuk 8:
  • 8.7 bestuderen.
  • 11.2 bestuderen.
• Programma's:
  • Tic-Tac-Toe: TicTacSlow.cpp
  • Hulpprogramma om het maximaal aantal mogelijke aanroepen van chooseMove te berekenen (zonder te controleren of er al een winnaar is als het bord nog niet vol is): CalcTTTMoves.cpp
  • Tic-Tac-Toe met alpha-beta pruning en transposition table: TicTac.cpp

Les 16. Toepassingen: Compressie.

• Sheets: 142 t/m 151.
• Boek: hoofdstuk 13:
  • 13.1 bestuderen.
• Programma's:
  • Huffman compression en uncompression: Hzip.cpp

Les 17. Toepassingen: Simulatie Internet Provider.

• Programma's:
  • Modempool simulatie: Modems.cpp
  • Hulpprogramma voor het genereren van ramdom getallen met een Poisson verdeling: Random.h Random.cpp

<<nog invullen!>>¹

Les 18. Graphs.

• Sheets: 152 t/m 165.
• Boek: hoofdstuk 15:
  • 15.1 en 15.2 bestuderen.
• Programma's:
  • Unweighted shortest path in een Graph: Paths.cpp

Les 19. Algoritmen voor graphs (bijvoorbeeld: korste pad).

• Sheets: 166 t/m 181.
• Boek: hoofdstuk 15:
  • 15.3, 15.4 en 15.5 tot 15.5.4 bestuderen.
  • 15.5.4 overslaan.
• Programma's:
  • Unweighted shortest path in een Graph: Paths.cpp

Les 20. Implementatie: Hashing.

<<nog invullen!>>¹

Les 21. Implementatie: Binary Heap.

<<nog invullen!>>¹