Week 11

Published

June 23, 2025

VL 20 - 23.06.25

  • revision of previous lecture: definition of a heap

    • for the heap tree and als its subtrees: root has the highest priority (max heap) \(\Rightarrow\) parent has higher priority than its children

    • the heap tree is perfectly balanced & left-leaning \(\Rightarrow\) flattening as Array is possible

    • for any node k

      • parent: (k - 1) // 2
      • left child: 2 * k + 1
      • right child 2 * k + 2

    • insert operation:

      1. append new elements at the end of the array (O(1))
      2. whenever necessary repair the heap-condition with upheap() after inserting

    • implementation

      class Heap:
    def __init__(self):
        self.data = []

    def  push(self, priority):
        self.data.apipend(priority)
        upheap(self.data, len(self.data) - 1)

    def upheap(a, k):
        while True:
            if k == 0: # repair has ended
                break
            parent = (k - 1) // 2
            if a[parent] > a[k]: # heap-cond holds
                break
            a[parent], a[k] = a[k], a[parent] # swap
            k = parent

      Heap Data Structure (Cont)

  • deleting an element:
    • deleting the largest element (the first element):
    1. replace last element (the smallest) with the first element (the largest) and delete the last element. (now the first element is violating the heap cond because it is the smallest)
    2. repair the heap condition starting from the root, successively pushing node down
    def pop(self):
    last = len(self.data) - 1
    self.data[0] = self[last]
    del self.data[last]
    downheap(self.data, last - 1)

def downheap(a, last):
    k = 0 # 
    while True:
        left, right = 2 * k + 1, 2 * k + 2 
        if left > last: # repair has ended, because k is a leaf
            break
        if right <= last and a[right] > a[left]: 
            child = right
        else: 
            child = left
        if a[k] > a[child]: break # heap cond  holds
        a[k], a[child] = a[child], a[k] # swap
        k = child
    number of comparisons O(d) = O(logN)

Heapsort - Sorting with the Heap Techniques

the idea is to first create a heap from the array

implementation:

def heap_sort(a):
    N = len(a)
    for k in range(1, N):
        upheap(a, k)
    # a is sorted a a sa heap
    for k in range(N - 1, 0, - 1): # loop iteration backwards
        a[0], a[k] = a[k], a[0] # bring the currently largest element to the position k
        downheap(a, k - 1) # repair the heap condition in the remaining heap

Treap Data Structure

Treap is a simultaneously both

  • a search tree
  • a heap

implementation:

class TreapNode:
    def __init__(self, key, priority, value):
        self.key = key
        self.value = value
        self.priority = priority
        self.left = self.right = None
  • idea:
    1. The tree satisfies the search tree condition w.r.t the key
    2. The tree satisfies the heap condition w.r.t. the priority
  • The inventor of the Treap DS showed that it is possible and feasible to satisfies both conditions at the same time
    • e.g. insert:
      1. normal tree_insert w.r.t the key (priority is ignored) \(\Rightarrow\) search tree condition is satisfied
      2. repair the heap condition on the way back of the recursive call stack, if the current node has lower priority than its child (important: the heap-condition can be only violated w.r.t to one of the children, namely in the subtree in which it was inserted)
        1. if the left child has higher priority \(\Rightarrow\) right-rotation
        2. if the right child has higher priority \(\Rightarrow\) left-rotation
  • possible appropriate priorities:
    • random numbers \(\Rightarrow\) the tree is balanced on average
    • access counter \(\Rightarrow\) rotate the element upwards if more often access than the parent (access optimized tree, i.e. important elements are closer to the root - and this is faster.)

Index Sort / Indirect Sort

given:

  • a - an unsorted array

  • p - array, where the indices are stored in a sorted order.

  • p[i] -> k (index). k is the index of an element before the sorting, s.t. i is the index after the sorting. (p is a permutation of the numbers 0, …, N - 1)

  • applications:

    • iff a read-only, in-place is not possible
    • if multiple arrays have to be sorted in the same way (?)

  • implementation

    def index_sort(a, p):
  r = [None] * len(a)
  for i in range(len(a)):
      r[i] = a[p[i]]
  return r

  • p can be obtained by any sorting algorithm, where the key-functoin accesses the original Array

    a = [...] # read-only array, to be sorted 
p = list(range(len(a))) # indices 0, ..., N - 1
quick_sort(p, key_function = lambda k: a[k])
r = index_sort(a, p)

VL 21 - 26.06.25

Graphs & Graph Theory

Origins of graph theory: Solution to the Kongisberg Problem:

  • is it possible to make a city tour without crossing any bridge ever twice?

Euler’s answer: No.

Koniegsberg

Solution: An Euler path exist only if all nodes (other than start and end nodes) have an even number edges incident to them (i.e. the degree of the nodes is even)

Definitions for Graphs:

  • Graph G = (V, E)
    • V: set of all nodes / vertices
    • E: Set of all edges, \(E \subseteq V \times V\)
  • This is a normal graph: at most one edge between any two nodes. Initially we also exclude self loops, i.e. \((u, u) \notin E\)
  • Multigraph: multiple edges between nodes are allowed (Like in the Konigsberg example)
  • undirected graph: \((v, u) \in E \Rightarrow (u, v) \in E\)
  • directed graph: not undirected.
  • Degree of a node:
    • undirected: number of edges incident to a node (we don’t count twice)
    • directed:
      • out degree: number of outgoing edges
      • in degree: numb of inocming edges
  • Complete Graph:

complete-graph

Let \(N := |V|, M := |E|\). For a complete graph we have:

  • \(degree(u) = N - 1\)

  • handshaking lemma: \(M = \frac{N(N - 1)}{2}\)

  • Subgraph: \(G' = (V', E'), V' \subseteq V, E' \subseteq E\) and \((u, v) \in E' \Rightarrow V'\)

    • induced subgraph: for an arbitrary \(V' \subseteq V\), \(E' := E \\ \{(u, v) : u \notin V' \text{or} v \notin V'\}\)
    • spanning subtree: \(V' = V, E' \subset E\)

  • Walks (Weg) in graphs:

    • trivial walk of length 0: individual node
    • walk of length 1: a single edge of a graph
    • a generalized walk of a graph: a sequence of nodes \((v_1, v_2, ... v_k)\), s.t. \((v_i, v_{i + 1}) \in E, \forall i\) \(\Rightarrow\) length:= \(k - 1\)

  • Path: A Walk where each individual node is distinct (other than possibly start and end)

  • Cycle (Zyklus): a Walk with \(v_1 = v_k\)

  • Circuit (sometimes Cycle) (Kreis): a path with \(v_1 = v_k\)

  • Reachability (Erreichbarkeit): \(u \rightsquigarrow v \Leftrightarrow u \rightsquigarrow v :\Leftrightarrow\) there is a Walk between the nodes \(u, v\)

  • Euler walk: each edge is contained exactly once. (example: Haus of Niklaus)

  • Hamilton path: each node is contained eactly once

  • Hamilton Circuit: A Hamilton path, s.t. start = end.

    • This definition is relevant to the problem of the “Traveling Salesman”: find the hamilton circuit with the least weight (for graphs with weighted edges). Best known algorithm is \(\mathcal{O}(2^N)\).
    • This is the standard example of a “NP-hard problem” \(\Rightarrow\) no efficient algorithm is known.

euler-hamilton
  • weighted graphs:
    • node-weighted: a number (weight) is assigned to every node
    • edge-weighted: a number (weight) is assigned to every edge
    • or both
    • example: a graph of streets: edge weights = length of the roads
  • Planar Graphs:
    • a planar graph can be drawn in 2D, s.t. no edges intersect.
    • ex.: Haus of Niklaus
    • euler’s formula for any planar graph drawn without crossings: \(V - E + F = 2\)
  • Dual Graphs:
    • each surface gets a node
    • each edge defines a border between surfaces - each surface seperated by an edge is connected with an edge planar dual
Euler’s Formula (Primal Form)

For any connected planar graph drawn without edge crossings:

\[ V - E + F = 2 \]

Where:

  • \(V\) = number of vertices
  • \(E\) = number of edges
  • \(F\) = number of faces, including the outer (infinite) face
Dual Graphs and Euler’s Formula

The dual graph \(G^*\) of a planar graph \(G\) is constructed by:

  • Placing a vertex in each face of \(G\)
  • Connecting two vertices in \(G^*\) if their corresponding faces in \(G\) are adjacent (i.e., separated by an edge in \(G\))

In the dual:

  • The number of vertices in \(G^*\) is equal to the number of faces in \(G\): \(V^* = F\)
  • The number of edges remains the same: \(E^* = E\)
  • The number of faces in \(G^*\) equals the number of vertices in \(G\): \(F^* = V\)
Euler’s Formula Applied to the Dual

Since the dual \(G^*\) is also planar and connected (if \(G\) is), Euler’s formula also holds:

\[ V^* - E^* + F^* = 2 \]

Substituting the dual identities:

\[ F - E + V = 2 \]

This shows that Euler’s formula is preserved under duality, with \(V \leftrightarrow F\), and \(E\) unchanged.

Summary Table
Property Original Graph \(G\) Dual Graph \(G^*\)
Vertices \(V\) \(V^* = F\)
Edges \(E\) \(E^* = E\)
Faces \(F\) \(F^* = V\)
Euler’s Formula \(V - E + F = 2\) \(V^* - E^* + F^* = 2\)

Connected Graph

any two nodes \(u, v\) are connected \(u \rightsquigarrow v\).

  • connected components: maximal subgraphs of the graph that are connected.
  • tree: connected graph, s.t. no cucles exist
    • for a tree: \(|E| = |V| - 1\)
  • forest: a not connected graph, s.t. each connected component is a tree
  • spanning tree: a subgraph of a connected graph that is a tree, s.t. all nodes are touched.
    • \(\Rightarrow\) theorem: for a connected graph such a spanning tree always exists.