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 10. apríl fyrir kl 16:00
Leysið dæmi 3.4.1 í bókinni.
Insert the keys E A S Y Q U T I O N in that order into an initially empty table of M = 5 lists, using separate chaining. Use the hash function 11*k % M to transform the kth letter of the alphabet into a table index.
Leysið dæmi 3.4.10 í bókinni.
Insert the keys E A S Y Q U T I O N in that order into an initially empty table of size M = 16 using linear probing. Use the hash function 11*k % M to transform the kth letter of the alphabet into a table index. Redo this exercise for M = 10.
Leysið dæmi 5.2.3 í bókinni.
Draw the R-way trie that results when the keys:
now is the time for all good people to come to the aid ofare inserted in that order into an initially empty trie (do not draw null links)
Leysið dæmi 5.2.4 í bókinni.
Draw the TST that results when the keys:
now is the time for all good people to come to the aid ofare inserted in that order into an initially empty TST.
Úthlutun símanúmera til landa byggist á forskeytum. Til dæmis hefur Ísland forskeytið 354 en Svíþjóð forskeytið 46. Öll símanúmer sem byrja á 354 tilheyra Íslandi, en öll símanúmer sem byrja á 46 tilheyra Svíþjóð.
Úthlutun símanúmera innan landa byggist einnig á forskeytum. Þannig tilheyrir, til dæmis, 354558 Vodafone, 354560 Símanum, og 354770 Nova.
Eitt forskeyti getur líka verið undirforskeyti fyrir annað forskeyti. Til dæmis hefur USA alþjóðlega forskeytið 1 en Bermuda eyjarnar hafa forskeytið 1441. Símanúmerið 1-441-12345 tilheyrir því Bermuda en ekki USA.
Til að finna rétt forskeyti fyrir gefið númer þá þarf að finna lengsta forskeytið sem passar við númerið. Þetta heitir á ensku "longest prefix match" (lengsta forskeyti sem passar).
Hröð uppfletting á lengsta forskeyti er mikilvægt verkefni í fjarskiptum og kemur til dæmis fyrir í leiðarvísun (routing) í símstöðvum, gjaldfærslu símtala, leiðarvísun (routing) í IP netum og fleiru.
Símanetið byggist upp á mörgum samtengdum netum. Símafyrirtæki rekur sitt net og samtengist öðrum símafyrirtækjum sem reka sín net. Símtöl eru síðan send á milli fyrirtækja eftir þörfum.
Símafyrirtæki gefa út verðskrár fyrir öll forskeyti sem þeir eru tilbúnir að taka á móti. Þið eigið að skrifa forrit sem les slíka skrá og getur flett upp lengsta forskeyti fyrir símanúmer sem eru lesin af aðalinntaki.
Sækið eftirfarandi skrá: rates.csv, sem inniheldur uþb. 14 þúsund alþjóðleg forskeyti á eftirfarandi sniði:
(Þetta er alvöru verðskrá frá stóru alþjóðlegu símafyrirtæki.)
Skrifið forrit sem virkar á eftirfarandi hátt. Það byrjar á því að lesa rates.csv inn í TST. Síðan les það símanúmer af aðalinntaki (eitt símanúmer per línu) og prentar út upplýsingar um lengsta forskeyti sem passar.
Dæmi um keyrslu:
hhg@hhg:~/t2/V12$ java Rating 3548967121 35489 -> 354 : Iceland : Telecom Mobile : 0.1100 18008474096 1800 -> 1 : Usa : North America 8xx Term. : 0.0150 442084332000 44208 -> 44 : United Kingdom : London : 0.0060 3545885522 354 -> 354 : Iceland : Other : 0.0148 999999999 999999999 - Not found