DM22-2002

DM22 - Obligatorisk opgave 1
Generelle kommenterer

• Dangelsk
  Mængder hedder ikke set eller sæt eller dansk.
  Knuder hedder ikke noder på dansk.
• Træ-til-liste-funktion
  Der er flere, der har lavet en træ-til-liste-funktion, der bruger mere end O(n) tid -- kig i stedet på, hvordan vi tidligere løste opgave 14.25.
• Liste-til-træ-funktion
  De fleste har lavet en løsning, der kører i O(n log n) tid. Hvis listen er sorteret, kan man faktisk lave det i O(n) tid. Dette gør, at en del andre funktioner kan laves i O(n) tid, herunder:
  • union
  • inter
  • diff
  • subSet
  • filterSet
• Kompleksitet for funktioner der tager flere parametre
  Hvis man har en funktion, som fx. subset, der tager to parametre, bruger man ofte m og n om størrelsen af disse, således at subset har kompleksiteten O(m+n).
• Andre rebalanceringsoperationer
  Der er flere, der har brugt andre rebalanceringsoperationer, end hvad angivet i opgaveformuleringen. Dette er i orden, dog skal man være klar over, at de kan gøre det nødvendigt med flere rebalanceringer, end de "rigtige" har brug for. (Dog stadig højst O(log n) -- de "rigtige" bruger i gennemsnit (amorticeret) kun O(1)).
• Test af programmet
  Dette har de fleste gjort godt. Det er dog de færreste, der har lavet en test af, om alle rebalanceringsoperationerne virker rigtigt. Dvs. et antal test-tilfælde, så alt bliver prøvet igennem.
• Parent-pointere
  Der er en del, der har forsøgt at bruge parent-pointere til deres løsning; dvs. hver knude har ud over sin egen værdi, farve og pointere til børn, en pointer til sin far. Kort fortalt er dette ikke umiddelbart muligt at gøre i Haskell: Da alt er "konstanter", kan man ikke have to knuder der peger på hinanden. For hvilken af de to skal laves først?