Sebastian

⬑ Liste aller flipped lectures.  —  Algorithmen und Datenstrukturen

Lektion 4: Elementare Datenstrukturen

In dieser Lektion behandeln wir elementare Datenstrukturen, die uns als Bausteine für komplexere Algorithmen und Datenstrukturen immer wieder begegnen werden: Arrays, linked lists, resizing arrays, stacks und queues.

Lernziele

  • Stack- und Queue-Abstraktionen kennen
  • sequentielle und verkettete Repräsentationen verwenden können, um diese und sonstige Listen zu implementieren
  • Vor- und Nachteile der Repräsentationen kennen
  • unter Verwendung der elementaren Datenstrukturen (einfache) Algorithmen selbst entwerfen

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung
  • Es ist explizit erlaubt/erwünscht, Fragen aus den Aufgaben zur Vorbereitung unter den Videos zu übernehmen, wenn ihr diese der Q&A Session besprechen wollt.
  • Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
    Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
  • Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
  • Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
  • Seid konstruktiv.

Material

Die Videos entstammen dem Coursera MOOC Algorithms Part I und der Princeton Vorlesung COS 126 von Robert Sedgewick und Kevin Wayne.

Die letzteren Videos wurden von Kevin Wayne exklusiv für A&DS zur Verfügung gestellt und sind deshalb nur mit Passwort abrufbar. Da es dieses Feature bei Youtube nicht gibt, sind sie bei vimeo gehostet; dort gibt es leider die beschleunigte Wiedergabe nicht. Im HTML5-Video Player kann man sie aber über Browser-Plugins nachrüsten: Firefox, Chrome. Leider funktionieren diese widerum nur in der vollen Ansicht, nicht für die eingebetten Player auf dieser Seite.

Das Passwort für die Videos erhaltet ihr im Kurs.

1 – Introduction to Stacks and Queues

Einführung von ADTs (abstract data types), Java APIs und Performance Specifications am Beispiel von Stacks (Stapel, Kellerspeicher) und Queues (Warteschlangen)

Aufgaben zur Vorbereitung:

  1. Was ist laut Sedgewick ein (abstrakter) Datentyp? Was ist eine Datenstruktur?
  2. Was ist eine Collection?
  3. Welche Operationen charakterisieren eine Stack, welche eine Queue?
  4. Wofür stehen FIFO und LIFO?
  5. Was ist ein parametrischer Datentyp? Was ist der Vorteil (für uns als Programmierer)?
  6. Was ist eine Performance Specification? Welche Performance verlangt Sedgewick für die Operationen von Stacks und Queues? Gib insbesondere präzise an, wie viel Speicher erlaubt ist.

2 – Strawman Implementation

Zum Warmwerden eine Dummy-Implementierung eines Stacks mit einem Array fester Größe.

Aufgaben zur Vorbereitung:

  1. Welche beiden funktionellen Abweichungen von der API gelten für die vorgestellte Implementierung?
  2. Inwiefern verletzt die Implementierung die performance spec?
  3. Kannst du dir eine Situation ausmalen, in der die Dummy-Implementierung trotzdem vorteilhaft sein könnte?

3 – Linked Lists

Einführung von linked lists (verketteten Listen). Dies dürfte für euch Wiederholung aus den Programmiervorlesungen sein; das Video bringt alle auf einen Stand und gibt die Namen und Begriffe vor, die wir in A&DS verwenden.

Aufgaben zur Vorbereitung:

  1. Wie wird eine Referenz/Link im Computer realisiert?
  2. Wie lautet die abstrakte Definition einer (einfach) verketteten Liste (singly-linked list)?
  3. Wie sieht eine linked list in Java aus?
  4. Was ist eine doubly-linked list?

4 – Linked Implementations

Detaillierte Implementierung von Stacks mittels singly-linked lists; es sollte inhaltlich eine Wiederholung von Bekanntem aus den Programmiervorlesungen sein, ist aber ein wichtiger show case für die allgemeine Vorgehensweise der Vorlesung (API, Implementierung, Analyse).

Aufgaben zur Vorbereitung:

  1. Wie sind die Stack-Operationen auf Basis von linked-list nodes realisiert? Bereite dich darauf vor, die Operationen auf Level der grapischen Syntax (Kästchen und Pfeile) vorführen zu können.
  2. Wie ist die Stack-Implementierung anzupassen, um eine Queue zu erhalten?

5 – Resizing Arrays

Neben der verketteten Repräsentation gibt es einen wichtigen Trick die sequentielle Repräsentation für beliebig große Collections zu verwenden: doubling arrays. Diese Vorgehensweise ist in der Praxis oft effizienter als linked lists.

Auch resizing arrays dürften euch aus einer Programmiervorlesung bekannt vorkommen, allerdings sieht man dort selten eine detaillierte Analyse. Resizing arrays sind außerdem das Paradebeispiel für amortisierte Kosten, einem wichtigen Konzept der Algorithmik.

Dieses Video stellt die doubling-array Methode am Beispiel von Stacks vor und zeigt die Performance-Charakteristika im Vergleich zur linked-list Implementierung auf.

Aufgaben zur Vorbereitung:

  1. Zuerst wird eine simplere Methode vorgestellt, Arrays für beliebige Größen zu bekommen. Wie funktioniert sie? Warum ist sie i.d.R. nicht brauchbar?
  2. Was versteht man unter amortisierten Kosten? Beschreibe das Konzept anhand der amortisierten Kosten von push.
  3. Wann verkleinern wir das Array wieder? Warum?
  4. Erfüllen resizing-array stacks die API und performance specs?
  5. Wann ist laut Sedgewick der Einsatz von resizing arrays bzw. linked lists zu empfehlen?

6 – Queues

Dieses Video stellt analoge Implementierungen für Queues vor.

Aufgaben zur Vorbereitung:

  1. Wie unterscheidet sich die linked-list Queue vom entsprechenden Stack?
  2. Wie unterscheidet sich die resizing-array Queue vom entsprechenden Stack?

7 – Generics

Dieses Video diskutiert nochmal detaillierter die Verwendung von Javas generics um Datentypen mit einem Typparameter zu realisieren.

Aufgaben zur Vorbereitung:

  1. Welche Optionen gab es in der ursprünglichen Version von Java (vor 1.5)?
  2. Welchen Vorteil bietet die Verwendung von generics, die es seit Java 1.5 gibt?
  3. Welche Fallstricke in der Verwendung von Javas generics erwähnt Sedgewick?

8 – Iterators

Vorstellung des Iterator-Konzepts und des abstrakten Datentyps Bag.

Aufgaben zur Vorbereitung:

  1. Welche Operationen bietet ein Iterator?
  2. Wie implementiert man einen Iterator für linked lists?
  3. Wie implementiert man einen Iterator für arrays?
  4. Überlege dir für beide Fälle was passiert, wenn dem zugrundeliegenden Stack Elemente hinzugefügt werden, während wir mit einem Iterator den Stack durchlaufen. Was passiert wenn Elemente entfernt werden?

9 – Applications

Einige Anwendungen von Stacks und Queues.

Aufgaben zur Vorbereitung:

  1. Welche Operationen unterstützt das List interface in Java?
  2. Beschreibe grob welche Laufzeitkomplexität diese Methoden in ArrayList und LinkedList haben könnten.
  3. Welche Anwendungen für Stacks werden vorgestellt?
  4. Welches Problem löst Dijkstras Zwei-Stack-Algorithmus? Welche Annahme an den Eingabeausdruck macht Sedgewick dabei (Stichwort Klammern)?
  5. Wie argumeniert Sedgewick, dass Dijkstras Zwei-Stack-Algorithmus korrekt arbeitet?