Mikaels övningar Tillämpad datalogi för 2013

Övning 1:

Vi gick igenom betydelsen av abstrakta datatyper/datastrukturer. Detta exemplifierades genom att dels titta den abstrakta dataytyperna stack och listan. Vidare gick vi igenom användningen av abstrakta datayper genom att jämföra inläsning från fil och inläsning från URL. Vi skissade på en lösning till Lab 1 samt kolla på några egendefinerade abstrakta datatyper fraction och temperatur. Slutligen gick vi igenom functionen iso2utf vilken byter kodningen sträng från iso till utf

Övning 2:

Övningsanteckningar och MyUtil.py .

Vi gick igenom listor, pekare, binära träd och rekursion . Vi han inte till komplexitet men titta gärna på sista exemplet i övningsanteckningarna. Detta exemplifierades genom att vi skrev remove_second och gcd (greatest common divisor) och . Vi gick även igenom hur binära träd byggs, utag från binärträd med in, pre och postordning samt vi räknade på programtidsåtgång givet en viss programkomplexitet. Övningsanteckningarna innehåller även ett ytterligare ett par program, re- fib (fibonnaccis tal), summa (trädsumma) och height (trädhöjd) som det kan vara bra att kolla på.

OBS: append metoden i LinkedList fungerar nu som den ska, dvs med append lägger vi till på slutet av den länkade listan. Har även förklarat exemplet där vi tar bort varannan nod ur en lista med hjälp av en stack bättre.

Övning 3:

Övningsanteckningar och ordlista

Vi gick igenom problemträd, sökning i problem träd med bredden först, och djupet först. Vi exemplifierade det genom att lösa två uppgifter strykord, med djupet först, och sjuor i rad, med bredden först.

Rättelse: Nu används endast engelska i funktionerna makesons och writechain.

Övning 4:

Övningsanteckningar

Vi igenom problem som handlade om lagring och sortering. Vi löste uppgifter som handlade om hashning, binärträd, bloomfilter, trappor (heap), komplexitet och sortering. Vi gick igenom talen 1-5. Jag rekommenderar att kolla på de återstående talen 6-10. Återkomm gärna till mig med frågor.

Övning 5:

Övningsanteckningar

Vi igenom automater, reguljära uttryck och syntax. Vi exemplifierade detta genom att lösa 5 uppgifter. Vi tittade på hur next vecktorn i en KPM automat byggs up, hur reguljära uttryck kan skapas och tolkas samt vi felsökte 4 olika syntax grammatiker och skapade får egna grammatik för att kolla om en websida är rätt skriven.

Övning 7:

Övningsanteckningar

Idag räknade vi igenom en tentamen från 12 januari 2010. OBS i många uppgifter kan man svara på olika sätt. Det viktiga är att visa att man förstått.