Period Ht1, vecka 35-41

Introduktion och översikt av kursen

Orientering de grundläggande delarna av C++. (OH 1-20)

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.

Orientering de grundläggande delarna av C++, forts. (OH 21-34)

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. Underlag för Laboration 1.5 kommer att behandlas på Fö 3-4.

(OH 35-44, Strömbiblioteket, överlämnas till eget studium)

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.

Klasser (OH 45-61)

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).

Klasser, forts. (OH 62-67)

Typomvandlande operatorfunktioner.

Operatoröverlagring (OH 68-77)

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 (==).

Undantagshantering, introduktion (OH 78-81)
try-block, throw-uttryck och catch-hanterare. Hantering av undantag. Mall för att definiera egna undantag.

Härledning, arv, polymorfi (OH 82-103)

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.

Dynamisk typkontroll och typomvandling (OH 104-109)

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

Standardundantag (OH 110-119)
Lite med om felhantering och undantagshantering. Repetition: try-block, catch-hanterare, throw-uttryck. Design av standardundantagen, att härleda egna undantagsklaser från standardundantagen.

Orientering om C++11 (OH 120-127)
Utvalda nyheter, relaterade till kursens innehåll.

Period Ht2, vecka 44-50 (sista föreläsningen v 47)

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

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").

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.
[Weiss: 16.1-16.2, 17.1-17.4, 18]

Enkelt binärt sökträd.
Princip. Sökning, insättning och borttagning.
[Weiss: 19.1-19.3]

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

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).
[Weiss: 22.1-22.2]

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.
[Weiss: 19.8]

B-träd, forts.

Insättning (överskott, noddelning, nodbalansering, lån eller adoption? Borttagning (underskott, lån, adoption, nodsammanslagning.
[Weiss: 19.8]

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.
[Weiss: 20], [komplettering om 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".
[Weiss: 21.1-21.4]

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.
[Weiss: 9, 21.6]

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).
[Weiss: 21.7]