Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Glasfasern aus der Optoelektronik in der Fakultät für Elektrotechnik, Informatik und Mathematik, Foto: Universität Paderborn

Bildinformationen anzeigen

Glasfasern aus der Optoelektronik in der Fakultät für Elektrotechnik, Informatik und Mathematik, Foto: Universität Paderborn

EIM Termin

Freitag, 11.01.2019 | 13.00 Uhr | Fürstenallee F1.110

Talk 1: An amazing but less known world of data structures

Abstract:

From most of the courses or textbooks on data structures and algorithms, unfortunately, one gets the following picture/impression about the data structures.

  1. The role of data structures is confined only to searching and sorting.
  2. Either the data structures are trivial (stacks, queues, Binary heaps, Red-Black trees), or they are too complex and impractical (Fibonacci Heaps).
  3. Most of the data structures lack the depth, richness, and elegance compared to the algorithms (e.g. Max-Flow).

The above picture/impression is totally wrong. Indeed, there are many simple and elegant data structures for various fundamental graph problems. These data structures achieve amazing, rather unbelievable, time complexities. In this talk, we shall discuss a few of such data structures.

Important note for this talk:

  1. The talk will be self contained. It will be followed by everyone who has done a course on data structures. However, the contents of the talk will be quite advanced.
  2. If you feel that majority of the data structures lack any elegance or depth, you must attend the talk.
  3. If you already know about dynamic trees (s-t tree and Euler Tour tree), you may skip this talk.
  4. The talk is the first talk in the series of talk on dynamic algorithms. This talk will cover the fundamental data structures that helped in designing efficient dynamic algorithms.

Die Universität der Informationsgesellschaft