Övning 1: Pythonuppgifter, abstrakta datatyper

Detta händer på dagens övning:

  • Vi tar en titt på Labb 2
  • Pythons dokumentation: string och list och array
  • Länkad lista - övning inför Labb 2
  • Knepiga listor - övning inför Labb 2
  • Rita en kö (implementerad med länkad lista) - övning inför Labb 2
  • Betygskriterier, samt exempel på tentafrågor på olika betygsnivå
  • Abstrakt datatyp för temperatur 

 

Ta en titt på Labb 2

Följande deluppgifter:

  1. ArrayQ - en kö med Pythons array

  2. Testa ArrayQ

  3. Skriv Trollkarlsprogrammet

  4. Skapa en ArrayQ-modul

  5. LinkedQ - en kö av noder (länkad lista)

  6. Testa LinkedQ 

  7. Trollkarlsprogrammet med LinkedQ

  8. Skicka in till Kattis

Du ska implementera en kö på två olika sätt: med array (ArrayQ) och med en länkad lista (LinkedQ).

Trollkarlsprogrammet ska se likadant ut i bägge fallen.

 

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"? [bilder om copy Links to an external site.]
  • Finns det någon metod här som inte har returvärde? Jämför med strängmetoderna och förklara skillnaden.

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

  • Vad är skillnaden mellan append, extend och insert?
  • Vad är skillnaden mellan remove och pop?
  • Finns det några skillnader mellan array och list?

 

 

Länkad lista

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

Med en nodklass kan vi skapa datastrukturen länkad lista. 
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next

För varje uppgift nedan, rita en bild som visar hur det ser ut när man...

  1. ...lägger in en ny nod i en tom lista. 
  2. ...lägger in en ny nod sist i en lista med en nod. 
  3. ...lägger in en ny nod först i en lista med en nod. 
  4. ...tar bort den första noden från en lista med två noder.
  5. ...tar bort den sista noden från en lista med två noder.

Skriv också upp vilka satser (pekartilldelningar) som ska utföras i vart och ett av fallen.

Jämför med din bänkkompis, och kontrollera att satserna stämmer med era bilder.

Linus lösning, s 1

 

Knepiga listor, uppgift 5 tenta 2005-12-05 från kursen DD1321 tilpro

Beta försöker lära sig hantera länkade listor under lovet. Det är inte lätt. Givet följande listor

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

a) Hur ser listan/listorna ut efter följande rader kod?

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

b) Hur skulle det ha sett ut om man istället skrivit följande rader kod?

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


Linus lösning, s 2

 

En kö implementerad med länkad lista

Rita en kö.jpg

Metoden enqueue ska lägga in ett nytt element i listan.

  • Var ska det nya elementet in?
  • Vilka pekare ska ändras?
  • Spelar det roll i vilken ordning man gör saker?

Metoden dequeue ska plocka ut ett element från listan.

  • Vilket element ska tas ut?
  • Vilka pekare ska ändras?
  • Spelar det roll i vilken ordning man gör saker?

 

 

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.

Tre exempel från tentan i juni 2018, att jämföra med betygskriterierna ovan. 

 

  1. KTHB undrar hur bloomfilter kan användas. (betyg E)

    Biblioteket har en mycket stor fil med bokdata som t.ex. ISBN-nummer, titel,
    författare etc. Man vill kunna söka snabbt efter data och har två frågor till dig. Motivera dina svar.
    a) Kan man använda bloomfilter för att snabbt ta reda på om biblioteket har
    en specifik titel?
    b) Kan man använda bloomfilter för att givet ett ISBN-nummer snabbt ta fram
    författaren?

  2. Arkitektur bygger slott. (betyg C)

    Ett magiskt sagoslott har många rum som är förbundna med varandra. En del rum angränsar till väldigt många rum och andra rum gränsar bara till ett enda. Ibland så ändras planlösningen magiskt. Det som händer då är att antingen så försvinner en förbindelse mellan två rum eller så tillkommer en ny förbindelse mellan två rum. En tildastudent får uppdraget att lagra hur rummen är förbundna med varandra i en graf. Man ska kunna

    • se om två rum är förbundna med varandra,

    • se vilka rum som är förbundna med ett givet rum,

    • uppdatera grafen när magi inträffar (rumsförbindelse försvinner/tillkommer).

    a) Rita och beskriv kortfattat hur grafen kan representeras som en grannlista.

    b) Rita och beskriv kortfattat hur grafen kan representeras som en grannmatris.

    c) Jämför grannlista och grannmatris med avseende på prestanda och minnesåtgång för de tre punkterna ovan.

  3. Bioteknik återkommer med nya frågor. (betyg A)

    En DNA-sekvens består av en följd kvävebaser, t ex
    GTCCAACGGATCGAGATCTGAGCGTTCAAAGATCCGTAGATCTCAACCTC
    Vissa sekvenser av tre eller fyra tecken är vanligare än andra, t ex ”GATC” i
    sekvensen ovan:
    GTCCAACGGATC GAGATC TGAGCGTTCAAAGATC CGTAGATC TCAACCTC
    a) Beskriv en effektiv algoritm som skapar en tabell över alla sekvenser på tre respektive fyra tecken. Tabellen ska sorteras efter förekomst, med den vanligaste sekvensen först. Algoritmen måste beskrivas på ett strukturerat och tydligt sätt.
    b) Demonstrera hur din algoritm fungerar med ett litet exempel.
    c) Uppskatta tidskomplexiteten för din algoritm.
    d) Amöbor har särskilt långa DNA-sekvenser, med upp till 6.7 · 1011 tecken. Vi komprimerade DNA med Huffmankomprimering i uppgift E3 [tidigare i samma tenta], med mindre lyckat resultat. Föreslå en förbättring av komprimeringsalgoritmen, med inspiration från algoritmen du skrev i deluppgift a) ovan. Motivera ditt svar.

Gamla tentor finns i tentabanken.

Uppgifter för extra träning på Python här:

Läsa in från fil till lista

Mål: Repetera inläsning från fil, och användning av lista

Skriv ett program som läser in glassar från en fil och skriver ut dom i bokstavsordning. 

Börja med att planera programmet:

  • Hur ser filen med glassarna ut?
  • Hur öppnar man en fil för läsning?
  • Hur läser man en rad från filen? Och hur lägger man in den i listan?
  • Hur sorterar man en lista? Blir det bokstavsordning automatiskt?

[ Download lasglass.py

]

Abstrakt datatyp för temperatur 

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.

a) Konstruera en klass Temp som representerar en temperatur. Diskutera först vilka attribut och metoder som behövs, skriv sedan koden.

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

]

c) Bygg ut klassen med en metod __str__ som returnerar en strängrepresentation av ett Temperaturobjekt. Hur ska vi testa metoden?

d) Lägg till en metod __lt__ för att kunna jämföra två Temperaturobjekt. Hur ska vi testa metoden?

[ Download tempV2.py

]

 

Föreläsningar i Python för nybörjare

https://kth.instructure.com/courses/12194/pages/forelasningar

Allmänhandledning

https://www.kth.se/social/group/allmanhandledning/