- 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
- radix trees, tries
- 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
- design paradigms
- divide and conquer
- dynamic programming
- backtracking
- greedy algorithms
- plane-sweep
- randomized algorithms
- amortized analysis
- selected algorithms
- graph algorithms
- breadth-first search, depth-first search
- 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
- Adapter
- 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
- modules in Haskell
- 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
- Tuesday, 16.10.2018
- Administrativa
- 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
- abstract data type (ADT)
- 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
- ADTs in Java
- 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.
- the ADT ordered dictionary.
- 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
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
- breadth-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
Wednesday, 20. 02. 2019
Monday, 01. 04. 2019
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. | Out | Due |
pdf | tex | Notes |
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 |
|
|
|