Övning 1: Pythonuppgifter, abstrakta datatyper

Pythons dokumentation: string och list

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

Slå upp string Links to an external site. 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 Links to an external site. 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.

class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next

p  ->  A -> B -> C -> D  
q  ->  E -> F -> G

z = p.next
p.next = q.next
z.next.next = p
q = p = z

p.next.next.next = q.next.next
q.next = p
p = q

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

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.

1. 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.

   ---

2. 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.

   ---

3. 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
   9 6 3
   läses in som 7 4 1 8 5 2 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!