Runtimes

Queue

A queue is an abstract data structure that preserves the elements sequence and has two operations, enqueue and dequeue. Enqueue is the insert function, which inserts elements at the back of the queue. Dequeue is the exctraction function, and retrieves the first element at the front of the queue. A queue is therefore a FIFO-data structure (First In First Out).

Stack

A stack is an abstract data structure which, similar to a queue, preserves the elements sequence. Unlike a queue however, a stack is LIFO (last in first out) implying that it both inserts and extracts elements from the back of the structure. These operations are called push and pop respectively.

Heap

A heap is a list which can be viewed as a binary tree. A heap is an implementation of the priority tree data structure. Check out heapsort

Max heap property: No node can have a higher value than its parent node.

Hash

The purpose of creating hash tables or (hash maps) is to arrange elements into a predetermined number of groups. Each element passes it's key (this can be it's value) to a hashing function, which determines which group the element is placed in. Multiple elements may be placed in the same group. These collisions aren't inherently bad as they can be dealt with, but may lead to slower run times. Common ways to resolve collisions are by either creating linked lists or using open addressing. The former creates linked lists (chains) for elements with colliding hashes, while the latter moves a colliding element to a different hash. The latter can be achieved with methods like linear probing, quadratic probing, or double hashing.

Bucket sort uses a similar concept to group unsorted elements.

Example

Another example retrieved from the 2009 Continuation Exam:

Solve the following recurrence. Give the answer in asymptotic notation. Give a short explanation.

$$ T(n) = 2T(^n/_3) + ^1/_n $$

We have $a = 2, b = 3, f(n) = n^{-1}$. This gives us $\log_b a = \log_3 2 \approx 0.63$. Since $f(n) = n^{-1}$ is $O(n^{.63})$, leaving us in case 1 and the solution $T(n) \in \Theta(n^{.63})$.

Brute force

This method is pretty self explanatory. Iterate through the list (sorted or unsorted) from beginning to end and compare each element with the element you are trying to find. With $n$ elements in the list the runtime will be $O(n)$

Binary search

If we know that the list we are searching is sorted, we can use a better strategy than brute force. Let $a$ be the target value we are searching for in a sorted list $L$. We start by finding the middle element and check if it is equal to the element we are searching for. If so, we return the index and the search is complete. If it is not the element we are searching for, we compare it to our target value. If the middle value is larger than the search term, the search continues in the subset of smaller values (left). If it is less than the search term, the search continues in the subset of higher values (right). Regardless of direction, the search process will keep comparing the middle term and halving the possible answers until the target value is found.

In Python:

def binary_search(li, value, start=0):
    # Dersom lista er tom, kan vi ikke finne elementet
    if not li:
        return -1
    middle = len(li) // 2
    middle_value = li[middle]
    if value == middle_value:
        return start + middle
    elif value < middle_value:
        # Første halvdel
        return binary_search(li[:middle], value, start)
    elif value > middle_value:
        # Siste halvdel
        return binary_search(li[middle + 1:], value, start + middle + 1)

Each iteration will halve the searchable elements. The search can at most take $O(\log n)$ time, since there is only $\frac{n}{2^{log(n)}} = 1$ element left after $\log n$ halvings.

Stability

A sorting algorithm can be considered stable if the order of identical elements in the list that is to be sorted is preserved throughout the algorithm. Given the following list:

$$[B_1, C_1, C_2, A_1]$$

Sorting it with a stable algorithm the identical elements will stay in the same order before and after the sort.

$$[A_1, B_1, C_1, C_2]$$

Comparison Based Sorting Algorithms

All sorting algorithms that are based on comparing two elements to determine which of the two are to come first in a sequence, are considered comparison based. It is proven that $\Omega(n\lg n)$ is the lower threshold for number of comparisons a comparison based algorithm has to perform. In other words, it is impossible to produce a comparison based sorting algorithm which has a better worst-case runtime than $O(n\lg n)$.

def merge_sort(li):
    if len(li) < 2:    # Dersom vi har en liste med ett element, returner listen, da den er sortert
        return li
    sorted_l = merge_sort(li[:len(li)//2])
    sorted_r = merge_sort(li[len(li)//2:])
    return merge(sorted_l, sorted_r)

def merge(left, right):
    res = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                res.append(left.pop(0))
            else:
                res.append(right.pop(0))
        elif len(left) > 0:
            res.append(left.pop(0))
        elif len(right) > 0:
            res.append(right.pop(0))
    return res

def quicksort(li):
    if len(li) < 2:
        return li
    pivot = li[0]
    lo = [x for x in li if x < pivot]
    hi = [x for x in li if x > pivot]
    return quicksort(lo) + pivot + quicksort(hi)

Other Sorting Algorithms

Sorting algorithms that are not comparison based are not limited to having $O(n\lg n)$ as lower runtime threshhold. The prerequisite for these algorithms is that certain attributes are already known about the lists before sorting.

Neighbor Lists

Given the graph G with nodes $V = \{A,B,C,D\}$ we can represent each node's neighbor in the following manner:

$$A: [B, C] \\ B:[A, C] \\ C:[D]$$

To clarify, $A$ has edges to $B$ and $C$, $B$ has edges to $A$ and $C$, and $C$ has an edge to $D$. This method of representing graphs is useful when a graph is sparse, meaning it has relatively few edges.

Neighbor Matrices

For dense graphs, graphs with relatively many edges, neighbor-matrices may prove more useful for representing edges. For a graph with $|V|$ nodes, this would require a $|V| \times |V|$ sized matrix. Example:

    0 1 2 3 4 5
  -------------
0 | 0 1 0 0 0 1
1 | 0 0 1 1 0 1
2 | 1 1 0 1 0 0
3 | 0 0 1 0 1 0
4 | 0 0 0 0 0 1
5 | 1 0 1 0 1 0

This matrix represents a graph $G$ with nodes $V = \{0,1,2,3,4,5\}$. The matrix entry $a_{u,v}$ is $1$ if there is an edge from node $u$ to node $v$, and $0$ otherwise. Neighbor matrices can also be modified to represent weighted graphs, such that the entry $a_{u,v}$ now represents the weight on the edge $(u,v)$. For example, if the weight on the edge $(u,v)$ is $w(u,v) = 3$, the neighbor matrix entry $a_{u,v}$ is equal to $3$.

Breadth First Search (BFS)

Breadth first search is a graph traversal algorithm that as it examines a node, it adds all of that node's children to the queue. More precisely:

1. The input is a graph and a starting node. The algorithm uses a queue to establish in which order it visits each node. The first node added to the queue is the starting node.
2. As long as there exists elements in the queue, the algorithm removes (dequeues) the first element from the queue, mark the node as visited, then enqueue it's children.

BFS can mark each node with a distance value, which indicates how many edges away it is from the starting node. Also, if you are searching for an element using BFS, the search can be terminated when the node you are searching for is found and dequeued.

Runtime: $O(|V| + |E|)$

Depth First Search (DFS)

DFS is similar to BFS, but uses a stack instead of a queue. Since a stack is LIFO, each child node is pushed onto the stack until a leaf node is reached. The node on the top of the stack is then popped, handled and discarded before moving to the underlying node. More precisely:

1. The input is a graph and a starting node. The algorithm uses a stack to establish in which order it visits each node. The first node added to the stack is the start node.
2. The algorithm pushes child nodes to the stack until a leaf node is reached. The topmost node on the stack is then handled, and this repeats until a node has children.

DFS cannot find the distances between nodes in a graph, but can record how many nodes it visited before adding the node in question onto the stack, as well as when it removed said node from the stack. This is called start and stop times, which can prove useful for topological sorting.

Runtime: $O(|V| + |E|)$

Traversing order

In-order traversal, pre-order traversal, and post-order traversal all traverse nodes in the same order, the difference is when each node is handled (sometimes called visited or colored). When traversing a tree, these traversal methods work in the following way:

• In a pre-order traversal, nodes are handled before visiting any subtrees.
• In an in-order traversal, nodes are handled after visiting the left subtree.
• In a post-order traversal, nodes are handled after visiting the both subtree.

Traversal method	Visualization	Result
Pre-order		F, B, A, D, C, E, G, I, H
In-order		A, B, C, D, E, F, G, H, I
Post-order		A, C, E, D, B, H, I, G, F

Kruskal

Kruskal's algorithm creates a tree by finding the smallest edges in the graph one by one, and creating a forest of trees. These trees are gradually merged together into one tree which becomes the minimal spanning tree. First the edge with the smallest weight is found and this edge is made into a tree. Then the algorithm looks for the second smallest edge weight and connects these two nodes. If these were two free nodes they are connected as a new tree; if one of them are connected to an existing tree, the second node is attached to that tree; and if both are in separate trees these two trees are merged; if both are in the same tree then the edge is ignored. This method continues until we have one complete tree with all nodes.

Prim

Prim's algorithm creates a tree by starting in an arbitrary node and then adding the edge (and connecting node) with the smallest weight to tree. With now two nodes connected, the edge with the lowest weight that connects to either of the two nodes is added. This continues until all of the nodes have become a part of the tree. Runtime depends on the underlying data structure, however the curriculum uses a binary heap.

One-to-All

One-to-all means finding the distance to all notes from a single starting node.

def dijkstra(G,start): #G er grafen, start er startnoden
    pq = PriorityQueue() # initialiserer en heap
    start.setDistance(0) # Initialiserer startnodens avstand
    pq.buildHeap([(node.getDistance(),node) for node in G]) # Lager en heap med alle nodene
    while not pq.isEmpty():
        currentVert = pq.delMin()    # velger greedy den med kortest avstand
        for nextVert in currentVert.getConnections():
            newDist = currentVert.getDistance() + currentVert.getWeight(nextVert) #kalkulerer nye avstander
            if newDist < nextVert.getDistance():
                nextVert.setDistance( newDist ) # oppdaterer avstandene
                nextVert.setPred(currentVert) # Oppdaterer foreldrene til den med kortest avstand
                pq.decreaseKey(nextVert,newDist) # lager heapen på nytt så de laveste kommer først.

def bellman_ford(G, s) # G er grafen, med noder og kantvekter. s er startnoden.
    distance = {}
    parent = {}
    for node in G: # Initialiserer startverdier
        distance[node] = float('Inf')
        parent[node] = None
    distance[s]=0 # initialiserer startnoden

    # relax
    for (len(G)-1):
        for u in G:    # fra node u
            for v in G[u]:    # til naboene
                if distance[v] > distance[u] + G[u][v]: # Sjekker om avstanden er mindre
                    distance[v] = distance[u] + G[u][v]    # hvis ja, oppdaterer avstanden
                    parent[v]=u    # og oppdaterer parent

    # sjekk negative sykler
    for u in G:
        for v in G[u]:
            if distance[v] > distance[u] + G[u][v]:
                return False

1 DAG-SHORTEST-PATHS(G, w, s)
2    for each vertex v in G.V
3        v.d = inf  # Distance
4        v.p = null # Parent
5    s.d = 0
6    for each vertex u in G.v, where G.v is topologically sorted
7        for each adjacent vertex v to u
8            if v.d > u.d + w(u, v) # Relax
9                v.d = u.d + w(u, v)
10               v.p = u

All to All

1  G_s = construct_G_with_start_node_s()
2  Bellman_Ford(G_s, s)
3  for node in G.nodes
4      h(node) = G_s.node.distance #distance s to node
5  for edge in G.edges
6      edge.weight = edge.weight + h(edge.parent) - h(edge.child)
7  D = matrix(n, n) #some n*n matrix
8  for node_I in G.nodes
9      Dijkstra(G, node_I) #uses dijkstra to find distances from node "node_I" with updated edge.weights in G
10     for node_J in G.nodes 
11         D[I, J] = node_J.distance + h(edge.child) - h(edge.parent) #add all distances starting in node I to the matrix

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each vertex v
3    dist[v][v] ← 0
4 for each edge (u,v)
5    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j] 
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

def FloydWarshall(W):
    n = len(W)
    D = W
    PI = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if(i==j or W[i][j] == float('inf')):
                PI[i][j] = None
            else:
                PI[i][j] = i

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][j] > D[i][k] + D[k][j]:
                    D[i][j] = D[i][k] + D[k][j]
                    PI[i][j] = PI[k][j]
    return (D,PI)

Flow Network

A flow network is a directed graf where all the edges have a non-negative capacity. Additionally, it is required that if there exists an edge between u and v, there exists no edge in the opposite direction from v to u. A flow network has a source, s, and a sink, t. The source can be seen as the starting node and the sink as the end node. The graph is not divided so for all v there exists a route s ~v~t. All nodes except from s have atleast one inbound edge. All nodes except the source and the sink have a net flow of 0 (all inbound flow = all outbound flow).

A flow network can have several sources and sinks. To eliminate this problem, a super source and super sink are created and linked up to all respective sources and sinks with edges that have infinite capactiy. This new network with only one source and sink is much easier to solve.

Residual Network

The residual network is the capacity left over: $$ c_f(u,v) = c(u,v) - f(u,v)$$

To keep an eye on the residual network is useful. If we send 1000 liters of water from u to v, and 300 liters from v to u, it is enough as sending 700 from u to v to achieve the same result.

Augumenting Path

An augumenting path is a path from the source to the sink that increases the total flow in the network. It can be found by looking at the residual netowrk.

Minimal cut

A cut in a flow network divides the graph in two, S and T. It is useful to look at the flow through this cut:

$$ f(S,T) = \sum_{u \in S}\sum_{v \in T} f(u,v) - \sum_{u \in S}\sum_{v \in T} f(v,u) $$ $$ c(S,T) = \sum_{u \in S}\sum_{v \in T} c(u,v) $$ The number of potential cuts in a network with n nodes is:

$$|C| = 2^{n-2}$$

Of all possible cuts, we want to see the cut with the smallest flow, as this is the bottleneck of the network. Proof exists that show that finding the minimal cut simultaneously gives us the maximum flow through the network.

$$f(S,T)\ =\ c(S,T)$$

Whole Number Theorem

If all capacities in the flow network are whole numbers, then Ford-Fulkerson's method will find a max flow with a whole number value, and the flow between all neighbor nodes will have whole number values.

Concurrency keywords

• Spawn - used to start a parallel thread, allowing tha parent thread to continue with the next line while the child thread runs its subproblem
• Sync - A procedure cannot safely use the values returned by its spawned children until after it executes a sync statement. This keyword indicates that the program must wait until both threads are finished allowing for the correct variables to syncronize
• Serializaion - the serial algorithm that results from deleting the multithreaded keywords: spawn, sync, and parallel.
• Nested parallelism - occurs when the keyword spawn precedes a procedure call. A child thread is spawned to solve the subproblem which in turn runs their own spawn subproblems, potentially creating a vast tree of subcomputations, all excecuting in parallel.
• Logical parallelism - concurrency keywords express logical parallelsism, indicating which parts of the computation may procedd in parallel. At runtime it is upt o a scheduler to determine which subcomputations actually run concurrently.

Performance Measures

Two metrics, work and span.

Work - The work of a multithreaded computation is the total time to execute the entire computatin on one processor. It is the sum of the times taken by each strand. Span - The span is the longest time to execute the strands along any path of the DAG. Again for a DAG in which each strand takes unit time, the span equals the number of vertices on a longest or critical path in the DAG. Given that time to calculate is denoted as $T_p$ where p stands for the number of processors used, span is the running time if we could run each srand on its own processor (or had infinite processors), $T_\infty$. Work Law - $T_P \geq T_1 / P$ Span Law - $T_P \geq T_\infty$ Speedup - $T_1/T_\infty$, says how many times faster the computation is on P processors than on 1 processor.

• Rewriting the work law we get $T_1/T_P \leq P$, stating that the speedup on P processors can at most be P.
• If $T_1/T_P = \theta(P)$ implies linear speed up

• If $T_1/T_P = P$ implies perfect linear speed up

• The ratio $T_1/T_\infty$ of the work to the span gives the parallelism of the multithreaded computation.

Reducibility-relation

To understand the proof technique used to prove a problem is NPC, a few definitions need to be in place. One of these is the reducibility-relation $\leq_P$. In this context it is used to say that a language ($L_1$) is polynomially reducible to another language ($L_2$): $L_1 \leq_p L_2$.

Cormen et al., exemplifies that the linear equation $ax + b = 0$ can be transformed to $0x^2 + ax + b = 0$. All viable solutions for the quadratic equation are also viable solutions for the linear equation. The idea behind the example is to show that a problem, X, can be reduced to problem, Y, so that the input values for X can be solved with Y. If you can reduce X to Y, it implies that to solve Y requires atleast as much as solving X, therefore must Y be as difficult to solve as X. It is worth mentioning that this relation is not mutual, and you therefore cannot use X to solve Y.

Some known NPC problems

Some common examples of NPC problems include:

• Circuit-SAT
• SAT
• 3-CNF-SAT
• Clique-problemet
• Vertex-Cover
• Hamilton-Cycle
• Travelling Salesman (TSP)
• Subset-Sum

But how can we prove a poblem is NPC?

Cormen et al. divides this into two parts:

1. Prove that the problem belongs to the NP-class. Use a certification to prove that the solution is verified in polynomial time.
2. Prove the problem is NP-hard. This is done through polynimial time reduction.

Given $P$ != $NP$, then we can say that a problem is NPC if it is both an NP-problem and an NP-hard-problem.

This connection is illustrated in the figure below:

Given that you are trying to prove that TSP is an NPC-problem:

1. Prove that TSP$\in$ NP. The certification you use can be a sequence of n nodes that you shall visit on your trip. If the sequence just consists of unique nodes (we do not visit the same city more than oce) then we can sum up the costs and verify the total cost is less than a given number k.
2. Prove that TSP is NP-hard. If you have understood what the different problems described above, then you will recognize that TSP is a Hamilton Cycle-problem (given an undireted graph G, there exists a cucle that contains all the nodes only once, and where the starting node = the end node). We know that TSP is atleast as difficult to solve as a the Ham-cycle problem (as Ham-cycle is a subproblem of TSP). Given that we already have proved that the Ham-cycle problem is NP-hard, we can show with polynomial time reduction that TSP is also NP-hard (since we reduce Ham-cycle to TSP in polynimial time, then TSP is NP-H)

$HAM-CYCLE \leq_P TSP$.

As most people now believe that $P$ != $NP$, then it follows that NP-H problems cannot be solved in polynomial time, and neither NP-problems. Disproving this, implying that $P$ != $NP$ or that $P$ = $NP$, then you have claim to a rather large sum of money.