Övning 1

Pythonuppgifter

Labbarna i kursen kräver goda Python-kunskaper, speciellt när det gäller klasser och filhantering.

Pythons inbyggda datastrukturer - 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.

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

import timeit  #tidtagning

def fil_till_lista():
    """Läser in alla glassar från filen,
    lägger dom i en lista,
    returnerar listan"""
    with open("glass.txt", encoding="utf8") as glassfil:
        rubrikrad = glassfil.readline()
        glasslista = []
        for rad in glassfil:
            glass = rad.strip()
            glasslista.append(glass)
    return glasslista


def main():
    glasslista = fil_till_lista()
    glasslista.sort()
    
    for glass in glasslista:
        print(glass)

    # Hur lång tid tar det att läsa in från filen?
    t = timeit.Timer(fil_till_lista)
    print("En miljon anrop av fil_till_lista tog", t.timeit(), "sekunder.")

    # Använd lambda för att ta tid på metodanrop eller funktion med parameter
    t = timeit.Timer(lambda: glasslista.sort())
    print("En miljon anrop av sort tog", t.timeit(), "sekunder.")

main()

Abstrakt datatyp för temperatur 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. Definiera klassen temp med metoderna setK, setC, setF och getK, getC, getF.

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

class Temp:
    """ Klass för att hantera temperaturer i Kelvin, Fahrenheit och Celsius """

    nollC = 273.15                        
    nollF = 255.3722                   #F-nollan i Kelvin

    def __init__(self):
        self.K = 0                     #Temperatur i Kelvin

    def setK(self,K): 
        self.K = K

    def setC(self,C):
        self.K = Temp.nollC+C

    def setF(self,F): 
        self.K = Temp.nollF+5*F/9

    def getK(self):   
        return self.K

    def getC(self):   
        return self.K-Temp.nollC

    def getF(self):   
        return (self.K-Temp.nollF)*9/5

def main():
    t = Temp()
    t.setC(20)
    print(round(t.getF()), "är temperaturen i Fahrenheit")

main()

Svara på följande frågor:

Vad är relationen mellan en klass och ett objekt?
Vad är K för sorts variabel?
Vad är nollF för sorts variabel?
Vad ärself?
Vad gör__init__?
Hur skriver man för att skapa ett Temp-objekt?

Stack implementerad med länkad lista

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.

Filen stack.py

class Stack:
   """ En implementation av en stack som en länkad lista av noder (instanser av Node-klassen)"""

   def __init__(self):
      self.top = None

   def push(self,x):
      ny = Node(x)
      ny.next = self.top
      self.top = ny

   def pop(self):
      x = self.top.value
      self.top = self.top.next
      return x

   def isempty(self):
      if self.top == None: 
         return True
      else: 
         return False


class Node:
   """ Representerar en nod med värde och next-pekare """
   def __init__(self, x):
      self.value = x
      self.next = None

Tentauppgifter

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.
Rymdtentan 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!