Kursen och formalia

Kursansvariga studenter sökes!
Gärna en per program/inriktning. Anmäl dig bums till Linda.

KursPM
Övrig kursinformation på Canvas
Repetition av klasser i Python
Algoritmer - några exempel
Datastrukturer
Läranvisningar

Kursinnehåll

Datalogikurser världen över är mycket lika varandra. Innehållet är i huvudsak det här.

Abstraktion
Datastrukturer
Algoritmer

Vad händer i kursen?

All undervisning i denna kursomgång är på distans, i Zoom.

Föreläsningar genomgång av algoritmer och datastrukturer. Spelas in!
Övningar kodexempel inför labben och träning inför KS:ar.
Labbar ni implementerar ni datastrukturer och algoritmer.
- På hjälptider prioriteras hjälp (köa här: http://queue.csc.kth.se/Queue/Tilda)
- Boka tid (https://kth.instructure.com/courses/21062/pages/bokning)
Kontrollskrivningar ges på schemalagd tid som obevakade Canvas-quiz

Vad är obligatoriskt för att klara kursen?

Labb 1-10 ska redovisas muntligt vid något av veckans labbtillfällen, och lämnas in i Canvas.
E-delen på tentan, dvs KS1 - KS5
Undervisningen är inte obligatorisk.

För högre betyg?

Den som gör alla E-labbar i tid får göra C-labben och A-labben (under period 2).
Munta med C-uppgift och A-uppgift (under period 2).

Pythonrepetition: en klass + läsa från fil

bok.py

class Bok:

   def __init__(self, datarad):
      rensad = datarad.strip()
      uppdelad = rensad.split(";")
      self.titel = uppdelad[0]
      self.sidantal = int(uppdelad[1])
      self.typ = uppdelad[2]
      self.pris = int(uppdelad[3])

   def __str__(self):
      return self.titel

def main():
   with open("bokdata.csv", encoding = "utf8") as fil:
      rubrikrad = fil.readline()
      print(rubrikrad)
      datarad = fil.readline()
      bok = Bok(datarad)
      print(bok)

main()

bokdata.csv

BOKTITEL;SIDANTAL;TYP;PRIS

The Raven Tower;416;inbunden;150

Problem Solving with Algorithms and Data Structures in Python;136;ebok;0

Time and Tide;442;pocket;120

Understanding Philosophy of Science;290;pocket;199

Algoritmer

En beskrivning, i ett ändligt antal steg, av hur man löser ett givet problem.

Exempel:
Skriv en algoritm för att läsa in gps-data för platser från en fil (t ex island.txt eller kina.txt) och lagra dom i en lista.
Platserna är i filen ordnade med sydligast latitud först, men i listan vill vi att dom ska ligga i ordning från nordligaste till sydligaste, alltså i omvänd ordning.

Algoritm 1

öppna filen
läs in rubrikraden
läs in första raden
lägg raden sist i listan
upprepa punkt 3 och 4 tills alla rader i filen lästs in
vänd listan

Implementation med for-slinga och append

print("Algoritm 1 med append och reverse")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
   for rad in landfil:
      rader.append(rad.strip())
rader.reverse()

#Kontrollera resultatet
print("Antal rader", len(rader))
for i in range(5):
   print(rader[i])

Samma algoritm - implementation med while-slinga

print("Algoritm 1 med append och reverse + while")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
   rad = landfil.readline()
   while rad:
      rader.append(rad.strip())
      rad = landfil.readline()
rader.reverse()

#Kontrollera resultatet
print("Antal rader", len(rader))
for i in range(5):
   print(rader[i])

Algoritm 2

Här är en annan algoritm för samma problem:

öppna filen
läs in rubrikraden
läs in första raden
lägg raden först i listan
upprepa punkt 3 och 4 tills alla rader i filen lästs in

Implementation med insert

print("Algoritm 2 med insert")
filnamn = "kina.txt"
rader = []
with open(filnamn, encoding = "utf-8") as landfil:
   for rad in landfil:
      rader.insert(0,rad.strip())
print("Antal rader", len(rader))

for i in range(5):
   print(rader[i])

Tidskomplexitet

Olika algoritmer kan ta olika lång tid för att lösa ett och samma problem. Ofta går det att ange tiden som funktion av indatas storlek, T(n) där n är antalet indata.

Jämför algoritmerna ovan.

Vad är n?
Vad är T(n) för algoritm 1 respektive algoritm 2?

Datastrukturer

Pythons lista är exempel på en datastruktur. I kursens tar vi upp följande datastrukturer:

Länkade listor
Vektor/array
Stack
Kö
Deque
Allmänna träd
Binära sökträd
Hashtabeller
Bloomfilter
Heap
Prioritetskö

På labbarna får du skriva egna implementationer av flera av dessa datastrukturer.

Läranvisningar

För varje datastruktur och algoritm gäller det att kunna:

Förstå
- Abstrakt: hur använder man den?
- Implementation: hur funkar den i detalj?
Analysera
- Hur snabb/effektiv är den? Komplexitet mm.
- Vad har den för fördelar/nackdelar? Begränsningar?
- När är den lämplig/olämplig?
  (jämfört med andra algoritmer/datastrukturer)