Period Ht1, vecka 36-42

Introduktion till kursen  [2x2]

Introduktion till C++  [2x2]

Grundläggande programstruktur. Grundläggande datatyper. Typomvandling. Variabler och konstanter. Deklarationer och definitioner. Uttryck och operatorer. Operatorers prioritet och associativitet, beräkningsordning för operander, sidoeffekter. Satser.

Introduktion till C++, forts.  [2x2]

Funktioner. Sammansatta datatyper: uppräkningstyper, fält, poster, pekare. Dynamiska datastrukturer, dynamisk minneshantering.

De delar av C++ som genomgåtts översiktligt på Fö 1-2 motsvarar Laboration 1.1-1.4 samt delvis 1.5. Underlag för att kunna slutföra Laboration 1.5 kommer att behandlas på Fö 3.

Strömbiblioteket överlämnas till eget studium

Klasser  [2x2]  [kodexempel String]
Kort orientering om objektorienterad programmering och objektorienterade konstruktioner: klass/objekt, arv/härledning, polymorfi/dynamisk bindning. Föreläsning 7 tar upp mer om objektorienterad programutvecklinling.

Grundläggande om syntax och semantik. Medlemmar (data- och funktionsmedlemmar). Åtkomst till klassmedlemmar (public, private). Olika alternativ för att deklarera och definiera medlemsfunktioner (definition i klassen, "in-class", medför underförstått "inline", separat definition, separat definition med uttrycklig "inline"-deklaration. const-deklaration av medlemsfunktioner. Konstruktorer. Destruktor. Defaultkonstruktor. Initierare. this-pekaren, Kopieringskonstruktor, typomvandlande konstruktor, explicit-deklaration av konstruktor. Kompilatorgenererade versioner av defaultkonstruktor, kopieringskonstruktor och kopieringstilldelning (operator=). Vikten av att korrekt kopiering och tilldelning är definierat för icke-triviala klasser (t.ex. klasser med datamedlemmar som är pekare till dynamiskt minne). Typomvandlande operatorfunktioner.

Klasser, forts.  [2x2]  [kodexempel String]

Operatoröverlagring  [2x2]

Operatorer som kan överlagras för klasser (de flesta fördefinierade operatorer). Syntax och semantik (försök normalt efterlikna språkets inbyggda operatorer). Frågan om operator ska/bör/måste vara klassmedlem eller fristående funktion. Exempel på operatorer som måste vara medlem (=, []), som inte kan vara medlem (<<) och som antingen kan vara medlem eller ej (==).

Introduktion till undantagshantering  [2x2] try-block, throw-uttryck och catch-hanterare. Hantering av undantag. Mall för att definiera egna undantag.

Härledning, arv, polymorfi  [2x2]  [kodexempel Person-Employee-Manager-Consultant]

Härledning av klasser. protected som åtkomstskydd för ärvd klassmedlem. Olika former av arv (public, protected och private) och dessas innebörd.

Virtuella medlemsfunktioner, rent virtuella ("pure virtual") medlemsfunktioner, dynamisk bindning (i detta sammanhang), Överskuggning ("overriding", inte att förväxla med överlagring, "overloading").

Orientering om olika typer av arv: enkelt arv, multipelt arv och repeterad arv samt virtuellt arv. Gränssnittsklasser.

Härledning, arv, polymorfi, forts.  [2x2]  [kodexempel Person-Employee-Manager-Consultant]

Dynamisk typkontroll och typomvandling

RTTI (Run-Time Type Identification). Klassen type_info, typeid-uttryck och dynamic_cast.

Undantagshantering, forts.  [2x2]
Lite med om felhantering och undantagshantering. Repetition: try-block, catch-hanterare, throw-uttryck. Design av standardundantagen, att härleda egna undantagsklaser från standardundantagen.

Period Ht2, vecka 45-51

Objektorienterad programutvecklingsmetodik.
Metodik, begrepp, notation (UML), CRC-kort, mm.

•  Objektorienterad programutveckling i ett nötskal (utdelas ej)
•  Visade dia OOP (utdelas ej):  fullformat  |  2x2

Introduktion till datastrukturer och algoritmer
Orientering om innehållet i datastrukturer och algoritmer (Fö 8-14). Implementering av listor och träd, begreppen "header" och "sentinel". Olika länkningsalternativ för länkade listor (enkel, dubbel, cirkulär) och länkade träd (binära träd med sentinel-nod, "threaded trees").

•  Datastrukturer och algoritmer (enkel översikt, utdelas ej)
•  DoA-OH, Fö 8-14 (utdelas):  fullformat  |  2x2

Observera, ovanstående häfte och OH definierar kursens innehåll avseende DoA.

Sökning i listor
Linjärsökning, binärsökning, interpolationssökning.

Allmänt om träd
Terminologi, begrepp. Trädtraversering, med uttrycksträd som exempel.

Enkelt binärt sökträd.
Princip. Sökning. Insättning och borttagning.

AVL-träd
Princip. Höjdbalanserat binärt sökträd. Sökning, insättning och borttagning.
Fibonacciträd.

Röd-svarta träd: orientering — enpass höjdbalanserat sökträd med "top-down"-balansering. AVL-trädet är tvåpass med "bottom-up"-balansering.

Skiplista — Tänkt att kunna konkurera med binära sökträd). Perfekt balanserad skiplista. Praktiskt balanserad skiplista.

Splayträd
Introduktion - splayning - splayrotationer - amorterad analys - 90/10-principen.
Två varianter: "bottom-up"-splayning (tvåpass) och "top-down"-splayning (enpass).

Orientering om "flytta-till-början-lista" (listornas motsvarighet till splayträd).

B-träd

Introduktion: Definition. Begrepp: fyllnadsgrad (M och L), överskott, underskott, noddelning, nodsammanslagning, nodbalansering, lån/adoption.

B-träd, forts.

Insättning (överskott, noddelning, nodbalansering, lån eller adoption? Borttagning (underskott, lån, adoption, nodsammanslagning.

Hashtabeller
Allmänt om begrepp, problem, lösningar, kollisionshanteringsmetoder: linjär sondering, kvadratisk sondering, dubbelhashning. Separat länkning. Omhashning. Borttagning ur hashtabell. Linjär hashning.

Hashtabeller, forts.
Linjär hashning.

Prioritetsköer
Prioritetsköer allmänt. Definition av heap (heapordningsegenskapen).

Binär heap
Definition. Avbildning på fält. Två alternativ att sätta in i en binär heap, insert och toss+fixheap. Borttagning. "percolate-up" och "percolate-down".

Sortering med binär heap, Heapsort.

Intern sortering.

Introduktion. Olika klassificeringar och begrepp: intern-extern, jämförande-distributiv, enkel-avancerad, stabil, naturlig.

Tekniker för jämförande sorteringsmetoder: urval, utbyte, insättning, samsortering.
Enkla metoder: Bubblesort, Shakersort, Selectionsort, Insertionsort (linjär insättning eller binär insättning).
Avancerade metoder: Heapsort, Shellsort, Mergesort, Quicksort.

Intern sortering, forts

Extern sortering
Samsortering. Två grundläggande samsorteringsmetoder: balanserad 2-vägs resp. naturlig 2-vägs samsortering; "Simple Merge". Polyphase Merge (avancerad balanserad samsorteringsmetod). (Replacement Selection; generering av initiala sorterade delsekvenser).