Hemtal 4

A) Hashning

• Vad använder man en hashtabell till?
• Beskriv ett sätt att hantera krockar. Rita gärna!
• Varför brukar % n ingå i hashfunktioner?
• Hitta på en hashfunktion för kth-id (t ex u1qz48cx).
• Om du stoppar in ditt kth-id, vad ger din hashfunktion för värde då?
• Nämn en egenskap som skiljer ett bloomfilter från en vanlig hashtabell.

B) Sortering

• Vad blir 1 + 2 + 3 + ... + n-1 ? Visa genom att summera första och sista termen, andra och näst sista osv.
• Vilken komplexitet har urvalssortering?
• Föreslå ett användningsområde för räknesortering!
• Visa hur mergesort fungerar för de första sex bokstäverna i ditt namn.
• Skulle du använda quicksort eller bubbelsortering i ett program som ska sortera tio objekt?
• När fungerar quicksort dåligt? Rita och förklara!

C) Heap

• Vad är heap-villkoret?
• En heap är ett slags binärträd implementerat som en vektor. Var i vektorn (på vilka index) hamnar barnen till det 2:a elementet?
• Lägg in de fyra sista siffrorna i ditt personnummer i en min-heap (siffrorna behöver inte vara unika). Rita upp heapen som ett binärträd.
• Tänk nu att vi gör get(). Hur kommer heapen att förändras? Rita tre bilder av binärträdet som visar hur heapen beter sig när talet plockas ut. (Eller rita hur det ser ut när du lägger in ett nytt tal med put().)
• Rita nu upp den nya heapen som en vektor.
• Vad är heapsort?