What are the basics of data structures

Basics: algorithms and data structures

Imprint Data Protection
Lecturer:Prof. Dr. Helmut Seidl
Place / time:Tue, 13: 45-16: 15 in MW 0001
Module number:IN0007
Description:

  • Basics of the analysis of efficiency and complexity (terms, dimensions, Landau symbols, machine model)
  • Data structures for sequences (dynamic arrays, lists, stacks, queues, each with the complexity of the operations)
  • Hashing (concatenation, universal hashing, probing method; optional: perfect hashing, hash-based algorithms, e.g. volume averaging)
  • Sorting (short repetition of simple procedures: InsertionSort, SelectionSort, BubbleSort; analysis of MergeSort, HeapSort and QuickSort; optional sort-based algorithms, e.g. quantity averaging; lower limit for comparison-based sorting, rank selection, radix sort, external sorting)
  • Priority queues (binary heaps, binomial heaps)
  • Search trees (binary search trees, AVL trees, (a, b) trees)
  • Graph algorithms (graph presentation, traversal via DFS / BFS, double-connected components, strongly connected components, topological sorting, shortest paths, minimal spanning trees, optional: TSP)
  • optional: data compression (Huffman, Lempel-Ziv)
  • optional: simple algorithms of pattern matching

 

Download the lecture slides

The address of the exercise website is (registration is via the exercise groups in TUMonline):

https://www.moodle.tum.de/course/view.php?id=21664

Lecture recordings can be downloaded from the TTT archive:

http://ttt.in.tum.de/lectures/index_ss15.php#GAD

 

 

If you have any questions, please contact the tutor first or ask in Piazza.

Anything that cannot be clarified about this goes to [email protected]