• 28.01.2019: The fourteenth problem set is online. This is the final problem set.
• 14.01.2019: am Montag, den 21.01.2019, findet im Rahmen eines Zusatztutoriums von 10–12 Uhr die Nachbesprechung der Probeklausur im SR 049 statt. Die Probeklausur enthält Aufgabentypen, die auch repräsentativ für die Abschlussklausur sind. Da bei der Nachbesprechung Lösungen zu Probeklausur besprochen werden, ist es ratsam, falls man es noch nicht gemacht hat, vorher selbst die Probeklausur durchzugehen als Vorbereitung der Klausur.
• 21.01.2019: The thirteenth problem set is online. This is the penultimate problem set.
• 14.01.2019: The twelfth problem set is online.
• 07.01.2019: Happy new year! The eleventh problem set is online.
• 17.12.2018: The tenth problem set is online. All problems are extra credit.
• 12.12.2018: Am 20.12.2018 findet in der Vorlesungszeit eine Probeklausur statt. Die Probeklausur enthält Aufgabentypen, die auch repräsentativ für die Abschlussklausur sind. Die Probeklausur kann abgegeben werden und zum Ende des Semesters verwendet werden, um bis zu 20 Übungspunkte auszugleichen.
• 10.12.2018: The ninth problem set is online.
• 03.12.2018: The eighth problem set is online.
• 26.11.2018: The seventh problem set is online.
• 19.11.2018: The sixth problem set is online.
• 12.11.2018: The fifth problem set is online.
• 05.11.2018: The fourth problem set is online.
• 29.10.2018: The third problem set is online.
• 22.10.2018: The second problem set is online.
• 01.10.2018: The first problem set is online.
• 01.10.2018: The first lecture takes place Tuesday, 16.10.2018, 14:15.
• 01.10.2018: The website is online.

The Problem Sets will appear only online on this website.

Topics

• algorithms
• basics
• machine model
• time and space
• approaches to algorithm analysis
• O-Notation
• solving recurrences
• Why efficient algorithms?
• data structures
• lists: simply and doubly linked
• bit vector
• heaps
• search trees
• balanced: AVL, red-black, ...
• external: B-trees, (a,b)-trees
• skip-lists
• hash tables
• conflict resolution (chaining, open addressing, cuckoo)
• universal hashing
• abstract data types
• for sets and lists
• stack, queue
• priority queue
• map, ordered map
• iterators
• relations, graphs, trees
• geometric objects
• divide and conquer
• dynamic programming
• backtracking
• greedy algorithms
• plane-sweep
• randomized algorithms
• amortized analysis
• selected algorithms
• graph algorithms
• topological sorting
• shortest paths (Dijkstra, Bellman-Ford)
• minimum spanning trees
• string searching
• Huffman-compression
• game trees
• FFT
• programming
• properties of good software
• reusability
• maintainability
• clarity
• low failure rate
• tools
• abstraction/information hiding
• modularization
• generics
• object oriented programming
• design patterns
• Iterator
• Composition
• template method
• Comparator
• Decorator
• language features
• objects and inheritance, access modifiers
• polymorphism
• interfaces and abstract classes
• Java collections framework
• generics in Java
• pakets in Java
• annotations in Java
• persistence und Serialization in Java
• algebraic data types in Haskell
• specification and correctness
• verbal specification
• formal specification (model based/algebraic/functional)
• Hoare-calculus
• memory management
• stack and heap
• memory management in C/C++
• garbage collection
• memory allocation/fragmentation

Actual Lectures

• Tuesday, 16.10.2018
• Introduction
• The class is about data: representation, manipulation, and access.
• Introductory example: polynomials
• Representation of a polynomial of degree n as a sequence of coefficients.
• Addition of two polynomials needs O(n) operations
• Evaluation at a position z requires O(n) operations using Horner's method
• Multiplication of two polynomials needs O(n^2) Operations
• Thursday, 18.10.2018
• Representation as the values at at least n+1 different positions
• Addition still needs O(n) operations
• Evaluation at a position z needs O(n^2) using polynomial interpolation (e.g., Newton or Lagrange Interpolation)
• Multiplication needs O(n) operations
• Through a clever choice of the n+1 different positions, we can switch from the coefficient representation to the value representation in O(n log n) operations (Fast Fourier Transformation, FFT)
• FFT is one of the most important algorithms, with applications in digital signal processing, data compression, for for fast quantum algorithms to break standard encryption schemes, etc. cf. pp 27ff of the MafI script.
• Tuesday, 23.10.2018
• Algorithms: Definition and quality criteri
• How to evaluate an algorithm: benchmarking and theoretically
• experimental evaluation (testing/benchmarking): very concrete results, but also many difficulties
• theoretical analysis: provides general and universal statements, usually cleaner than an experimental evaluation, but might fail to consider some key factor that affect an algorithm's performance
• theoretical analysis requires an abstract machine model that defines the steps allowed in an algorithm.
• Definition Random Access Machine (RAM)
• Definition: running time on a ram
• An example program on the RAM, with a running time analysis
• Thursday, 25.10.2018
• Constant factors do not matter on the RAM. Thus, we may use pseudocode to write and analyze our algorithms.
• O-Notation and asymptotic analysis: lets us focus on the qualitative running time and provides a clean statement about the performance of an algorithm (Careful: the O-notation hides constant factors and thus might be deceptive)
• Tuesday, 30.10.2018 (given by Max Willert)
• Recursion
• The over-hyped Fibonacci-Numbers
• Recursion trees as a tool to visualize recurrences relations
• dynamic programming: recursion + table, to remember results for repeated subproblems
• Thursday, 01.11.2018 (given by Max Willert)
• Simple data structures: queue and stack
• implementations: linked list, static array, dynamic array
• dynamic array
• amortized analysis: consider a sequence of m operations. If every such sequences needs f(m) steps, then the amortized cost per operations is f(m)/m.
• proof, that PUSH in a dynamic array has amortized cost O(1), using the accounting method: pay 3 euros per operation, argue, that this suffices to pay for all the copying operations.
• good software design: good software is easily maintained, flexible, easy to understand, bug-free
• Means to achieve this: information hiding
• Pieces have a clearly specified interface to communicate with the outside
• internal implementation is hidden
• a type whose objects can only be manipulated through a clearly specified interface the internal data cannot be accessed
• Java is an object oriented programming language
• central notion: objects
• important properties: encapsulation, inheritance, polymorphism
• define interface a superclass/Interface, implementation as subclass.
• use encapsulation to hide implementation details from the outside
• Tuesday, 06.11.2018 (given by Max Willert)
• Specification of the ADT Priority Queue
• with a model: define an abstract model for the data type, specify operations wrt the mode. Advantages: short and exact. Disadvantage: requires prior knowledge, can we unwieldy; danger of overspecification. Possible models include, e.g., mathematical objects or Haskell data types.
• Implementations of the ADT priority queue
• unsorted and sorted linked list
• binary heaps: notes
• bottom-up heap construction
• Thursday, 08.11.2018
• ADT dictionary/map/associative array: can store, lookup and delete entries
• Hashing
• K set of keys, V set of values, goal: store subset S of K x V. Typical situation: S is much smaller than K.
• idea: store S in an array, use keys as indices. Problem: K is very large and does not necessarily consist of integers. Solution: pick a hash function h : K → {0, ..., N-1}, that assigns a position in the array to each key.
• If K is larger than N, then there will be collisions (two distinct keys are mapped to the same position in theory array). Ways of dealing with collisions: collision resolution:
• chaining: all entries in the same position.
• open addressing: if a position is occupied, search for a new one
• cuckoo: if a position is occupied, move the occupying element
• hash table: array + hash function + strategy for collision resolution
• Tuesday, 13.11.2018
• how to choose a hash function
• hashCode from K to N (natural numbers), compression function from N to {0, ..., N-1}.
• hash function should spread keys evenly over the hash table and destroy all structure in the key set (i.e., h should behave like a "random" function)
• Chaining: Implementation of the operations.
• Analysis of hashing with chaining
• assumption: hash function behaves randomly
• then: expected time per operation is O(1+|S|/N).
• |S|/N is called load factor. If the load factor is O(1), so is the running time. In practice we want to keep the load factor constant (say, about 0,75) (→ dynamic array)
• Thursday, 15.11.2018
• universal Hashing
• Assumption of a random hash function is not realistic
• But, we can choose a random function from a small set of pseudorandom functions while maintaining the theoretical guarantees on the running time
• open addressing and linear probing
• all entries are stored in a single array
• if a position is occupied, scan array for the next free position
• get and remove: look for first NULL-position
• mark deleted entries with a special token DELETED, regularly rebuild the hash table
• Pseudocode
• in expectation, all operations require O(1) time (if the load factor is small enough and the hash function behaves randomly)
• Cuckoo hashing
• use two hash functions, every entry can be only at two possible positions (O(1) worst-case time for get and remove)
• insertion: if a position is occupied, move existing entry to alternative position. If the alternative position is occupied, iterate. If the table is full or if there is a cycles, rebuild the table with a new choice of hash functions.
• Pseudocode
• If the load factor is small enough and the hash functions behave randomly, insertions require O(1) amortized expected time
• Proof
• Tuesday, 20.11.2018
• further applications of hash functions
• hash functions give a way to map a large, possibly infinite key universe into a small range.
• Collisions should be unlikely: if the range has size N, then the probability of a collision for a random hash function is 1/N.
• If N is moderately large, say N=2^128 oder N=2^256, then collisions with a random hash functions are virtually impossible in practice.
• Complexity theory: if a function is sufficiently complicated, it looks like a random function ist,
• Use of complicated hash functions as a message digest/finger print/checks sum, to ensure the integrity of the data.
• Hope: an adversary can only find a collision by trying N different random pre-images. The hash value practically determines the pre-image.
• Application in data structures: hash pointer. Store the hash value of the data in an object together with a reference to the object. This ensures the integrity of the reference.
• Application of hash pointers in a linked list yields a tamper proof write only log. This data structure is called blockchain.
• like dictionary, but now the key universe K is assumed to be ordered.
• put(k,v), get(k), remove(k)
• max, min: find the maximum and minimum key in the data structure
• pred(k): find the largest key in the data structure that is strictly smaller than k (predecessor)
• succ(k): find the smallest key in the data structure that is strictly larger than k (successor)
• Thursday, 22.11.2018
• skip lists
• store a hierarchy of lists L0, L1, .... L0 stores all entries, L(i+1) stores each entry from L(i) with probability 1/2
• pseudocode for the operations
• expected space O(n), expected height O(log n), expected search time O(log n), where n is the number of entries
• original paper
• Tuesday, 27.11.2018
• trees: tree, rooted tree, height, leaf, parent node, child node, binary tree
• binary search tree: rooted, ordered tree the spells the entries in the nodes and that has the binary search tree property: for every node with key k, all keys in the left subtree are less than k and all keys in the right subtree are larger than k.
• Operations on a binary search tree by example
• Pseudocode for the operations.
• All operations have worst-case running time O(height of the tree).
• In the worst case, the tree can degenerate and have height n-1 (e.g., if we insert 1, 2, ..., n, in this order).
• Thursday, 29.11.2018
• AVL-trees
• height-balanced trees; for each inner node, the heights of the left and the right subtree differ by 1.
• Height-balance guarantees height O(log n)
• structural operations in binary trees
• single rotations: left rotation (l-Rotation), right rotation (r-Rotation)
• double rotations: lr-rotation (first left, then right), rl-rotation (first right, then left)
• if u is a node in which the heights of the two subtrees differ by exactly 2, and if all descendants of u are balanced, then there is always an (l-,r-,lr-, or rl-)rotation, that balances the subtree at u.
• insertion and deletion in AVL-trees: insert or delete as in a reguls binary search tree, follow the path to the root, and perform appropriate rotations in order to balance all the nodes on the path to the root.
• Conclusion AVL-trees
• advantages: O(log n) worst-case running time; small space usage
• disadvantages: cumbersome implementation, (case distinction); possibly a lot of rotations become necessary.
• Tuesday, 04.12.2018
• no class – dies academicus
• Thursday, 06.12.2018
• remarks on red-black trees
• further relax the tree structure compared to AVL-trees, so that less restructuring operations are necessary during insertion and deletion
• every node is red or black. The coloring must fulfill certain conditions. This ensures height O(log n).
• Insertion and deletion is similar to AVL-trees, but now the structure can be restored by recoloring the nodes. This reduces the number of rotations, but there are more cases to distinguish.
• Popular data structure that is implemented often. For example, in the Java-library, the C++-STL, or in the Completely-Fair-Scheduler in the Linux kernel.
• (a,b)-trees
• a,b are natural numbers with b >= 2a-1 and a >= 2.
• Every node has degree at most b. The root has degree at least 2 (or 0), every internal nodes has degree at least a.
• The root stores between 1 and b-1 keys. All other nodes store between a-1 and b-1 keys.
• the binary search tree property is generalized to several children.
• all trees have the same depth
• the depth is O(log n/log a).
• the search is a suitably adapted BST search for multiway nodes. The running time is O(b log n/log a).
• Insertion in (a,b)-trees: search to a leaf insert the entry into the leaf. If the leaf overflows (b entries), split is and insert the middle entry into the parent node. Repeat if necessary, until the root. Running time O(b log n / log a).
• Deletion in (a,b)-trees
• if the entry to be deleted is in an internal node, replace it by its successor and delete it from the leaf.
• deletion from a leaf: remove the entry. If the leaf has at least a entries, nothing needs to be done; otherwise, try to borrow an entry from a sibling node; if this is not possible; join it with a sibling node; then possibly the parent nodes underflows; repeat if necessary.
• Applications: (2,4)-trees are equivalent to red-black trees; as external data structures in database management systems or in file systems (e.g., Btrfs, NTFS)
• more details on the operations can be found here.
• Tuesday, 11.12.2018
• Algorithms for strings
• string: finite sequence of symbols from an alphabet sigma
• codes:
• assign a bit sequence to each symbol from the alphabet.
• to encode a string, concatenate the corresponding bit sequences.
• goals: (i) unique decodability, (ii) encoding should be as short as possible (alternatively: (ii) high fault-tolerance)
• prefix-free codes are codes in which no codeword is prefix of another codeword
• prefix-free codes can be decodes uniquely
• prefix-free codes can be represented as binary trees.
• Huffman-compression
• finds an optimal prefix-free codes for a given sequence of frequencies.
• greedy algorithm: make choices that are locally optimal, hope for a global optimum.
• incremental construction of code tree: begin with a leaf for each symbol, annotate leaves with corresponding frequencies; iteratively unite subtrees with smallest frequencies and add frequencies, repeat, until one tree is left. The result is called Huffman-tree
• Thursday, 13.12.2018
• Huffman-codes are optimal.
• Lemma: For two symbols a, b with minimum frequencies, there is an optimal prefix-free code in which a and b are siblings.
• Prove the theorem by induction on the size k of the alphabet: for k = 2, the claim is clear; for the inductive step, assume that for alphabet size k, there is a prefix-free code that is better than the Huffman-code. Then we can use the lemma to construct a prefix-free code for alphabet size k-1 that is better than the Huffman-code. This yields a contradiction to the inductive hypothesis.
• remarks on data compression
• Huffman-codes are optimal, under three assumptions 1. the code is prefix free; 2. we encode symbol by symbol; 3. the compression is lossless
• Assumption 2 can be circumvented in several ways (i) run-length encoding: store runs of repeated characters only once together with their length. Used, e.g., in the PCX-file format. (ii) dictionary coding, e.g, LZW. Repeated patterns are abbreviated. Used, e.g., in the GIF-file format. LZW was patented, leading to a lot of controversy.
• To circumvent assumption 3, we assume that unnecessary information can be discarded. This unnecessary information can be identified through appropriate transformations. Examples include JPEG or MP3
• Similarity of strings: diff, fc, longest common subsequence, edit distance
• Tuesday, 18.12.2018 (given by J. Cleve)
• finding the longest common subsequence (LCS) of two strings s and t.
• First, we only determine the length of such a LCS (LLCS).
• Recursive approach: consider only the respective last symbol of s and t (the first one also works). If these symbols are equal, then LLCS = 1 + the LLCS of s' and t', the strings obtained from s and t by removing the last symbol. If these symbols are not equal, recursively determine the LLCs of s' and t and of s and t'. Take the maximum of the two solutions.
• As soon as the recursion is clear, we can immediately write it down as a formula and implement it.
• But: many subproblems are considered repeatedly. Thus, we can use a table for remembering intermediate results. This is called dynamic programming.
• Two possibilities of implementation: (i) top down as a recursion, but using a lookup table to avoid repeated subproblems; or (ii) bottom up, by filling the table iteratively by increasing size of the subproblems. Solution (ii) is often preferable, since it leads to short and efficient code.
• As soon as the LLCS table is available, we can find the LCS by reconstructing the recursion (or by using a second table that tracks the recursively computed maxima).
• An example pseudocode is available here.
• Algorithms for string search
• The naive algorithm and the algorithm of Rabin-Karp: notes.
• Thursday, 20.12.2018
• Practice exam
• Tuesday, 08.01.2019
• String searching: more on Rabin Karp: notes.
• Dictionaries for Strings: tries
• Tries are specialized data structures that store sets of strings and support the operations of the ADT ordered dictionary.
• a trie is a rooted multi-way tree: every inner node has between 1 and S children, where S = |Sigma| is the alphabet size.
• The edges are labeled with symbols from Sigma., so that for each node, each symbol appears at most once.
• We can obtain the strings in the structure by concatenating for each leaf v the labels of the edges on the path from the root to v.
• Problem: What happens, is one string as the prefix of another string? Solution 1: Introduce an additional flag in the tree nodes that indicates the end of a string. Disadvantage: leads to more complicated algorithms and a more involved data structure. Solution 2: Introduce a special symbol that does not appear in the alphabet and that indicates the end of a word. Implicitly add this symbol to each string in the data structure. Note that Solution 2 is essentially equivalent to solution 1, but it leads to conceptually simpler algorithms.
• Tries support the operations of the ADT ordered dictionary in time O(r|Sigma|), where r is the total length of the the strings that are involved in the query.
• The space for the trie is proportional to the total length of the strings that are stored in it.
• Compressed tries/Patricia-tries: replace long paths that consist of nodes with only one child by a single edge that is labeled with the corresponding substring. This reduces the number of nodes to O(l) (l = number of strings stored in the trie). Asymptotically, the space requirement stays the same.
• Thursday, 10.01.2019
• suffix-trees
• a suffix-tree is a compressed trie that stores all the suffices of a given string s. To keep the total space linear in the size of s, the edges do not store the corresponding substrings of s, but only pointers to the corresponding positions in s.
• There are special algorithms to construct a suffic tree in linear time from a given string s (The naive insertion of all suffices could require quadratic time).
• Suffix-trees have many applications in the area of string algorithm. A few of them can be found on the Wikipedia-page.
• Graphs
• basic definitions, examples
• some algorithmic problems on graphs: are two vertices connected? Finding the connected components; finding shortest paths (unweighted and weighted); topological sorting; minimum spanning trees; minimum cuts.
• two possible representations in the computer: adjacency matrix and adjacency list.
• The operations of the ADT graph.
• notes.
• Tuesday, 15.01.2019
• depth-first-search
• single pair shortest path problem (SPSP): find a shortest path from s to t.
• single source shortest path problem (SPSP): Find shortest paths from s to all other vertices in the graph.
• Subpath-optimality-property: subpaths of a shortest path are shortest paths
• Representation of the shortest paths from s to all other vertices: shortest path tree: each vertex v stores a pointer to its predecessor on a shortest path from s to v. The shortest path can be reconstructed by following the predecessor pointers.
• Shortest paths in unweighted graphs: modify BFS to remember the predecessor pointers and distances to s. See here.
• Thursday, 17.01.2019
• shortest paths in weighted graphs: Dijkstra's Algorithm
• Assumption: all edges weights are positive
• Modify BFS-algorithm for unweighted graphs in two ways: 1. Use a priority queue instead of a simple queue; 2. When the neighbors of a vertex v are being examined, check whether we can find a shorter path to the neighbor through v.
• Pseudocode can be found here.
• The running time depends on the implementation of the priority queue. There are |V| inserts, |V| extractMins, and O(|E|) decreaseKeys. Using a binary heap, the running time is O(|V| log |V| + |E| log |V|).
• Tuesday, 22. 01. 2019
• Dijkstra: correctness
• basic idea: call a vertex v finished, if v is no longer contained in the priority queue. The values v.d and v.pred refer to shortest paths that use only nodes that are finished (possibly except for v). All paths to vertices that are not yet finished must be at least as long as all the shortest paths to vertices that are finished. Whenever we finish a new node, all these invariants remain valid, because the edge weights are positive and because we extract the vertex with minimum v.d from the priority queue.
• Thursday, 24. 01. 2019
• A*-search with a consistent heuristic;
• We want a shortest path from s to t.
• in addition to the graph, we have a heuristic: a function h: V -> R+ that estimates the distance from every vertex v to t.
• h is called consistent if the following holds for every edge e = uv: h(u) <= e.length + h(v)
• A*-search corresponds to Dijkstra's algorithm with modified edge weights: for an edge e = uv i, we set e.length' := e.length + h(b) - h(v)
• consistency ensures, that the new edge lengths are nonnegative.
• Edge that lead towards t become shorter; edges, that lead away from t become longer.
• Die length of every path from s to t changes by h(t) - h(s) (telescoping sum). Thus, a shortest path for the new weights is also a shortest path for the old weights
• If the heuristic is chosen well, we must examine significantly fewer vertices as with regular Dijkstra.
• Applications: Anwendungen: route planning; search problems in artificial intelligence.
• slides
• All-Pairs-Shortest-Paths: Floyd-Warshall
• APSP-Problem: find a shortest path from u to v for all pairs of vertices u and v.
• If all edge weights are positive and if the graph contains few edges, we can run Dijkstra's algorithm for every vertex.
• A general algorithm that uses dynamic programming: number nodes from 1 to n, arbitrarily. For k = 0 to n, recursively find the lengths of the shortest paths that use only internal vertices numbered 1 to k.
• The Floyd-Warshall algorithm can be implemented with O(n^3) time and O(n^2) space (n = number of vertices). With O(n^3) space, we can also find all the shortest paths.
• Tuesday, 29. 01. 2019
• minimum spanning trees (MST)
• given: graph G=(V, E), undirected, weighted, connected
• want: set of edges T with minimum total weight such that (V, T) is a tree
• general strategy: greedy algorithm; begin with an empty edge set, successively add safe edges.
• An edge set A is called safe, if there is an MST that contains A
• cut lemma: Let A be a safe set of edges, and let S be a cut that is crossed by no edge from A. Let e be an edge of minimum weight, that crosses S. Then we can obtain a safe st of edges by adding A to A.
• We use the cut lemma in order to find safe edges.
• Thursday, 31. 01. 2019
• Two MST-algorithms: the algorithm of Prim-Jarník-Dijkstra and the algorithm of Kruskal.
• Prim-Jarník-Dijkstra: grow the MST from a start vertex s. In each step, add the lightest edge incident on the current connected component that contains s. The algorithm is implemented in almost the same way as Dijkstra's algorithm for shortest paths, while changing only two lines. The running time is identical to Dijkstra's algorithm.
• Kruskal's algorithm: sort the edges according to their weight. In each step, add the next edge if and only if it connects two distinct connected components.
• To maintain the connected components, we need a Union-Find-Structure: maintain a partition of a universe into sets, such that we can unite two sets of the partition (UNION) and such that we can find for each element of the universe the set that contains it (FIND)
• Simple solution: each set has a representative. The FIND-operation returns the representative. The UNION-operation changes the representative for all elements in the smaller set to the representative of the larger set.
• If the representative of an element changes, the size of its set grows by a factor of at least two. Thus, the total number of representative changes for each element is logarithmic.
• Running time of Kruskal: O(|E| log |E|).
• Tuesday, 05. 02. 2019 (given by Jonas Cleve)
• Computational complexity theory: computability and complexity; efficiency; thesis of Cobham-Edmonds; extended Church-Turing thesis.
• Foundations of computational complexity theory; decision problems; running time; Turing machines; complexity classes.
• The complexity class P: all language, for which membership can be decided efficiently. Formal definitions and example.
• time hierarchy theorem: There are languages that are "arbitrarily hard" to decide.
• Thursday, 07. 02. 2019
• NP: The complexity class with all decision problems, for which there are certificates of membership that are polynomial in length and that can be verified in polynomial time.
• Examples of problems in P: MST, Shortest Path, Optimum Prefix Compression
• all problems in P are also in NP
• Problems in NP that are now known to be in P: graph coloring, subset sum, Sudoku.
• Tuesday, 12. 02. 2019
• Sudoku and Sokoban.
• If a Sudoku puzzle has a solution, this solution can be written down and checked efficiently.
• Most likely, this is not the case for Sokoban. There are Sokoban-puzzles for which the solution ist extremely long, and we do not know how to represent it efficiently.
• While Sudoku is known to be in NP, Sokoban is only known to be in the larger complexity class PSPACE.
• A method to compare computational problems with respect to their hardness: polynomial time reductions.
• Hardest problems in NP: NP-complete problems
• Examples of NP-complete problems: graph coloring; subset sum; Sudoku
• End of class
• Thursday, 14. 02. 2019
• exam
• Wednesday, 20. 02. 2019
• Klausureinsicht
• Monday, 01. 04. 2019
• second exam
• Recommended Prerequisites

• discrete mathematics, logic and probability theory
• programming skills in Haskell, Python and Java

References

• P. Morin: Open Data Structures, an open content textboox: [link]
• T. H. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 2009: Recommended for further study. A comprehensive textbook, contains a lot more material than is covered in the lectures. Very formal, sometimes the intuition gets lost in the detail.
• R. Sedgewick: Algorithms in Java (Part 1–5), Addison-Wesley, 2003: Also a comprehensive treatment of algorithmics, with a slightly different perspective. Has a special focus on sorting algorithms.
• G. Saake, S. Sattler: Algorithmen und Datenstrukturen, dpunkt.verlag, 2013: In German. Covers many topics, but does not go very deep.
• M. Dietzfelbinger, K. Mehlhorn, P. Sanders: Algorithmen und Datenstrukturen: Die Grundwerkzeuge, Springer, 2014: [English] [German]
• M.T. Goodrich, R. Tamassia: Data Structures and Algorithms in Java, Wiley, 2014: Covers most of the lecture material, very good presentation. However, due to the outrageous pricing, the book is not recommended for purchase.

There will be an exam at the end of the semester, and a second alternative exam at the beginning of the next semester. If you are taking the class for the first time, you can improve your grade by taking the second exam.

The exam takes place Thursday, February 14th, 14:00–16:00.

To pass the class, you must

• regularly attend the tutorial sessions (at least 80% of the time);
• obtain at least 60% of the possible credits on the problem sets and present two homework problems in the tutorial sessions;
• obtain at least 50% of the possible credits on the final exam.

The successful completion of the homework requirement and passing the final exam are independent criteria. The class is graded. The grade is determined exclusively by the final exam.

The class takes place Tuesday and Thursday, 14:00–16:00, in the large lecture auditorium, Takustraße 9. There are six student TAs who conduct the tutorial sessions (Christopher Filsinger, Johathan Gadea Harder, Fabian Halama, Nina Matthias, Lena Strobl, Valeria Zahoransky). The problem sessions start in the first week, after the first class.

Monday
14:00–16:00 Takustraße 9, SR 055 Lena Strobl
16:00–18:00 Arnimallee 7, SR 031 Christopher Filsinger
Tuesday
08:00–10:00 Takustr. 9, SR 006 Valeria Zahoransky
10:00–12:00 Takustr. 9, SR 055 Jonathan Gadea Harder
12:00–14:00 Arnimallee 6, SR 009 Jonathan Gadea Harder
12:00–14:00 Arnimallee 7, SR 031 Fabian Halama
16:00–18:00 Arnimallee 6, SR 031 Nina Matthias
Wednesday
14:00–16:00 Arnimallee 7, SR 031 Fabian Halama
16:00–18:00 Takustr. 9, SR 046 Lena Strobl
Friday
08:00–10:00 Takustr. 9, SR 055 Valeria Zahoransky
14:00–16:00 Takustr. 9, SR 006 Christopher Filsinger

Office hours: Tuesday, 13:00–14:00, room 112 and upon request.

The problem sets are published here each week. They appear only online. The usual work period is from Monday to Friday, 11 days later. The homeworks must be in the respective TAs mailbox by 10:00 on Friday. The homeworks must be done in groups of two.

Homeworks that are turned in late will not be graded.

No.OutDue pdftexNotes
1 01.10.2018 26.10.2018
2 22.10.2018 02.11.2018
3 29.10.2018 09.11.2018
4 05.11.2018 16.11.2018
5 12.11.2018 23.11.2018 binary heaps
6 19.11.2018 30.11.2018 hashing
7 26.11.2018 07.12.2018 skip lists
8 03.12.2018 14.12.2018 binary search trees
9 10.12.2018 21.12.2018 (a,b)-trees
10 17.12.2018 11.01.2019 extra credit
cuckoo-hashing
Practice Exam 20.12.2018 none
11 07.01.2019 18.01.2019 string search
12 14.01.2019 25.01.2019 graphs
13 21.01.2019 01.02.2019
14 28.01.2019 08.02.2019