Syllabus

The formal course contents can be found in the official course syllabus. More concretely, the contents is defined by the lectures and lecture slides.

Here's a list of the parts that the course contains, with references to the slides:

• Complexity analysis (2)
  • Big O-notation
    • Definition of O(), Ω(), Θ()
    • Rules (O(c * f(n)) = O(f(n)), ...)
  • Common complexity classes (constant, logarithmic, linear, ...)
  • Cost models, know that we apply the uniform cost model and what characterizes that and the logarithmic model
  • Time complexity program analysis
    • Atomic operations, if-statements, function calls
    • Loops (nested, writing time requirement as (nested) sums, know how to simplify the most commons sums)
    • Recursion (writing time requirement as recurrence equations, solving the most common recurrence equations)
  • Worst case complexity
  • Amortized complexity (know what it means, but not calculate amortized complexity of code) (2, 14)
• The distinction between abstract data types (ADTs) and implementating data structures. (1)
• Invariants in the context of data structures. (6)
• ADTs and their standard operations
  • List (1)
  • Stack (5)
  • Queue (5)
  • Deque (5)
  • Priority queue (6)
  • Set / Map (8)
• Data structures (conceptually, time complexity of operations and also how to implement unless other specified). Implemented ADT specified in parenthesis.
  • Linked list (list, stack, queue) (10)
  • Dynamic array (list, stack) (1)
  • Circular array (queue) (5)
  • Double list queue (queue in Haskell) (5)
  • Binary heap (including array representation) (priority queue) (6)
  • Skew heap (excluding how to calculate the amortized complexity) (priority queue suitable for Haskell) (7)
  • Search tree (set, map)
    • Binary search tree (unbalanced) (8)
    • AVL tree (not on implementation level, not deletion) (8)
      • Rotations
      • Re-balancing
    • 2-3 tree (not on implementation level, not deletion) (9)
      • Absorb
      • Split
    • AA tree (not deletion) (9)
      • Skew
      • Split
    • B-tree (only conceptually) (9)
  • Skip list (not on implementation level) (set, map) (10)
    • Probabilistic
    • Deterministic
  • Hash table (set, map) (11)
    • Hash function
    • Rehashing
    • Chaining
    • Linear probing
• Trees, terminology and properties (binary, node, root, path, child, parent, ancestor, descendant, height, size, depth/level) (6)
  • Tree traversal (pre-order, in-order, post-order)
  • Concept of balanced trees
• Graphs
  • Terminology and properties (verteces/nodes, edges, directed/undirected, loop, multigraph, complete, path, cycle, DAG, (strongly) connected, (strongly) connected components, transpose) (12)
  • Relation between number of nodes and edges in non-multigraphs (directed, undirected, with/without loops, acyclic and connected (trees)) (12, 13)
  • Implementations (adjecency list, adjecency matrix) (12)
  • Pre-order depth-first search (12)
  • Determine connectedness (12)
  • Calculate strongly connected components (12)
  • Topological sorting (12)
  • Postorder depth-first search (12)
  • Cycle detection (12)
  • Breadth-first search (13)
  • Shortest paths in unweighted graphs (13)
  • Dijkstra's algorithm (shortest paths in weighted graphs) (13)
  • Minimum spanning trees (13)
  • Prim's algorithm (13)
• Searching and sorting (conceptually, time complexity, properties (in-place (3), stable (4)) and also how to implement unless other specified)
  • Binary search (3)
  • Sorting
    • Insertion sort (in-place) (3)
    • Merge sort (3)
    • Quicksort (including different pivot strategies) (4)
    • Introsort, natural merge sort, timsort (only coneptually) (4)
• Iterators in Java (10)
• Standard libraries (14)
• Algorithm methods (know the concepts)
  • Divide and conquer (3)
  • Greedy (13)