Övning 1

Pythons dokumentation: string och list
Abstrakt datatyp för temperatur
Stack implementerad med länkad lista
Tentafrågor på olika betygsnivå

Pythons dokumentation: string och list (denna uppgift lämpar sig att göra på egen hand)

Mål: Pythons inbyggda datastrukturer - öva på att läsa dokumentationen.

Slå upp string i Pythons dokumentation, och svara på följande frågor:

Vad har capitalize för parametrar och returvärden?
Vad har count för parametrar och returvärden?
Vad gör metoden split? Vilken datatyp returneras? Visa med ett eget exempel.
Vad gör metoden strip?
Finns det någon metod här som inte har returvärde?

Slå upp list i Pythons dokumentation, och svara på följande frågor:

Vad har append för parametrar och returvärden?
Vad är skillnaden mellan append, extend och insert?
Vad är skillnaden mellan remove och pop?
Läs om copy. Vad menas med "shallow copy"?
Finns det någon metod här som inte har returvärde? Jämför med strängmetoderna och förklara skillnaden.

Abstrakt datatyp för temperatur (diskutera först vilka attribut och metoder som behövs, skriv sedan koden)

Mål: Öva på abstraktion, repetera klasser.

I kursen ska ni själva implementera datastrukturer, oftast genom att skriva egna klasser i Python. Här är ett exempel.

Temperatur kan anges i olika skalor. En abstrakt datatyp minskar risken för missförstånd. Konstruera en klass Temp som representerar en temperatur.

Testa klassen i ett program som läser in utomhustemperaturen (Celsius) och skriver ut temperaturen så att en amerikan förstår (Fahrenheit).

Svara sedan på följande frågor:

Vad är relationen mellan en klass och ett objekt?
Om du skulle skriva dokumentation för klassen - vad är viktigt att ta med?

temp.py

Stack implementerad med länkad lista (rita först, jämför med din kompis bild)

Mål: Förstå hur en länkad lista fungerar i detalj.

Rita bilder som visar hur det ser ut när man lägger in ett nytt element i stacken.
Rita bilder som visar hur det ser ut när man tar bort ett element från stacken.

stack.py

Tentauppgifter

Mål: Veta hur tentans E-, C-, och A-uppgifter skiljer sig åt. Kunna lösa uppgifter på olika betygsnivå.

Betygskriterier - sammanfattning

För betyg E ska man kunna avgöra vilken algoritm som löser ett givet problem, kunna beskriva algoritmen och demonstrera den steg för steg med givna data, samt implementera den. Motsvarande gäller för datastrukturer.
För betyg C ska kraven för betyg E vara uppfyllda, och dessutom ska man kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem. Här ställs också krav på tidsplanering. Se tidsgränser för aktuell kursomgång under Laborationer.
För betyg A ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.

Cykeltentan 2014-10-24, uppgift 4 (betyg E)
Cyklisterna köar vid övergångsstället nere vid Valhallavägen. Först i kön står Linda, sen Alexander, sen Robert och sist Marko.

Kön är implementerad med en länkad lista. Rita bilder som visar hur det ser ut i detalj (varje steg) när man sätter in respektive plockar ut ett element ur kön.
Alien-tentan 2015-03-20, uppgift 6 (betyg E/C)
En norrskensentusiast vill lagra bilder på norrsken. Vad finns det för fördelar respektive nackdelar med en vektor respektive en länkad lista när det gäller
- åtkomst
- insättning
- borttagning
Svara med en tabell med tre rader.

Japantentan 2007-10-24, uppgift 5 (betyg A)

Våra datorer läser texter radvis, från vänster
till höger. 
Men japansk text står i kolumner uppifrån och ner, 
som läses från höger till vänster.
Ge en algoritm för att 
med hjälp av en abstrakt kö eller stack
ordna om en japansk text om m kolumner och n rader.

Exempel:

  7 4 1
  8 5 2  läses in som 7 4 1 8 5 2 9 6 3
  9 6 3
men vi vill ha ordningen 1 2 3 4 5 6 7 8 9
Du kan förutsätta att alla kolumner och rader är helt fyllda, men
antalet kolumner, m, behöver inte vara detsamma som antal rader, n.
Till exempel kan det finnas fem rader men bara tre kolumner.

Visa sedan hur din algoritm fungerar för exemplet ovan.

Utred till sist vilken komplexitet din algoritm har!