Hemtal 3
Hemtal 3
Sortering
Läs om sortering i kursboken.
Besvara sedan följande frågor:
- Gör en tabell över de sex sorteringsalgoritmer som tas upp i kapitlet ovan, med algoritmernas namn och komplexitet. (betyg E)
- Vad är den rekursiva tanken och basfallet i Mergesort? (betyg E)
- Hur ska man testa en sorteringsfunktion? Beskriv upplägget och testdata. (betyg E)
- Layton och hans ärkefiende Don Paolo skrev var sin sorteringsfunktion. Layton använde mergesort och Don Paolo selection sort (urvalssortering). När de provkörde med 1 000 element gick det lika fort eftersom Don Paolos dator är snabbare. Men Layton vann när de sorterade 32 000 element – med hans funktion tog det tio sekunder. Ungefär hur lång tid tog det för Don Paolos funktion att sortera 32 000 element? (betyg C)
- Ge en rekursiv tanke för en funktion som returnerar True om en stack är sorterad, False annars. Stacken får bara manipuleras med metoderna push, pop och isEmpty, och måste återlämnas i ursprungligt skick efter anropet. (betyg A)
Prioritetsköer, heap och bästaförstsökning
Läs om prioritetsköer och Dijkstras algoritm i kursboken.
Besvara sedan följande frågor:
- En prioritetskö har insättnings- och utplockningsoperationer. Vad är skillnaden om man jämför med motsvarande operationer för en vanlig kö? (betyg E)
- Vad är heapvillkoret, och hur tillämpas det för att justera ordningen när man plockat ut ett värde ur heapen? Visa med ett eget exempel. (betyg E)
- Anta att vi puttar in talen10 15 5 3 1 i tur och ordning i en min-heap respektive ett binärt sökträd. Visa resultatet och förklara skillnaden. (betyg C)
- I labb 4 används breddenföstsökning för att hitta kortaste vägen från fan till gud. Skulle det gå lika bra att använda bästaförstsökning med en prioritetskö? Motivera ditt svar! (betyg C)
- Beskriv (tydligt och strukturerat) hur bästaföstsökning skulle kunna användas i ett trafikinformationssystem för bilister. (betyg A)
Hemtalet lämnas in på kurswebbsidan (under Inlämningsuppgifter).