Op universiteiten, hogescholen en andere onderwijsinstellingen zitten voortdurend studenten te zweten op hun tentamens. De Ingenieur vroeg zich af: wat brengt u er nog van terecht? Hier vindt u de antwoorden op de laatste vraag die in het blad heeft gestaan. 

Het vak

De tentamenvraag kwam uit het eerstejaarsvak The diamonds of computer science van de Universiteit Twente, meer specifiek uit de module Software diamond, gegeven door hoogleraar informatica Marieke Huisman. Het onderwerp was algoritmiek: dat gaat over de recepten die stap voor stap aangeven wat de computer moet doen om een gewenste opdracht uit te voeren. In deze opgave is die opdracht het zoeken naar de grootste en kleinste usb-stick in een verzameling.

De tentamenvraag

De opdracht luidde: 

Je wil zowel de hoogste als de laagste opslagcapaciteit bepalen van een verzameling usb-sticks die op je bureau liggen. 

(a) Schrijf een algoritme in gewone woorden, met genummerde en ondubbelzinnige stappen, waarmee dat kan. Per stap mogen slechts twee usb-sticks met elkaar worden vergeleken. 

(b) Hoeveel stappen zijn er nodig als functie van n: de totale hoeveelheid usb-sticks? Verklaar je antwoord.

Antwoord en uitwerking

De meest genoemde ‘standaardmethode’ bij deze opgave, is deze:

1)      Pak een usb-stick. Dit is voorlopig de grootste.

2)      Pak de volgende stick (B) en vergelijk deze met die in je hand (A)

3)      Is A groter dan B, leg B dan bij de verzameling ‘gecheckt’ en houdt A in je hand. Is A kleiner dan B, leg A dan bij de verzameling ‘gecheckt’ en houdt B in je hand – dat is nu de voorlopige grootste.

4)      Ga weer naar stap 2, tot je alle sticks hebt gecheckt en de grootste in je hand hebt.

Herhaal de hele procedure  om het minimum te bepalen, maar zoek dan naar de kleinste. (De grootste die je bij vorige procedure hebt gevonden kun je nu weglaten).

Aantal stappen:

Om het maximum te vinden zijn met deze methode (n-1) vergelijkingen tussen twee sticks nodig. (Want je vergelijkt elke stick met het voorlopige maximum, behalve de eerste). Het aantal benodigde vergelijkingen om zowel de grootste als de kleinste stick te vinden, is dus 2n-3.

Snellere methode

Een slimme, snellere methode, is deze:

1)      Pak steeds 2 usb-sticks en vergelijk ze met elkaar. Leg telkens de grootste op stapel A en de kleinste op stapel B. De grootste stick van allemaal moet nu wel in stapel A zitten, en de kleinste in stapel B.

2)      Volg voor stapel A (die nu n/2 sticks bevat) de standaardprocedure om het maximum te vinden, en voor stapel B de standaardprocedure om het minimum te vinden.

Het totaal aantal vergelijkingen dat in dit geval nodig is, is (n/2) voor stap 1, en twee keer (n/2 – 1) voor stap 2. Het totaal aantal vergelijkingen is dan dus 3n/2 – 2.

---- 

(Op het echte tentamen moesten studenten opschrijven wat ONGEVEER het aantal benodigde vergelijkingen was. Dat omdat het er in de praktijk vooral om gaat of de toename met n lineair is of exponentieel. In dat geval is 2n voldoende.)