Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 17. apríl fyrir kl 16:00
Gefum okkur að við séum með endalausan straum af gildum. Við getum byrjað að lesa strauminn á tilteknum tímapunkti en hann hættir aldrei. Slíkur straumur gæti til dæmis innihaldið fyrirspurnir á Google leitarvélina, Twitter skilaboð, o.s.frv.
Okkur langar til að vita K algengustu gildin (top K) í straumnum á hverjum tímapunkti í lestrinum.
Til að flækja málin þá skulum við gera ráð fyrir því að það séu svo mörg mismunandi gildi í straumnum að einföld talning með hakkatöflu er útilokuð því við höfum ekki pláss fyrir öll gildin. En á móti skulum við gera ráð fyrir að talningin þurfi ekki að vera alveg nákvæm -- við erum tilbúin að sætta okkur við skekkjur (en ætlum ekki að fara neitt nákvæmlega út í hversu mikla skekkju.)
Til að leysa verkefnið þá skuluð þið útfæra einfalda útgáfu af s.k. Count Min Sketch (CM) (gagnamót fyrir líkindafræðilega samantekt á gildum). Þið getið notað CM gagnamótið til að halda utan um tíðni gilda (innan vissra skekkjumarka).
Til að halda utan um top K gildin á hverjum tíma þá skuluð þið nota hrúgu með K gildum. Þegar nýtt gildi kemur inn þá er því bætt inn í CM gagnamótið, tíðni þess gildi er athuguð og ef hún er hærri en lægsta top K gildisins í hrúgunni og gildið er ekki þegar í hrúgunni þá skiptið þið minnsta gildinu út (og þurfið að koma hrúgunni á rétt form aftur), en ef gildið er þegar í hrúgunni þá uppfærið þið tíðni þess og lagfærið hrúguna.
Útfærslan á CM sketch byggir á sambærilegri hugmynd og svokallaðir Bloom filters. Bæði gagnamótin hafa það sameiginlegt að þurfa safn af H tætiföllum og útfærsla þeirra er það flóknasta í útfærslunni á bloom filters og CM.