Algowiki - User contributions [en]

Ford-Fulkerson

2015-01-22T15:48:25Z

Pezi22: /* Pseudocode */

Hopcroft-Tarjan

2014-11-11T19:00:49Z

Pezi22: cat

[[Category:Graph Algorithms]]
== Abstract view ==

'''Algorithmic problem:'''
[[Biconnected components]]

'''Type of algorithm:'''
two steps.

== Step 1 ==

'''Abstract view:'''
# A start node <math>s</math> and an edge <math>\{s,v\}</math> to an arbitrarily chosen node <math>v\in V</math> are added to <math>G</math>.
# The core algorithm is a variation of [[Depth-first search|DFS]], where for each node <math>v\in v</math> two additional nonnegative integral numbers are computed:
## The '''depth''' of <math>v</math> in the arborescence created by the DFS procedure.
## The '''lowpoint''', that is, the minimal depth of any node <math>w\in V</math> such that <math>(u,w)\in A</math> for some immediate or non-immediate successor of <math>v</math> in the DFS tree.
# The start node <math>s</math> and the edge <math>\{s,v\}</math> are removed from <math>G</math> and from the DFS arborescence (which is rooted at <matH>v</math> afterwards).

'''Implementation of step 2:'''
# ''Depth'': The DFS maintains a global integral number, the '''current depth'''. Whenever a node is seen for the first time, its depth attribute is set identical to the current depth. In each forward step, the current depth is ''in''creased by one, in each backward step, it is ''de''creased by one.
# ''Lowpoint'':
## Whenever a node <math>v\in V</math> is seen for the first time, its lowpoint is set identical to its depth.
## Whenever an arc <math>(v,w)</math> is examined such that <math>w</math> has already been seen and the depth of <math>w</math> is smaller than the lowpoint of <math>v</math>, the lowpoint of <math>w</math> is set identical to the depth of <math>w</math>.
## In each backward step of DFS from a node <math>w</math> back to its immediate predecessor <math>v</math>: If the lowpoint value of <math>w</math> is smaller than the lowpoint value of <math>v</math>, the lowpoint value of <math>v</math> is set identical to the lowpoint value of <math>w</math>.

'''Remarks:'''
# We do not choose a start node from the given nodes but insert a new start node to avoid a special treatment of the start node.
# This is another example where it makes perfect sense to implement graph traversal algorithms as iterators (cf. [[Graph traversal#Remarks|here]]). In fact, then the operations on the depth and lowpoint attributes can be inserted in the DFS loop in an easy, obvious way.

== Step 2 ==

'''Definition:'''
A node <math>v\in V</math> is '''essential''' if, for at least one arc <math>(v,w)</math> in the arborescence from step 1, the lowpoint value of <math>w</math> is equal to or larger than the depth of <math>v</math>.

'''Abstract view:'''
A repeated application of [[Depth-first search|DFS]], where the start nodes of the individual DFS runs are the essential nodes. In that, the essential nodes are considered in ascending order of their finishing times as computed in step 1. The nodes hit in one DFS run are removed from <math>G</math> before the next DFS run commences. The node sets visited in the individual DFS runs are returned as the biconnected components.

== Correctness ==

Obviously, the depth and the lowpoint are set correctly according to their intended semantics.

First consider an essential node <math>v\in V</math>. Let <math>(v,w)</math> be an arc in the arborescence such that the lowpoint value of <math>w</math> is equal to or larger than the depth of <math>v</math>. We have to show that the subarborescence rooted at <math>(v,w)</math> is connected to the rest of the graph via <math>v</math> only. So suppose for a contradiction that there is an edge <math>\{x,y\}</math> such that <math>x</math> belongs to that subarborescence and <math>y</math> does not. Then <math>y</math> must have been seen before <math>x</math>, because otherwise, <math>y</math> would be in the subarborescence rooted at <math>x</math>. Since the lowpoint of <math>x</math> is equal to or larger than the depth of <math>v</math>, <math>y</math> cannot be a predecessor of <math>v</math> in the arborescence. Hence, <math>y</math> was even finished before <math>v</math> was seen. In particular, <math>y</math> was finished before <math>x</math> was seen, which is impossible.

Now consider a node <math>v\in V</math> that is ''not'' essential. Opposite to the first case, we have to show that the subarborescence rooted at an arc <math>(v,w)</math> is not only connected to the rest of the graph via <math>v</math>. However, this follows immediately from the definition of the lowpoint value: There is some <math>x\in V</math> in the subarborescence rooted at <math>(v,w)</math> connected to some node <math>y</math> that cannot be in the subarborescence due to its smaller depth.

== Complexity ==

'''Statement:'''
The asymptotic complexity is linear.

'''Proof:'''
Follows immediately from the linear asymptotic complexity of DFS.

Kosaraju

2014-11-11T19:00:09Z

Pezi22: category

[[Category:Graph Algorithms]]

== General information ==

'''Algorithmic problem:''' [[Strongly connected components]]

'''Type of algorithm:''' loop

== Abstract View ==

# Apply a [[repeated depth-first search]] to <math>G</math>, the output order is parenthetical.
# Invert the output order of the nodes.
# Let <math>G^t=(V,A^t)</math> be the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G=(V,A)</math>.
# Apply a [[repeated depth-first search]] to <math>G^t</math> with a modification: The order in which the nodes are considered as potential start nodes is the inverted parenthetical order from step 2.
# The node sets from the individual applications of [[Depth-first search|DFS]] inside step 4 are exactly the SCC of <math>G</math>.

== Correctness ==

First note that the transposition of all arcs does not change the SCC of a graph, so step 4 indeed processes the SCC of <math>G</math>.
[[File:CondensedGraphKosaraju.jpg|200px|thumb|right|Construction of the condensed graph (example)]]
Consider the condensed graph <math>G'</math> whose nodes are these SCC, and there is an arc from an SCC <math>C_i</math> to an SCC <math>C_j</math> in <math>G'</math> if, and only if, there is at least one arc in <math>G</math> from some node in <math>C_i</math> to some node in <math>C_j</math>. This condensed graph is acyclic because all nodes in all SCC on a cycle would be mutually reachable from each other in <math>G</math> and their union would consequently form a single larger SCC contradicting the construction of the condensed graph.

In step 1, each [[Depth-first search|DFS]] run either meets ''all'' nodes of an SCC of <math>G</math> or ''none'' of the nodes of this SCC. More specifically, all nodes in the same SCC as the start node and in all SCC reachable from that SCC, except for the SCC processed in previous [[Depth-first search|DFS]] runs.

It is easy to see that all nodes of an SCC are finished consecutively (because of the parenthetical order); that is, all nodes of an SCC form a connected subsequence in the output sequence of step 1. In particular, it does not matter in step 4 which node of an SCC is chosen as a start node for a [[Depth-first search|DFS]] run. If an SCC <math>C_i</math> is reachable from an SCC <math>C_j</math> in <math>G</math>, then the nodes of <math>C_i</math> appear before the nodes of <math>C_j</math> in parenthetical order. Equivalently, the nodes of <math>C_i</math> appear ''after'' the nodes of <math>C_j</math> in the reverse order on which step 4 is based.

Let <math>C_i</math> and <math>C_j</math> be two SCC of <math>G</math>. Since each SCC is processed exhaustively or not at all in a [[Depth-first search|DFS]] run, it suffices to show that <math>C_i</math> and <math>C_j</math> are not processed within the same run of step 4. Suppose for a contradiction that <math>C_i</math> and <math>C_j</math> are processed in the same [[Depth-first search|DFS]] run in step 4 (not necessarily in the same run in step 1). Let <math>C_k</math> be the SCC to which the start node of that run belongs (possibly <math>k=i</math> or <math>k=j</math>). Without loss of generality, suppose <math>k\neq i</math>. Then <math>C_i</math> is reachable from <math>C_k</math> in <math>G'</math>; in other words, <math>C_k</math> is reachable from <math>C_i</math> in <math>G</math>. However, then the nodes of <math>C_i</math> have higher finishing times than the nodes of <math>C_k</math>, so some node of <math>C_i</math> had been chosen as a start node before any node of <math>C_k</math>.

== Complexity ==

'''Statement:''' The asymptotic complexity is in <math>\Theta(|V|+|A|)</math>.

'''Proof:''' Follows immediately from the linear asymptotic complexity of [[Repeated depth-first search|repeated DFS]].

== Pseudocode ==

<code>
STRONGLY-CONNECTED-COMPONENTS(''D'')
1 call '''DFS'''(''D'') to compute finishing times ''f''[v] for each vertex ''v'' ∈ ''V''
2 compute ''D''''T'' (w.r.t. step 3)
3 call '''DFS'''(''D''''T''), but in the main loop of '''DFS''', consider the vertices in order of decreasing ''f''[v] as computed in step 1
4 output the vertices of each tree in the '''DFS''' forest of step 3 as a separate strongly connected component
</code>

Main Page

2014-11-11T18:54:07Z

Pezi22: /* ??? */

== News ==
* The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 13th October.
* The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/
* <math>LaTeX</math> [http://www.mediawiki.org/wiki/Manual:Math available now!]
* ToDo List added
* Every content has to be in English!
* [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi Syntaxhighlight]

== Rules ==
* Add finalized reconstructions of the old Wiki to Category:Checkup.
* Don't any non-Weihe content until the reconstructions isn't finished.
* Keep your active reconstructing Pages in "Division of labor" section up to date!

'''Look here for short/uncomplete Pages''' [[Special:ShortPages]]

== Page Status ==
Final: [[:Category:Checkup]]

== To Do ==
=== Notations ===
* [[Big O notation]]
* [[L' Hospital]]
* [[Master theorem]]

=== Problems ===
* [[Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]] (DONE)
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]]
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]] (DONE)
*** [[Insert an element in a sequence]] (Empty in old wiki?!)
*** [[Median]] (DONE)
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]] (DONE)
*** [[Sorting Sequences of Strings]] (DONE)

=== Coding Basics ===
* [[Inheritance]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

=== String Matching Algorithms ===
* [[Simple string matching algorithm]] (DONE)
* [[String matching based on finite automaton]] (DONE)

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion sort]]
* [[Quicksort]]
* [[Bubblesort]]
* [[Mergesort]]
* [[Bucketsort]]
* [[Selection sort]]
* [[Bogosort]]

=== Search Algorithms ===
* [[Binary search]]

=== Auxillary Algorithms ===
* [[Pivot partitioning by scanning]]

=== Manipulation ===
* [[Array list: find]]
* [[Array list: find at position]]
* [[Array list: insert at head]]
* [[Array list: insert at position]]
* [[Array list: number]]
* [[Array list: remove]]
* [[Doubly-linked list: insert at position]]
* [[Doubly-linked list: insert at tail]]
* [[Doubly-linked list: remove]]
* [[Find element in sequence iteratively]]
* [[Find element in sequence recursively]]
* [[Hashtable: find]]
* [[Hashtable: insert]]

=== Tree Algorithms ===
* [[Depth-first search]]
* [[Breadth-first search]]
* [[B-tree: find]]
* [[B-tree: minimum]]
* [[B-tree: maximum]]
* [[B-tree: insert]]
* [[B-tree: insert and rearrange]]
* [[B-tree: merge two siblings]]
* [[B-tree: remove]]
* [[B-tree: shift key to sibling]]
* [[B-tree: rotate]]
* [[B-tree: merge]]
* [[B-tree: split]]
* [[Binary search tree: find]]
* [[Binary search tree: minimum]]
* [[Binary search tree: maximum]]
* [[Binary search tree: insert]]
* [[Binary search tree: remove]]
* [[Binary search tree: remove node]]
* [[Binary search tree: traverse]]

=== Graph Theory ===
* [[Directed graph]]
* [[Bipartite graph|Bipartite graph]] (DONE)
* [[k-partite graph]]
* [[Negative paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]] (DONE)
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]
* [[Union-find with disjoint trees: find]]
* [[Union-find with lists: unite]]
* [[Max-flow min-cut]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Abstract Data Structures ===
*[[Network Structures]]
**[[Graph]]
**[[Tree]]
*[[Sequence]]
**[[Sorted sequence]]
**[[Bounded priority queue]]
**[[Linear sequence]]
**[[Priority queue]]
**[[Sorted sequence]]
=== Implementations of Abstract Data Structures ===
* [[Linked list]]
* [[Array list]]
* [[Binary search tree]]
* [[Doubly-linked list]]
* [[Heap as array]] (DONE (Heap as Array))
* [[Hashtable]]
* [[Multi-way search tree]]
* [[Red-black tree]]
* [[B-tree]]

=== ??? ===
* [[Min-Max Heaps]]
* [[First In - First Out]]
* [[First In - Last Out]]
* [[Directed Tree]]
* [[Decision Tree]]

=== Other ===
* [[Model computer]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Euclid]]
* [[Gauss]]
* [[Discrete fourier transform]]
* [[Fast fourier transform]]
* [[Bresenham]]
* [[Round robin]]
* [[Seperate and conquer]]
* [[Message-Digest algorithm]]
* [[Secure hash algorithm]]
* [[Sequent calculus]]
* [[Resolution calculus]]
* [[Cocke-Younger-Kasami algorithm]]
* [[Distance vector routing]]
* [[Link state routing]]
* [[Z Buffer algorithm]]
* [[Marching squares]]
* [[Marching cubes]]
* [[Bottom-Up heapsort]]
* [[Radixsort]]
* [[Median cut]]
* [[Pancake sorting]]
* [[Karnaugh-Veitch diagramm]]
* [[Delanuay triangulation]]
* [[Backtracking]]
* [[Alpha–beta pruning]]
* [[Beam search]]
* [[Best-first search]]
* [[Bidirectional search]]
* [[Borůvka's algorithm]]
* [[Branch and bound]]
* [[D*]]
* [[Depth-limited search]]
* [[Edmonds' algorithm]]
* [[Fringe search]]
* [[Hill climbing]]
* [[IDA*]]
* [[Iterative deepening depth-first search]]
* [[Jump point search]]
* [[Lexicographic breadth-first search]]
* [[SMA*]]
* [[Uniform-cost search]]

=== Other Data Structures (LOCKED) ===
* [[Adelson-Velskii and Landis' tree]]
* [[Patricia-Trie]]
* [[Suffix Tree]]
* [[Huffmann Tree]]
* [[Binary Expression Tree]]
* [[Hash Set]]
* [[Incidence Matrix]]
* [[Voronoi Diagramm]]
* [[Quad Tree]]
* [[Oct Tree]]
* [[kd Tree]]
* [[Binary space partitioning]]

Classical eulerian cycle algorithm

2014-11-11T18:50:02Z

Pezi22:

[[File:Nikolaus.png|400px|thumb|right|Another may well know example with 44 solutions]]

== General information ==

'''Algorithmic problem:''' [[Eulerian cycle]]

''' Type of algorithm:''' recursion with an arbitrarily chosen start node <math>s\in V</math> as an additional input. Before the proper recursive procedure is invoked, the output sequence <math>S</math> is initialized so as to contain the start node <math>s</math> and nothing else.

'''Break condition:''' No edges/arcs leave the start node <math>s</math> of that recursive call.

== Induction basis ==

'''Abstract view:''' Nothing to do.

== Induction step ==

For notational convenience, both undirected edges and directed arcs are denoted by parentheses in the following (in the direction in which they are looked at).

# Let <math>p</math> be a (dynamically growing) path, represented in <math>p</math> as an alternating sequence of nodes and edges/arcs.
# Initialize <math>p</math> so as to contain <math>s</math> and nothing else.
# Set <math>x:=s</math>.
# While there are edges/arcs leaving <math>x</math>:
## Choose one such arc <math>(x,y)</math>.
## Remove <math>(x,y)</math> from the graph.
## Append <math>(x,y)</math> and then <math>y</math> to <math>p</math>.
## Set <math>x:=y</math>.
# If <math>x\neq s</math>, terminate the algorithm with the statement that no eulerian cycle exists.
# Otherwise: For each node <math>v</math> on <math>p</math> that still has leaving edges/arcs,:
## Call the procedure recursively with <math>v</math> as the start node, giving path <math>p'</math>.
## Replace <math>v</math> in <math>p</math> by <math>p'</math>.

== Correctness ==

Since each edge/arc is removed immediately when it is processed, no edge/arc occurs twice in the output. Obviously, steps 4.3 and 6.2 ensure that the order in which the nodes and edges/arcs occur in the output yields a correct path. Obviously, whenever step 4 is finished, it is <math>x=s</math> and the remaining graph is eulerian, if the original graph was eulerian. Consequently, the statement that no eulerian cycle exists is only delivered if the graph is indeed non-eulerian. Moreover, the graph handed over to a recursive call is Eulerian, if the original graph was Eulerian.

Suppose for a contradiction that some edge/arc <math>e/a</math> is '''not''' in the output. Since the graph is (strongly) connected, there is a path <math>q</math> from the start node to the tail of <math>e/a</math> (an arbitrary endnode of <math>e/a</math> in the undirected case). Let <math>v</math> be the last node on <math>q</math> processed by any recursive call. Then the subsequent edge/arc on <math>q</math> has not been processed, which contradicts the procedure.

== Complexity ==

'''Statement:'''
Both for directed and undirected graphs, the asymtptotic complexity is linear in the number of edges/ars.

'''Proof:'''
We assume that all data structures are implemented in the obvious appropriate way. First note that steps 1, 2, 3, and 5 take constant time each. So the total complexity of these steps is linear in the number of recursive calls, which is linear in the number of edges/arcs in turn. The total number of iterations of steps 4 and 6, respectively, taken over all recursive calls, is linear in the number of edges/arcs as well.

'''Remarks:'''
# Since the graph is (strongly) connected, the number of nodes is asymptotically dominated by the number of edges/arcs and, therefore, irrelevant here.
# Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it must be hidden from the algorithm up to its termination to achieve the linear bound on the complexity. A boolean edge/arc label to indicate whether this edge/arc has already been processed, does not suffice.

== Example ==
<gallery>
File:Eulerpath_1.png|Step 1
File:Eulerpath_2.png|Step 2
File:Eulerpath_3.png|Step 3
File:Eulerpath_4.png|Step 4
File:Eulerpath_5.png|Step 5
File:Eulerpath_6.png|Step 6
File:Eulerpath_7.png|Step 7
File:Eulerpath_8.png|Step 8
File:Eulerpath_9.png|Step 9
File:Eulerpath_10.png|Step 10
File:Eulerpath_11.png|Final Step
</gallery>

Main Page

2014-11-11T18:37:37Z

Pezi22: /* Other Algorithms (LOCKED) */ euclid instead of eulcid

== News ==
* The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 13th October.
* The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/
* <math>LaTeX</math> [http://www.mediawiki.org/wiki/Manual:Math available now!]
* ToDo List added
* Every content has to be in English!
* [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi Syntaxhighlight]

== Rules ==
* Add finalized reconstructions of the old Wiki to Category:Checkup.
* Don't any non-Weihe content until the reconstructions isn't finished.
* Keep your active reconstructing Pages in "Division of labor" section up to date!

'''Look here for short/uncomplete Pages''' [[Special:ShortPages]]

== Page Status ==
Final: [[:Category:Checkup]]

== To Do ==
=== Notations ===
* [[Big O notation]]
* [[L' Hospital]]
* [[Master theorem]]

=== Problems ===
* [[Maximum matching problem]]
* [[Max-Flow Problems]]
* [[Min-Cost Flow Problems]]
* [[Shortest Paths Problems]]
** [[All pairs shortest paths]]
*** [[Floyd-Warshall]]
*** [[Bellman-Ford]] (DONE)
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)
** [[Single source shortest paths]]
*** [[Dijkstra]]
** [[Single source single target shortest paths]]
*** [[A*]]
* [[Maximum spanning forest]]
* [[Problems on Sequences]]
** [[Basic Problems on Sequences]]
*** [[Find an element in a sequence]] (DONE)
*** [[Insert an element in a sequence]] (Empty in old wiki?!)
*** [[Median]] (DONE)
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]] (DONE)
*** [[Sorting Sequences of Strings]] (DONE)

=== Coding Basics ===
* [[Inheritance]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

=== String Matching Algorithms ===
* [[Simple string matching algorithm]] (DONE)
* [[String matching based on finite automaton]] (DONE)

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion sort]]
* [[Quicksort]]
* [[Bubblesort]]
* [[Mergesort]]
* [[Bucketsort]]
* [[Selection sort]]
* [[Bogosort]]

=== Search Algorithms ===
* [[Binary search]]

=== Auxillary Algorithms ===
* [[Pivot partitioning by scanning]]

=== Manipulation ===
* [[Array list: find]]
* [[Array list: find at position]]
* [[Array list: insert at head]]
* [[Array list: insert at position]]
* [[Array list: number]]
* [[Array list: remove]]
* [[Doubly-linked list: insert at position]]
* [[Doubly-linked list: insert at tail]]
* [[Doubly-linked list: remove]]
* [[Find element in sequence iteratively]]
* [[Find element in sequence recursively]]
* [[Hashtable: find]]
* [[Hashtable: insert]]

=== Tree Algorithms ===
* [[Depth-first search]]
* [[Breadth-first search]]
* [[B-tree: find]]
* [[B-tree: minimum]]
* [[B-tree: maximum]]
* [[B-tree: insert]]
* [[B-tree: insert and rearrange]]
* [[B-tree: merge two siblings]]
* [[B-tree: remove]]
* [[B-tree: shift key to sibling]]
* [[B-tree: rotate]]
* [[B-tree: merge]]
* [[B-tree: split]]
* [[Binary search tree: find]]
* [[Binary search tree: minimum]]
* [[Binary search tree: maximum]]
* [[Binary search tree: insert]]
* [[Binary search tree: remove]]
* [[Binary search tree: remove node]]
* [[Binary search tree: traverse]]

=== Graph Theory ===
* [[Directed graph]]
* [[Bipartite graph|Bipartite graph]] (DONE)
* [[k-partite graph]]
* [[Negative paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]] (DONE)
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]
* [[Union-find with disjoint trees: find]]
* [[Union-find with lists: unite]]
* [[Max-flow min-cut]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Abstract Data Structures ===
*[[Network Structures]]
**[[Graph]]
**[[Tree]]
*[[Sequence]]
**[[Sorted sequence]]
**[[Bounded priority queue]]
**[[Linear sequence]]
**[[Priority queue]]
**[[Sorted sequence]]
=== Implementations of Abstract Data Structures ===
* [[Linked list]]
* [[Array list]]
* [[Binary search tree]]
* [[Doubly-linked list]]
* [[Heap as array]] (DONE (Heap as Array))
* [[Hashtable]]
* [[Multi-way search tree]]
* [[Red-black tree]]
* [[B-tree]]

=== ??? ===
* [[Min-Max Heaps]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Directed Tree]]
* [[Decision Tree]]

=== Other ===
* [[Model computer]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Euclid]]
* [[Gauss]]
* [[Discrete fourier transform]]
* [[Fast fourier transform]]
* [[Bresenham]]
* [[Round robin]]
* [[Seperate and conquer]]
* [[Message-Digest algorithm]]
* [[Secure hash algorithm]]
* [[Sequent calculus]]
* [[Resolution calculus]]
* [[Cocke-Younger-Kasami algorithm]]
* [[Distance vector routing]]
* [[Link state routing]]
* [[Z Buffer algorithm]]
* [[Marching squares]]
* [[Marching cubes]]
* [[Bottom-Up heapsort]]
* [[Radixsort]]
* [[Median cut]]
* [[Pancake sorting]]
* [[Karnaugh-Veitch diagramm]]
* [[Delanuay triangulation]]
* [[Backtracking]]
* [[Alpha–beta pruning]]
* [[Beam search]]
* [[Best-first search]]
* [[Bidirectional search]]
* [[Borůvka's algorithm]]
* [[Branch and bound]]
* [[D*]]
* [[Depth-limited search]]
* [[Edmonds' algorithm]]
* [[Fringe search]]
* [[Hill climbing]]
* [[IDA*]]
* [[Iterative deepening depth-first search]]
* [[Jump point search]]
* [[Lexicographic breadth-first search]]
* [[SMA*]]
* [[Uniform-cost search]]

=== Other Data Structures (LOCKED) ===
* [[Adelson-Velskii and Landis' tree]]
* [[Patricia-Trie]]
* [[Suffix Tree]]
* [[Huffmann Tree]]
* [[Binary Expression Tree]]
* [[Hash Set]]
* [[Incidence Matrix]]
* [[Voronoi Diagramm]]
* [[Quad Tree]]
* [[Oct Tree]]
* [[kd Tree]]
* [[Binary space partitioning]]

Binary search

2014-11-11T12:19:55Z

Pezi22: new

== Binary search ==
'''Algorithmic problem:''' [[Sorted sequence: find]]

'''Prerequisites:''' The linear sequence S(length n) must be well-ordered and sorted by the same key

'''Type of algorithm:''' loop

'''Auxiliary data:''' A pointer <math>p</math> of type "pointer to list item of array lists of component type <math>\Kappa</math>".

== Abstract view ==

'''Invariant:''' After <math>i \ge 0</math> iterations:
# The pointer <math>p</math> points to the sequence at position <math>k_i</math>
#The key <math>\Kappa </math> is in the range of <math>[k_i-n/2^i, k_i +n/2^i]</math>

'''Variant:''' The pointer <math>p</math> is moved so the sequence item at the position (rounded) <math>(k_i+k_{i-1})/2</math> with <math>k_0=0 if S[n/2]<\Kappa,k_0=n if S[n/2]>\Kappa </math>

'''Break condition:''' Either <math>S[k_i]=\Kappa</math> or, otherwise, <math>k_i=k_{i+1} with S[k_i]\neq \Kappa</math>.

== Induction basis ==

'''Abstract view:''' Set <math>p:=</math> n/2.

'''Implementation:''' Obvious.

'''Proof:''' Nothing to show.

== Induction step ==

'''Abstract view:'''
If p points to a node but not with key K, p descends in the appropriate direction, left or right.
'''Implementation:'''

#If <math>p.key = K</math>, terminate the algorithm and return '''''true'''''.
# Otherwise:
## If <math>K < p.key</math>, set <math>p </math> to the sequence element <math>k_{i+1}=k_i-n/2^i</math>.
## If <math>K > p.key</math>, set <math>p </math>to the sequence element <math>k_{i+1}=k_i-n/2^i</math>.

'''Correctnes:''' Obvious.

== Complexity ==

'''Statement:''' Log(n)

'''Proff:''' Obvious.

Array list: find

2014-11-10T11:56:24Z

Pezi22:

'''Algorithmic problem:''' [[Linear sequence: find]]

'''Prerequisites:''' None.

'''Type of algorithm:''' loop

'''Auxiliary data:''' A pointer <math>p</math> of type "pointer to list item of array lists of component type <math>\Kappa</math>".

== Abstract view ==

'''Invariant:''' After <math>i \ge 0</math> iterations:
# The pointer <math>p</math> points to the list item at position <math>i + 1</math> (or is void if no such item exists).
# The first <math>i</math> arrays in the list do not contain <math>\Kappa</math>.

'''Variant:''' The pointer <math>p</math> is moved one step forward to the next array list item.

'''Break condition:''' Either <math>p=</math>void or, otherwise, <math>\Kappa \in \{p.A[1], \ldots, p.A[p.n]\}</math>.

== Induction basis ==

'''Abstract view:''' Set <math>p:=</math> first.

'''Implementation:''' Obvious.

'''Proof:''' Nothing to show.

== Induction step ==

'''Abstract view:'''
# Terminate the algorithm if the end of the list is reached or, otherwise, if <math>\Kappa</math> is found in the current array.
# Otherwise, <math>p</math> is moved one step forward to the next array.

'''Implementation:'''
# If <math>p=</math>void, terminate the algorithm and return <math>false</math>.
# Otherwise, if <math>p.A[j] = \Kappa</math> for some <math>j \in \{1, \ldots, p.n\}</math>, set <math>p:=p.next</math>.

'''Correctness:''' Obvious.

== Complexity ==

'''Statement:''' Linear in the length of the sequence in the worst case.

'''Proff:''' Obvious.

L' Hospital

2014-10-29T22:43:33Z

Pezi22: Created page with "A central rule for the determination of the limit of series is the rule of L'Hospital. After several forming steps it might be that the rest of your sequels or functions can b..."

A central rule for the determination of the limit of series is the rule of L'Hospital. After several forming steps it might be that the rest of your sequels or functions can be represented as a fraction, e.g. <math>\lim_{x\rightarrow 0}\frac{sin(x)}{x}</math>. It is known that devisions with zero are forbidden or not definied.

The '''rule of L'Hospital''' allows us to determine the limit value of a term <math>\lim_{x\rightarrow x_0} \dfrac{ f(x)}{g(x)}</math>, where <math>f(x)</math> and <math>g(x)</math> are sequels(or functions), either both have the limit zero or infintity.

Normally, it is not solvable what the limit of the fraction is, because in math limits of <math>\frac{0}{0} </math> and <math>\frac{\infty}{\infty}</math> are not defined.
The rule of L'Hospital says, that you can replace the functions with their derivative. So basicly in formula:
<math>\lim_{x\rightarrow x_0} \dfrac{ f(x)}{g(x)} \overset{l'H}{=} \lim_{x\rightarrow x_0} \dfrac{ f'(x)}{g'(x)}</math>,
if and only if <math>f</math> and <math>g</math> are derivable and have the same limit if <math>x</math> goes to <math>x_0</math>.

''Remark 1:'' Don't try to make a derivative of the whole fraction!

''Remark 2:'' If it is neccessary and the functions are continous derivable enough you can reapply L'Hospital until the fraction has a known limit (you have to check on every step if the single limits are equal!).

Edmonds-Karp

2014-10-29T11:58:19Z

Pezi22: fleasible->feasible

== General Information ==

'''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problems (standard version)]]

'''Algorithm :''' This is a specialization of [[Ford-Fulkerson]]: Among all flow-augmenting <math>(s,t)</math>-paths, always choose one with smallest number of arcs.

== Abstract View ==

'''Invariant:'''
After <math>i \ge 0</math> iterations:
# The flow <math>f</math> is a feasible flow.
# If all upper bounds are integral, <math>f</math> is integral as well.

'''Notation:'''
For an <math>(s,t)</math>-flow, let <math>A_f</math> denote the set of all arcs that belong to at least one flow-augmenting <math>(s,t)</math>-path with smallest number of arcs.

'''Variant:'''
# The smallest number of arcs on a flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously.
# Whenever that number does ''not'' decrease in an iteration, the size of <math>A_f</math> decreases.

'''Break condition:''' There is no flow-augumenting path.

== Correctness ==

See [[Ford-Fulkerson#Correctness|Ford-Fulkerson]].

== Complexity ==

'''Statement:'''
Even if the upper bounds are not integral, the asymptotic complexity is in <math>\mathcal{O}(nm^2)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.

'''Proof:'''
If the variant is fulfilled, the smallest number of arcs on a flow-augmenting path strictly increases after at most <math>m</math> iterations. This number is positive, but cannot be larger than <math>n-1</math>. Hence, the total number of iterations is in <math>\mathcal{O}(nm)</math>. The claim then follows from the fact that the complexity of an iteration is linear in the number of arcs. Therefore, it suffices to show that the variant is fulfilled.

Let <math>p</math> be the flow-augmenting path in the current iteration, and let <math>k</math> be the number of arcs on <math>p</math>; in other words, the minimum number of arcs of a flow-augmenting <math>(s,t)</math>-path with respect to the current flow. At least one arc of <math>p</math> is being saturated in this iteration and, thus, not on any flow-augmenting path anymore. Therefore, it remains to show that augmenting the flow along <math>p</math> according to [[Ford-Fulkerson]] does not create new flow-augmenting paths of length <math>k</math> or less than <math>k</math>.

A new flow-augmenting <math>(s,t)</math>-path can only be created by an arc of <math>p</math> that fulfills one of the following two conditions immediately before the current iteration:
# A forward arc <math>(v,w)\in A</math> of <math>p</math> with <math>f(v,w)=0</math>.
# A backward arc <math>(w,v)\in A</math> of <math>p</math> with <math>f(w,v)=u(w,v)</math>.

Suppose a new flow-augmenting path <math>p'</math> has been created. We have to show that <math>p'</math> has more than <math>k</math> arcs. Note that <math>p'</math> contains <math>r\geq 1</math> arcs that fall into one of the two cases above. For notational convenience (to get rid of that case distinction), we assume without loss of generality that all of these arcs are backward arcs; the treatment of forward arcs is perfectly analogous. So let <math>(w_1,v_1),\ldots,(w_r,v_r)</math> denote these arcs, in the order in which they appear on <math>p'</math> (not necessarily the order in which they appear on <math>p</math>). For notational convenience, let <math>v_0:=s</math> and <math>w_{r+1}:=t</math>.

For <math>i\in\{0,\ldots,r\}</math>, let <math>p_i</math> denote the subpath of <math>p'</math> from <math>v_i</math> to <math>w_{i+1}</math>. Now, for all paths <math>p_i</math> such that <math>v_{i+1}</math> appears after <math>w_i</math> on <math>p</math>, the specific choice of <math>p</math> to have a minimum number of arcs implies that <math>p_i</math> does not have fewer arcs than the subpath of <math>p</math> from <math>w_i</math> to <math>v_{i+1}</math>. For the other subpaths <math>p_i</math>, it suffices to note the trivial fact that the number of arcs on <math>p_i</math> is not negative. So, summing up the numbers of arcs on all <math>p_i</math> and adding the number <math>r</math> of arcs <math>(w_i,v_i)</math> to get the number of arcs on <math>p'</math> proves the claim.

Ford-Fulkerson

2014-10-29T11:57:39Z

Pezi22: aus fleasible das erste l für die Rechtschreibung gelöscht

== General information ==

'''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problems (standard version)]] 

'''Type of algorithm:''' loop 

== Abstract view ==

'''Invariant:'''
After <math>i \ge 0</math> iterations:
# The flow <math>f</math> is a feasible flow.
# If all upper bounds are integral, <math>f</math> is integral as well.

'''Variant:''' The value of <math>f</math> increases.

'''Break condition:''' There is no flow-augumenting path.

== Induction basis ==
'''Abstract view:''' We start with some feasible flow, for example, the zero flow.

'''Implementation:''' Obvious.

'''Proof:''' Obvious.

== Induction step ==
'''Abstract view:''' Find a [[Basic flow definitions#Flow-augmenting path|flow-augmenting path]] and increase <math>f</math> along this path by the maximal value such that the flow value of each <math>a\in A</math> remains in the interval <math>[0,...,u(a)]</math>. 

'''Implementation:'''
# Apply a [[Graph traversal|graph traversal]] algorithm from <math>s</math> as follows:
## If <math>f(v,w)<c(v,w)</math>, <math>(v,w)\in A</math> can be used for going forward in the direction <math>v \rightarrow w</math>;
## If <math>f(v,w)>0</math>, <math>(v,w)\in A</math> can be used for going forward in the direction <math> w\rightarrow v</math>; .
# Terminate this graph traversal once either <math>t</math> is seen or all reachable nodes were seen (whatever occurs first).
# In the latter case, the break condition applies and the loop is terminated.
# Otherwise,
## Let <math>p</math> denote the current path of the traversal (which is an <math>(s,t)</math>-path in this case).
## Let <math>x</math> denote the minimum of the values <math>c(a)-f(a)</math> on all forward arcs of <math>p</math>.
## Let <math>y</math> denote the minimum of the values <math>f(a)</math> on all backward arcs of <math>p</math>.
## For each arc <math>a \in A</math> on <math>p</math>, increase the flow value by <math>\min \{x,y \}</math> if <math>a</math> is a forward arc on <math>p</math>, otherwise, decrease the flow value by <math>\min \{x,y \}</math>.

'''Proof:''' If the graph traversal does not hit <math>t</math>, the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit <math>t</math>. Then <math>p</math> is an <math>(s,t)</math>-path. By definition of <math>x</math> and <math>y</math>, the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes of <math>p</math> are relevant. Let <math>v</math> be such an internal node, and let <math>u</math> and <math>w</math> denote the immediate predecessor and successor of <math>v</math> on <math>p</math>, respectively. Basically, there are four cases:
*Either <math>(u,v)</math> is on <math>p</math> as a forward arc or <math>(v,u)</math> is on <math>p</math> as a backward arc.
*Either <math>(v,w)</math> is on <math>p</math> as a forward arc or <math>(w,v)</math> is on <math>p</math> as a backward arc.
It is easy to check preservation of the flow conservation conditions for each of these four cases.

== Correctness ==

Due to the invariant, the flow is feasible before and after each iteration. Termination results from the complexity considerations below. Due to the [[Max-flow min-cut|max-flow min-cut theorem]], the break condition implies that the final flow is maximum.

== Complexity ==

'''Statement:''' If all capacity values are integral, the asymptotic worst-case complexity is <math>\mathcal{O} (m\cdot F)</math>, where <math>m = |A|</math> and <math>F</math> is the maximum total flow value.

'''Proof:''' A graph search from <math>s</math> requires <math>\Omicron (m)</math> . Obviously, determining <math>x</math> and <math>y</math> and changing the flow values along <math>p</math> requires <math>\mathcal{O}(m)</math> as well.
It is also evident that, before and after each iteration, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval <math>[0...F]</math>, this may happen at most <math>F</math> times.

== Pseudocode ==
<code>
FORD-FULKERSON(''G,s,t'')
1 '''for''' each edge (''u,v'') ∈ ''G.E''
2 (''u,v'').''f'' = 0
3 '''while''' there exists a path ''p'' from ''s'' to ''t'' in the residual Network Gf''
4 ''cf''(''p'') = min{''cf''(''u,v'') : (''u,v'') is in ''p''}
5 '''for''' each each edge (''u,v'') in ''p''
6 '''if''' (''u,v'') ∈ ''E''
7 (''u,v'').''f'' = (''v,u'').''f'' + ''cf''(''p'')
8 '''else''' (''v,u'').''f'' = (''v,u'').''f'' - ''cf''(''p'')

</code>