DD1320 Tillämpad datalogi 2010

Hemtal 2

A) Teorifrågor

1. Hur snabb är binärsökning? Ange som funktion av n och berätta vad n är!
2. Hur många ord finns i Svenska Akademiens Ordlista (SAOL)
3. Vad är 2¹⁷  ?
4. Hur många jämförelser behöver du göra (som mest) för att hitta ett ord i SAOL med binärsökning?
5. Hur många multiplikationer behövs vid matrismultiplikation av två kvadratiska matriser? Ange som funktion av n och berätta vad n är!
6. Varför är det viktigt att ha ett basfall i rekursiva funktioner?
7. Ett binärt träd kan skrivas ut i inorder, preorder eller postorder. Vad är skillnaden?
8. Vad är höjden av ett balanserat binärt träd med n noder?

B) Rita ett binärt sökträd

• Tänk dig att du har ett program som läser in ett ord i taget och sorterar in ordet i ett binärt sökträd (bokstavsordning). Rita hur trädet skulle se ut om man i tur och ordning lägger in orden:
  lanterna, kristallkrona, stearinljus, taklampa, cykellyse, nattlampa, ficklampa.

C) Förberedelse för problemträd

• Titta på bilspelet: trafikkaos (det är samma spel i flera implementationer - välj vilken du vill).
• Rita av startpositionen för bilarna och numrera dom.
• Hur många olika sätt finns det att flytta någon bil i startläget? Skriv upp alla möjligheter (t ex "Flytta bil 1 en ruta uppåt")
• Hur många steg behöver du för att få ut den lilla folkvagnen? Skriv ner hur du gör!