Hemtal 2 Hemtal 2

1. Hur snabb är binärsökning? Ange som funktion av n och berätta vad n är! How fast is binary search? Enter as a function of n and tell me what n is!
2. Hur många ord finns i Svenska Akademiens Ordlista (SAOL) How many words are in the Swedish Academy's Dictionary (SAOL)
3. Vad är 2 ¹⁷ ? What is 2 ^17?
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? How many comparisons do you do (at most) to find a word in SAOL with binary search?
5. Hur många multiplikationer behövs vid matrismultiplikation av två kvadratiska matriser? Ange som funktion av n och berätta vad n är! How many multiplications are needed for matrix multiplication of two square matrices? Enter as a function of n and tell me what n is!
6. Varför är det viktigt att ha ett basfall i rekursiva funktioner? Why is it important to have a base case of recursive functions?
7. Ett binärt träd kan skrivas ut i inorder, preorder eller postorder. Vad är skillnaden? A binary tree can be printed in the Nordic region, preorder or mail order. What's the difference?
8. Vad är höjden av ett balanserat binärt träd med n noder? What is the height of a balanced binary tree with n nodes?

• 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: Imagine you have a program that reads one word at a time and sorts the word in a binary search tree (alphabetical order). Draw the tree would look like if we in turn put into words:
  lanterna, kristallkrona, stearinljus, taklampa, cykellyse, nattlampa, ficklampa. lantern, chandelier, candles, ceiling light, bicycle lights, night light, flashlight.

• Titta på bilspelet: trafikkaos (det är samma spel i flera implementationer - välj vilken du vill). Bilspelet Watch: traffic chaos (that's the same game in multiple implementations - select what you want).
• Rita av startpositionen för bilarna och numrera dom. Plot of the starting position of the cars and renumber them.
• Hur många olika sätt finns det att flytta någon bil i startläget? How many ways are there to move a car in the starting position? Skriv upp alla möjligheter (t ex "Flytta bil 1 en ruta uppåt") Write down all the possibilities (eg, "Move the car up 1:01 a.m. box")
• Hur många steg behöver du för att få ut den lilla folkvagnen? How many steps do you need to get the little people of the wagon? Skriv ner hur du gör! Write down how you do!