Læringsmål#
De studerende kan efter aktiviteten:
- Forklare hvad O-notation beskriver (vækstrate, ikke præcis tid)
- Knytte konkrete datastrukturer til deres tidskompleksitet
- Argumentere for forskellen på O(1), O(n) og O(log n) med fysiske eksempler
Forudsætninger#
De studerende forventes at kende til:
- Grundlæggende datastrukturer på konceptniveau (liste, stak)
- Begrebet “algoritme”
Kort beskrivelse#
De studerende roterer rundt til seks fysiske stationer, der hver repræsenterer en datastruktur og en operation. Ved hver station udfører de en konkret handling og skriver deres bud på kompleksiteten i en tipskupon — inden svaret afsløres. Til sidst samles kuponerne og diskuteres fælles.
Pointen er at kompleksiteten skal erfares fysisk inden den formaliseres. Studerende der har stået i en menneskekæde og talt skridt ved godt hvad O(n) betyder.
Faglig kontekst#
- Semester/fag: Algorithms & Data Structures (valgfag)
- Holdstørrelse: Skalerer — justér antal studerende pr. station efter holdstørrelse
- Organisering: Grupper roterer mellem stationer; tipskupon udfyldes i grupper
Stationer#
De studerende får ikke at vide hvilke datastrukturer de forskellige stationer repræsenterer.
Station 1 — Stak (tallerkener)#
Datastruktur: Stak
Operation: Push og pop — læg en tallerken på, tag den øverste af. En stor stak og en mindre stak.
Kompleksitet: O(1)
Pointen: Uanset hvor mange tallerkener der er i stakken, tager det samme tid. Man rører aldrig de andre.
Station 2 — Array (faste pladser)#
Datastruktur: Array
Operation: (a) Gå direkte til plads nr. 7. (b) Find den studerende der holder tallet 42 — uden at kende pladsen.
Kompleksitet: O(1) for direkte access / O(n) for lineær søgning
Pointen: To operationer, samme fysiske struktur, vidt forskellig kompleksitet.
Station 3 — ArrayList (dynamisk)#
Datastruktur: ArrayList
Operation: Tilføj en studerende til listen. Find en bestemt studerende.
Kompleksitet: O(1) amortiseret for tilføjelse / O(n) for søgning
Pointen: Tilføjelse er næsten altid hurtig — men af og til skal listen udvides, og det koster. Gennemsnitligt O(1).
Station 4 — Linked list (pege på hinanden)#
Datastruktur: Linked list
Operation: Find den studerende der holder et bestemt tal — start fra den første, følg pegerne.
Kompleksitet: O(n)
Pointen: Der er ingen genvej. Man skal igennem kæden fra start.
Station 5 — Binær søgning (sorteret række)#
Datastruktur: Sorteret liste
Operation: Find en studerende med et bestemt tal — start på midten, halvér søgefeltet hver gang.
Kompleksitet: O(log n)
Pointen: Hver beslutning eliminerer halvdelen. Med 32 studerende behøver man maks 5 skridt.
Station 6 — BST (fødselsdage)#
Datastruktur: Binært søgetræ
Operation: Indsæt studerende i et træ baseret på fødselsdag (dag+måned). Gå til venstre hvis datoen er tidligere, til højre hvis den er senere. Søg derefter efter en bestemt dato.
Kompleksitet: O(log n) i det balancerede tilfælde — O(n) hvis træet er skævt
Pointen: Hvis træet tilfældigvis bliver skævt (alle til højre), er det ikke en fejl — det er en diskussion: hvad sker der med kompleksiteten, og hvorfor opfandt man balancerede træer?
Tipskupon#
Hver gruppe får en kupon med seks felter — ét pr. station. De skriver deres bud på kompleksiteten inden svaret afsløres. Opsamlingen tager udgangspunkt i kuponerne: hvad var I enige om? Hvad overraskede jer?
Materialer#
- Tallerkener (ca. 20 stk.)
- Stole i en række med numre
- Talkort til studerende (til array- og linked list-stationerne)
- Snor eller tape til at markere “pegere” i linked list (valgfrit)
- tipkupon — Én pr. gruppe
- printede opgaver og hint til hver station
Tidsforbrug#
Ca. 10 min. pr. station + 20 min. fælles opsamling. Planlæg 90 min. i alt.
Modtagelse#
Ikke prøvet endnu
Udvidelser#
- De studerende skal matche de fysiske øvelser med datastrukturer
- De studerende implementerer de samme strukturer i Java og måler faktisk køretid
- Tilføj en station med O(n²) — f.eks. boblesortering med fysiske kort
- Lad studerende designe en ny station til en medstuderende
Noter til underviseren#
Station 6 (BST med fødselsdage) kan producere et skævt træ afhængigt af hvem der indsættes først. Det er ikke et problem — det er en gave. Vær klar til diskussionen: hvornår er O(log n) en løgn? Det åbner naturligt for balancerede træer (AVL, rød-sort) senere i forløbet.
Tipskuponen er vigtig: forudsigelsen inden svaret er det der skaber det kognitive engagement. Lad grupperne diskutere før de afleverer — uenighed inden for gruppen er et godt tegn.
Under udarbejdelse:
- Konkrete opgaveformuleringer til hver station
- Tipskupon-layout
- Beskrivelse af opgaver