Föreläsning 14 - Tentaåterlämning och -genomgång

Kursenkät

Fyll i kursenkäten! Du hittar den på kurshemsidan, här: http://www.csc.kth.se/utbildning/kth/kurser/2D1320/tilda06/kursenkat/

Denna kursenkät och mittkursuntvärderingen kommer att utgöra underlag för kursanalysen som påverkar nästa kursomgångs upplägg. Ta chansen att påverka!

Resultatet av mittkursutvärderingen som gjordes denna kursomgång hittar du på kurshemsidan, här: http://www.csc.kth.se/utbildning/kth/kurser/2D1320/tilda06/kursanalys/tilda06mittkursutv.pdf

Laborationerna

Kom ihåg att sista redovisningsdag för laborationerna är den 16/11! Man måste bli godkänd på laborationsdelen (dvs redovisa alla sju labbarna) för att bli godkänd på kursen. Använd de kommande laborationspassen.

Tentaresultatet

Tentan har 100 poäng. Så här gick det:

Gränser	Betyg	Antal
<45	U	26
45-49	K	11
50-64	3	37
65-84	4	48
>84	5	18

Totalt var ni 140 som skrev tentan, varav fyra kom från andra kursomgångar. Antalet godkända var alltså 103, 114 om vi räknar in de som ska komplettera.

Fick du 45-49 poäng? Då har du också fått en individuell kompletteringsuppgift utdelad tillsammans med tentan. Den ska lämnas in senast 7 november.

Bland de 26 som blev underkända hade 13 stycken ännu inte redovisat fler än 3 av de bonuspoängsgivande laborationerna, ytterligare 8 hade "bara" redovisat 4 stycken. Kopplingen är tydlig!

I kurspm står följande: "Klagomål på rättning av tentan lämnas till kursledaren inom tre veckor från det att tentaresultatet anslagits. Observera att du inte bör ta med dig tentan från expeditionen eller tentaåterlämningen om du vill klaga på rättningen. Kolla tentan på expeditionen, skriv ned dina kommentarer och kontakta sedan kursledaren."

Tentagenomgång

Här följer några kommentarer om tentan och lösningarna som inkommit.

Uppgift 1

Denna uppgift borde i princip vara "gratispoäng". Några kommentarer:

• a) -
• b) Man kan sortera på aritst och år på en gång om man förutsätter en jämförelsefunktion för detta! Quicksort!
• c) Vi har en sorterad bokylla. Det är inte en hashtabell! Det är inte ett träd!
• d) -
• e) Enklaste tänkbara rekursiva tanke. Ändå problematiskt...
• f) Fördelarna med ADT:er har nämnts flera gånger på föreläsningarna...

Uppgift 2

Uppgiften testar att man kan använda huffmanalgoritmen för att bygga ett träd. Använder man inte algoritmen blir det oftast inte rätt. Det finns massor av korrekta huffmanträd för denna uppgift!

Vissa försöker sätta in bokstäverna i ett symmetriskt träd. Huffmanalgoritmen producerar inte alltid symmetriska träd!

Uppgift 3

Uppgiften testar att man kan skriva ett enkelt reguljärt utryck. Det avslutande valfria 's' tecknet har vållat mest besvär. Även om man inte kommer på den praktiska operatorn '?' går det dock att lösa problemet. Avslutar man med ((t)|(ts)) så får man rätt resultat.

Uppgift 4

Har man lärt sig att en prioritetskö implementeras med hjälp av datastrukturen trappa (heap) och hur denna fungerar ger denna uppgift "gratispoäng".

• a) En heap lagras som en vektor och kan visualiseras som ett binärt träd. Man förväntades rita både en vektor och ett binärt träd efter varje insättning. Det finns både min- och max-heap. Eftersom inget specificeras förväntas båda. Det räcker med max-heap eftersom den är svårast i det här fallet. Max-heap är det naturliga med tanke på uppgiftsformuleringen.
• b) -
• c) Funktionen ska använda sig av de båda inparametrarna och returnera ett resultat. Hur ska annars någon kunna ha någon nytta av den?

  En motivering är inte en beskrivning av vad funktionen gör utan en förklaring av varför den är skriven som den är.

Uppgift 5a

Nästan alla problem på denna uppgift kan kopplas till dåligt läsande av vad man egentligen ska göra. Man ska skapa en datasturktur. Eftersom det ska gå snabbt att hämta ur den är det uppenbara valet en hashtabell.

Ska man redogöra för hur man går till väga bör man alltid skriva en tydlig algoritm, gärna punktvis.

Uppgift 5b

Endast en bråkdel av de inlämnande lösningarna fungerar. Det genomgående kritiska problemet är att vad ett dumbarn är inte specificeras. Har vi stött på Beatles i en kedja utgör dessa endast dumbarn i denna kedja. En annan kedja kan ha Beatles i ett senare steg.

Ett ganska vanlig förslag är: "då Muddy Waters dyker upp igen har man nått slutet av kedjan". Varför det? Det stämmer inte alls.

På en sådan här uppgift förväntar man sig en strukturerad algoritm, gärna i punktform med förtydliganden i löptext efter. Väldigt många hade nog hittat sina egna fel om de renskrivit sin lösning på det viset.

Uppgift 6

Här vållade uppgiftsformuleringen vissa problem. Läs den flera gånger! Om man anlyserar den är det inte konstigt. De två första meningarna i lydelsen är hela uppgiften. De följande är förklaringar och specialfall...

Uppgift 7

Den delfråga som kräver kommentar är uppgift a. Många har fel på denna. En del har noterat att damerna-först-sortering ingår i Quicksort och sedan angivit komplexiteten för damerna-först-sortering till O(N log N). Ett mycket orimligt svar eftersom Quicksort själv är O(N log N). Komplexiteter multipliceras med varandra. En for-slinga har komplexitet O(N), och en for-slinga inne i en for-slinga har komplexitet O(N^2)