Algowiki - User contributions [en]

Main Page

2014-10-06T10:09:18Z

Cuozzo: /* Graph Algorithms */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Bellman-Ford
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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 ===
* [[Heritage]]
* [[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]]

=== 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]]

=== 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 Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Eulcid]]
* [[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]]

Main Page

2014-10-06T10:08:55Z

Cuozzo: /* Problems */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Bellman-Ford
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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 ===
* [[Heritage]]
* [[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]]

=== 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]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== 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 Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Eulcid]]
* [[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]]

Bellman-Ford

2014-10-06T10:05:56Z

Cuozzo:

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[All pairs shortest paths]]
'''Prerequisites:'''
'''Type of algorithm:''' loop
'''Auxiliary data:'''
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>M</math>, where <math>n=|V|</math>. The eventual contents of <math>M</math> will be returned as the result of the algorithm.
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>L</math>, where <math>n=|V|</math>. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is <math>L=M^1</math> in the terminology of Section "Powers of distance matrices" on [[Paths#Powers of distance matrices|this]] page.

==Abstract view==
'''Invariant:''' After <math>i \ge 0</math> iterations, <math>M^i (v,w)</math> contains the length of a shortest <math>(v,w)</math>-path with at most <math>i+1</math> arcs (for all <math>v,w \in V</math>).

'''Variant:''' <math>i</math> increases by 1.

'''Break condition:''' <math>i=n-1</math>.

==Induction basis==
'''Abstract view:''' For all <math>v,w \in V</math>, we set
# <math>M^0 (v,v):= L(v,v) := 0</math>;
# <math>M^0 (v,w):= L(v,w) := \ell (v,w)</math> if <math>(v,w)\in A</math>;
# <math>M^0 (v,w):= L(v,w) := +\infty</math>, if <math>v\neq w</math> and <math>(v,w)\notin A</math>.

==Induction step==
'''Abstract view:''' For all <math>v,w \in V</math>, we set <math>M^{i+1} (v,w) := \min \{ M^i (v,w) + L(u,w) \mid u \in V \}</math>.

(Note that <math>M^i (v,w) + L(u,w) = M^{i+1} (v,w)</math> is one of the arguments over which the minimum is taken, so the right-hand side is identical to <math>\min \{ M^i (v,w), \min \{ M^i (v,u)+ L(u,w) \mid u \in V \} \}</math>.)

'''Implementation:''' Obvious.

'''Correctness:''' Follows from the explanations of [[Paths#Powers of distance matrices|powers of the distance matrix]] and from the fact that a shortest path cannot have more than <math>|V|-1</math> arcs.

==Complexity==
'''Statement:''' The asymptotic complexity is <math>\Theta (n^4)</math> in the best and worst case.

'''Proof:''' The main loop terminates after <math>n-1</math> iterations. In each iteration of this loop, we update all <math>n^2</math> matrix entries, and computing one update value requires <math>\Theta (n)</math> steps.

Bellman-Ford

2014-10-06T09:51:46Z

Cuozzo: Created page with "Category:Algorithm Category:Main Algorithm '''Algorithmic problem:''' All pairs shortest paths '''Prerequisites:''' '''Type of algorithm:''' loop '''Auxiliary data..."

[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[All pairs shortest paths]]
'''Prerequisites:'''
'''Type of algorithm:''' loop
'''Auxiliary data:'''
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>M</math>, where <math>n=|V|</math>. The eventual contents of <math>M</math> will be returned as the result of the algorithm.
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>L</math>, where <math>n=|V|</math>. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is <math>L=M^1</math> in the terminology of Section "Powers of distance matrices" on [[Paths#Powers of distance matrices|this]] page.

Main Page

2014-10-06T09:45:25Z

Cuozzo: /* Divison of labor */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Bellman-Ford
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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 ===
* [[Heritage]]
* [[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]]

=== 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]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== 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 Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic redundancy check]]
* [[Eulcid]]
* [[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]]

Priority queue

2014-10-04T15:33:42Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Abstract Data Structure Category:Sequence ==General information== '''Representation invariant''' # The abstract data structure..."

__NOTOC__
[[Category:Checkup]]
[[Category:Abstract Data Structure]]
[[Category:Sequence]]
==General information==
'''Representation invariant'''
# The abstract data structure '''priority queue''' implements [[Sets and sequences#Ordered and sorted sequences|ordered sequences]].
# This abstract data structure is [[Genericity|generic]] and parameterized by a fixed '''key type''' <math>\mathcal{K}</math> and a fixed [[Genericity#Comparison|comparison]] <math>c</math> defined on <math>\mathcal{K}</math>.
# An object with key type <math>K</math> represents a finite, dynamically changing [[Sets and sequences|multiset]], whose elements are of type <math>\mathcal{K}</math> (the multiset may be empty).
# Let <math>K_{1}, K_{2} \in \mathcal{K}</math> be two values currently stored in the priority queue object such that <math>K_{1} \le K_{2}</math>. Then <math>K_{1}</math> will leave the queue earlier when the method <math>pop</math> is used than <math>K_{2}</math>.

'''Constructor:''' Gets a [[Genericity#Comparison|comparison]] <math>c</math> and initializes the queue so as to be empty.

==Method==
'''Name:''' <math>push</math>

'''Input:''' A key <math>K \in \mathcal{K}</math>.

'''Output:''' <math>\in \N</math>. A unique and permanent ID that identifies the inserted heap item.

'''Precondition:''' -

'''Postcondition:''' A new element with the key <math>K</math> is inserted into the queue.

==Method==
'''Name:''' <math>pop</math>

'''Input:''' -

'''Output:''' <math>\in \mathcal{K}</math>. Returns the minimum key <math>K</math> currently within the queue.

'''Precondition:''' There should be at least one item left in the queue <math>n>0</math>.

'''Postcondition:''' The length of the queue is smaller by one and the minimum key <math>K</math> is dequeued.

==Method==
'''Name:''' <math>peek</math>

'''Input:''' -

'''Output:''' <math>\in \mathcal{K}</math>. Returns the minimum key <math>K</math> currently within the queue or <math>void</math> if the queue is empty.

'''Precondition:''' -

'''Postcondition:''' -

==Method==
'''Name:''' <math>decreaseKey</math>

'''Input:''' A natural number <math>ID \in \N</math> presenting the heap item <math>k</math> to be changed, a key <math>K \in \mathcal{K}</math>.

'''Output:''' -

'''Precondition:'''
# A valid ID currently found within the heap <math>A</math>
# <math>1 \le ID \le N</math>
# <math>K \le A[Positions[ID]].key</math>

'''Postcondition:''' The heap item <math>h</math> has the new <math>K</math>. Its position within the heap afterwards is stored accordingly in <math>Positions[ID]</math> and remains at the same or a higher level than before.

Main Page

2014-10-04T15:06:58Z

Cuozzo: /* Graph Theory */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Problems on Sequences
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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 ===
* [[Heritage]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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 graphs|Bipartite Graph]] (DONE)
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

Bipartite graph

2014-10-04T15:04:49Z

Cuozzo: Created page with "Category:Checkup Category:Background ==Definition== An undirected graph <math>G=(V,E)</math> is called '''bipartite''' if there is a partition of <math>V</math>, <math..."

[[Category:Checkup]]
[[Category:Background]]
==Definition==
An undirected graph <math>G=(V,E)</math> is called '''bipartite''' if there is a partition of <math>V</math>, <math>V=V_{1} \dot\cup V_{2}</math>, such that for every edge <math>\{ v,w \} \in E</math> it is <math>v \in V_{1} \Leftrightarrow w \in V_{2}</math>.

==Absence of odd cycles==
'''Theorem:''' An undirected graph <math>G=(V,E)</math> is bipartite if, and only if, <math>G</math> has now cycle of odd length.

'''Proof:'''
* First suppose <math>G</math> contains at least one cycle <math>v_{1} - v_{2} - ... - v_{k} - v_{1}</math> of odd length <math>k \in \N</math>. Without loss of generality, we assume <math>v_{1} \in V_{1}</math>. Then it is <math>v_{i} \in V_{1}</math> for all odd <math>i</math> and <math>v_{i} \in V_{2}</math> for all even <math>i</math>. The edge <math>\{ v,w \}</math> contradicts bipartiteness.
* Now suppose that <math>G</math> contains no cycle of negative length. We will prove bipartiteness constructively. Without loss of generality, we may assume that <math>G</math> is connected (otherwise, each connected component may be considered separately). We start with an arbitrary node <math>u \in V</math> and label each node "<math>x</math>" if its distance (smallest number of edges) from <math>v</math> is even, and "<math>y</math>", otherwise. Suppose for a contradiction that there is an edge <math>\{ v,w \}</math> such that both endnotes have the same label. Then the shortest paths from <math>u</math> to <math>v</math> and <math>w</math> plus this edge from an odd cycle (which is not simple but can be easily reduced to a simple cycle, which is odd again).

Strings

2014-10-02T13:35:28Z

Cuozzo: Created page with "Category:Checkup Category:Background ==Definitions== # An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>. # The elements of an alphabet <math>\..."

[[Category:Checkup]]
[[Category:Background]]
==Definitions==
# An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>.
# The elements of an alphabet <math>\Sigma</math> are called its '''characters'''.
# A '''string''' over alphabet <math>\Sigma</math> is an [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] of characters of <math>\Sigma</math>.
# The '''length''' of a string <math>str</math> is the number of characters and denoted by <math>|str|</math> or <math>\ell (str)</math>.
# For <math>i\in \{ 1,...,\ell (str)\}</math>, the character of <math>str</math> at position <math>i</math> is denoted by <math>str[i]</math>.
# For two strings <math>str1</math> and <math>str2</math> over some alphabet <math>\Sigma</math>, we say that <math>str1</math> is a '''prefix''' of <math>str2</math> if
## <math>\ell (str1) \le \ell (str2)</math> and
## for <math>i \in \{ 1,...,\ell (str1)\}</math> it is <math>str1[i] = str2[i]</math>.
# Analogously, we say that <math>str1</math> is a '''suffix''' of <math>str2</math> if
## <math>\ell (str1) \le \ell (str2)</math> and
## for <math>i \in \{ 1,...,\ell (str1)\}</math> it is <math>str1[i]=str2[\ell (str2)- \ell(str1)+i]</math>.
#We say that <math>str1</math> is a '''proper''' prefix (resp., suffix) of <math>str2</math> if <math>str1</math> is a prefix (resp., suffix) of <math>str2</math> and <math>\ell (str1) < \ell (str2)</math>.

==Lexicographic order==
Suppose a [[Genericity#Comparison|comparison]] is defined on alphabet <math>\Sigma</math>. For two strings <math>str1</math> and <math>str2</math> over <math>\Sigma</math>, we say that <math>str1</math> is '''lexicographically''' smaller than <math>str2</math> - or alternatively, <math>str1</math> '''precedes''' <math>str2</math> '''lexicographically''' - if <math>str1 \neq str2</math> and one of the following two conditions is fulfilled:
# <math>str1</math> is a proper prefix of <math>str2</math>.
# Let <math>\ell := \min \{ \ell (str1), \ell (str2)\}</math> for short. Let <math>k := \min \{i \mid i \in \{1,...,\ell \} , str1[i] \neq str2[i] \}</math>. Now the second condition is <math>str1[k] < str2[k]</math>.
If <math>str1</math> precedes <math>str2</math> we write <math>str1 \prec str2</math>, and we write <math>str1 \preceq str2</math> if either <math>str1</math> precedes <math>str2</math> or <math>str1 = str2</math>.

Genericity

2014-10-02T13:14:07Z

Cuozzo: Created page with "Category:Background Category:Checkup ==Definition== An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic'''..."

[[Category:Background]]
[[Category:Checkup]]
==Definition==
An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic''' if one or more related types are left open in the definition. The choice of these types is deferred until the algorithm is called or an object of the data structure is created.

===Remark===
Typically, there are requirements on the open types. A typical requirement is that a comparison as defined below is given for that type.

==Comparison==
A '''comparison''' on a finite or infinite set <math>S</math> is a binary relation <math>c:S\times S \rightarrow \{ -1,0,+1\}</math> with the following properties:
* <math>c(x,x) = 0</math> for all <math>x \in S</math> (reflexivity),
* <math>c(x,y)=-c(y,x)</math> for all <math>x,y \in S</math> (anti-commutativity), and
* <math>(c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1</math> for all <math>x,y,z \in S</math> (transitivity)
For convenience, we write <math>x<y</math> in case <math>c(x,y)=1</math>, <math>x\le y</math> in case <math>c(x,y)\ge 0</math>, and so on.

===Remark===
Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which pairs of elements may be incomparable.

Sets and sequences

2014-10-02T12:58:05Z

Cuozzo: Created page with "Category:Checkup Category:Background ==Sets and multisets== in a '''set''', each element occurs at most once, that is, no duplications of elements within a set. In con..."

[[Category:Checkup]]
[[Category:Background]]
==Sets and multisets==
in a '''set''', each element occurs at most once, that is, no duplications of elements within a set. In contrast, in a '''multiset''', al element may occur more than once. The '''multiplicity''' of an element in a multiset is the number of its occurrences in that set.

===Remark===
Of course, in computer science, sets and multisets are assumed to be dynamic, that is, elements may be inserted and removed.

==Ordered and sorted sequences==
An '''ordered sequence''' (or '''sequence''', for short) is given by
# a number <math>n \in \N_{0}</math>, its '''length''',
# some '''component type''' <math>C</math>, and
# a mapping <math>\pi : \{1,...,n\} \rightarrow C</math>.
We say that <math>1,...,n</math> are the '''positions''' in the sequence (a.k.a. the '''indexes'''). The element <math>\pi (i)</math> of sequence <math>S</math> at position <math>i</math> is denoted by <math>S[i]</math>.

Consider a comparison <math>c</math> on <math>C</math>, as introduced above. Then a sequence <math>S</math> of length <math>n</math> is '''sorted''' with respect to <math>c</math>, if <math>S[i] \le S[i+1]</math> for all <math>i \in \{1,...,n-1\}</math>.

===Remark===
Note that the first position is <math>1</math>, not <math>0</math>, as opposed to array indexes in many popular programming languages such as C, C++, and Java.

Like '''sets and multisets''', sequences are dynamic.

==Maps==
A '''map''' is given by
# a number <math>n \in \N_{0}</math>, its '''size'''
# a '''key type''' <math>\mathcal{K}</math> and a '''value type''' <math>\mathcal{V}</math>,
# a finite subset <math>K \subseteq \mathcal{K}</math>, the map's '''keys''', and
# a mapping <math>K \rightarrow \mathcal{V}</math>, which assigns a value to each key in the map.

===Remark===
A sequence may also be a map, namely if its component type is <math>\mathcal{K} \times \mathcal{V}</math> and each value of <math>\mathcal{K}</math> occurs at most once.

Like '''sets, multisets and sequences''', maps are dynamic.

Main Page

2014-10-02T12:40:10Z

Cuozzo: /* Problems */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Problems on Sequences
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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 ===
* [[Heritage]]
* [[Generics]]
* [[Collections]]
** [[Iterator]]
** [[Comparator]]

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

Category:Sorting

2014-10-02T12:38:11Z

Cuozzo: Created page with "Category:Problems on Sequences"

[[Category:Problems on Sequences]]

Sorting Sequences of Strings

2014-10-02T12:37:23Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Sorting ==Input== An ordered sequence <math>S<..."

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Sorting]]
==Input==
An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n \in \mathbb{N}_{0}</math> and component type string over some [[Strings|alphabet]] <math>\Sigma</math>.

==Output==
A permutation of <math>S</math> such that, for <math>i \in \{1,...,n-1\}</math>, <math>S[i]</math> is not [[Strings#Lexicographic order|lexicographically]] larger than <math>S[i+1]</math>.

==Objective==
N/A

==Complexity==
Linear in the total sum of all string lengths.

==Known algorithms==
[[Bucketsort]]

Sorting based on pairwise comparison

2014-10-02T12:29:35Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Sorting ==Input== # An ordered sequence <math>..."

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Sorting]]
==Input==
# An [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n</math>.
# A definition of [[Genericity#Comparison|comparison]] on the component type of <math>S</math>.

==Output==
A permutation of <math>S</math> such that <math>S[i] \le S[i+1]</math> for all <math>i\in \{1,...,n-1\}</math>.

==Objective==
N/A

==Complexity==
Polynomial.

==Known algorithms==
# [[Bubblesort]]
# [[Mergesort]]
# [[Quicksort]]
# [[Selection sort]]

==Remark==
Some algorithms could be formulated in a much simpler way in case each key occurs at most once in <math>S</math>. Here all algorithms are formulated for the general case of arbitrary multiplicities. Alternatively, there are three options to make each key unique:
# An additional generated key, for example, student ID or tax file number.
# If the keys are associated with values, they are additionally compared if the keys of two items are identical (e.g. date of birth and home address, if last and first names of two persons are identical).
# If the keys are '''not''' associated with values, we may remove the duplicates and store their multiplicities separately.

Main Page

2014-10-02T12:17:02Z

Cuozzo: /* Problems */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Problems on Sequences
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

Median

2014-10-02T12:16:18Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Basic Problems on Sequences ==Input== An Sets and multisets#Ordered and sorted sequences|ordered..."

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Basic Problems on Sequences]]
==Input==
An [[Sets and multisets#Ordered and sorted sequences|ordered sequence]] <math>S</math> of length <math>n</math> such that a [[Genericity#Comparison|comparison]] <math>c</math> is defined on the component type <math>C</math> of <math>S</math>.

==Output==
# If <math>n</math> is odd, the median is the unique value <math>x \in \{ S[1],...,S[n]\}</math> such that
## <math>S[i]<x</math> for at most <math>\lfloor n/2 \rfloor</math> positions <math>i</math> of <math>S</math> and
## <math>S[i]>x</math> for at most <math>\lfloor n/2 \rfloor</math> positions <math>i</math> of <math>S</math>.
# On the other hand, if <math>n</math> is even, the median is <math>(x+y)/2</math>, where <math>x,y \in \{ S[1],...,S[n]\}</math> (let <math>x \le y</math>) are the unique values such that
## <math>S[i]<x</math> for at most <math>\lfloor n/2 \rfloor</math> positions <math>i</math> of <math>S</math>, and
## <math>S[i]>y</math> for at most <math>\lfloor n/2 \rfloor</math> positions <math>i</math> of <math>S</math>.

==Objective==
N/A

Main Page

2014-10-01T20:06:53Z

Cuozzo: /* Problems */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Problems on Sequences
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Merging two sorted sequences]] (DONE)
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

Category:Basic Problems on Sequences

2014-10-01T20:05:06Z

Cuozzo: Created page with "Category:Problems on Sequences"

[[Category:Problems on Sequences]]

Merging two sorted sequences

2014-10-01T20:03:34Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Basic Problems on Sequences ==Input== Two Sets and sequences#Ordered and sorted sequences|sorted..."

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Basic Problems on Sequences]]
==Input==
Two [[Sets and sequences#Ordered and sorted sequences|sorted sequences]], <math>S_{1}</math> and <math>S_{2}</math>, that have identical component type and identical definition of [[Genericity#Comparison|comparison]].

==Output==
A sorted sequence <math>S</math>, whose element set is the union of the element sets of <math>S_{1}</math> and <math>S_{2}</math>, sorted according to the same definition of comparison.

==Objective==
N/A

==Complexity==
Linear in the sum of the lengths of the input sequences.

==Known algorithms==
[[Merge]]

Find an element in a sequence

2014-10-01T19:53:57Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Basic Problems on Sequences ==Input== # A sequence <math>S</math>. # an element <math>x</math> of..."

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Basic Problems on Sequences]]
==Input==
# A sequence <math>S</math>.
# an element <math>x</math> of the component type of <math>S</math>.

==Output==
A boolean value:
# <math>true</math>, if <math>x</math> is currently in <math>S</math>,
# <math>false</math>, otherwise.

==Objective==
N/A

==Complexity==
Linear

==Known algorithms==
# [[Find element in sequence iteratively]]
# [[Find element in sequence recursively]]

Category:Problems on Sequences

2014-10-01T19:46:45Z

Cuozzo: Created page with "Category:Algorithmic Problem"

[[Category:Algorithmic Problem]]

Problems on Sequences

2014-10-01T19:43:34Z

Cuozzo: Blanked the page

Problems on Sequences

2014-10-01T19:41:13Z

Cuozzo: Created page with "Category:Algorithmic Problem"

[[Category:Algorithmic Problem]]

Main Page

2014-10-01T19:39:23Z

Cuozzo: /* Divison of labor */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Problems on Sequences
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Insert an element in a sequence]]
*** [[Median]]
*** [[Merging two sorted sequences]]
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

Main Page

2014-10-01T19:32:25Z

Cuozzo: /* Problems */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Pattern Matching
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Insert an element in a sequence]]
*** [[Median]]
*** [[Merging two sorted sequences]]
** [[Pattern Matching]]
*** [[One-dimensional string matching]] (DONE)
*** [[String matching]] (DONE)
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

String matching

2014-10-01T19:30:13Z

Cuozzo: /* Known algorithms */

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Pattern Matching]]
==Input==
Two non-empty [[Sets and sequences|sequences]], <math>S</math> and <math>T</math>. Let <math>n(S),n(T) \in \mathbb{N}</math> denote the lengths of <math>S</math> and <math>T</math>, respectively.

==Output==
A [[Sets and sequences#Ordered and sorted sequences|sorted sequences]] <math>P</math> of positions of <math>S</math>, that is, <math>P[i] \in \{ 1,...,n(S)\}</math> for all positions of <math>P</math>. More specifically, <math>P</math> contains all positions <math>m</math> of <math>S</math> such that <math>S[m+j-1]=T[j]</math> for all <math>j \in \{ 1,...,n(T)\}</math>. Such a subsequence <math>(S[m],...,S[m+n(T)-1])</math> is called an '''occurrence''' of <math>T</math> in <math>S</math>.

==Objective==
N/A

==Complexity==

==Known algorithms==
[[Simple string matching algorithm]]

[[String matching based on finite automaton]]

==Remark==
Note that occurrences of <math>T</math> in <math>S</math> may overlap (otherwise, the string matching problem would be trivially solvable in linear time).

String matching

2014-10-01T19:29:35Z

Cuozzo: Created page with "__NOTOC__ Category:Checkup Category:Algorithmic Problem Category:Pattern Matching ==Input== Two non-empty sequences, <math>S</math> and <mat..."

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Pattern Matching]]
==Input==
Two non-empty [[Sets and sequences|sequences]], <math>S</math> and <math>T</math>. Let <math>n(S),n(T) \in \mathbb{N}</math> denote the lengths of <math>S</math> and <math>T</math>, respectively.

==Output==
A [[Sets and sequences#Ordered and sorted sequences|sorted sequences]] <math>P</math> of positions of <math>S</math>, that is, <math>P[i] \in \{ 1,...,n(S)\}</math> for all positions of <math>P</math>. More specifically, <math>P</math> contains all positions <math>m</math> of <math>S</math> such that <math>S[m+j-1]=T[j]</math> for all <math>j \in \{ 1,...,n(T)\}</math>. Such a subsequence <math>(S[m],...,S[m+n(T)-1])</math> is called an '''occurrence''' of <math>T</math> in <math>S</math>.

==Objective==
N/A

==Complexity==

==Known algorithms==
[[Simple string matching algorithm]]
[[String matching based on finite automaton]]

==Remark==
Note that occurrences of <math>T</math> in <math>S</math> may overlap (otherwise, the string matching problem would be trivially solvable in linear time).

Category:Pattern Matching

2014-10-01T19:15:30Z

Cuozzo: Created page with "Category:Problems on Sequences"

[[Category:Problems on Sequences]]

Main Page

2014-10-01T19:12:27Z

Cuozzo: /* Divison of labor */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Pattern Matching
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Insert an element in a sequence]]
*** [[Median]]
*** [[Merging two sorted sequences]]
** [[Pattern Matching]]
*** [[One-dimensional string matching]]
*** [[String matching]]
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

One-dimensional string matching

2014-10-01T19:06:26Z

Cuozzo:

[[Category:Checkup]]
[[Category:Algorithmic Problem]]
[[Category:Pattern Matching]]
__NOTOC__
==Input==
Two [[Linear sequence|linear sequences]], <math>S</math> of length <math>n=|S|</math> and <math>T</math> of length <math>m=|T|</math>.

==Output==
A [[Sets and sequences#Ordered and sorted sequences|sorted sequence]] <math>R</math> of integral values from <math>\{ 1,...,n\}</math> such that <math>i \in R</math> if, and only if, it is <math>i\le n-m+1</math> and <math>T[j]=S[i+j-1]</math> for all <math>j \in \{ 1,...,m \}</math>.

==Objective==
N/A

==Complexity==
Polynomial.

==Known algorithms==
# [[Simple string matching algorithm]]
# [[String matching based on finite automaton]]

One-dimensional string matching

2014-10-01T19:05:04Z

Cuozzo: Created page with "Category:Algorithmic Problem Category:Pattern Matching __NOTOC__ ==Input== Two linear sequences, <math>S</math> of length <math>n=|S|</math> and <m..."

[[Category:Algorithmic Problem]]
[[Category:Pattern Matching]]
__NOTOC__
==Input==
Two [[Linear sequence|linear sequences]], <math>S</math> of length <math>n=|S|</math> and <math>T</math> of length <math>m=|T|</math>.

==Output==
A [[Sets and sequences#Ordered and sorted sequences|sorted sequence]] <math>R</math> of integral values from <math>\{ 1,...,n\}</math> such that <math>i \in R</math> if, and only if, it is <math>i\le n-m+1</math> and <math>T[j]=S[i+j-1]</math> for all <math>j \in \{ 1,...,m \}</math>.

==Objective==
N/A

==Complexity==
Polynomial.

==Known algorithms==
# [[Simple string matching algorithm]]
# [[String matching based on finite automaton]]

Main Page

2014-10-01T14:09:22Z

Cuozzo: /* String Matching Algorithms */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Heaps
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Insert an element in a sequence]]
*** [[Median]]
*** [[Merging two sorted sequences]]
** [[Pattern Matching]]
*** [[One-dimensional string matching]]
*** [[String matching]]
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

String matching based on finite automaton

2014-10-01T14:08:37Z

Cuozzo:

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A current '''maximum prefix length''' <math>q\in \{ 0,...,m\}</math>.
# A look-up table <math>\Delta</math> with rows <math>\{ 0,...,m\}</math> and one column for each character in the alphabet <math>\Sigma</math>. Intended semantics: The value <math>\Delta [j,c]</math> is the length of the longest [[Strings|prefix]] of <math>T</math> that is also a [[Strings|suffix]] of <math>(T[1],...,T[j],c)</math>.

==Abstract view==
'''Invariant:''' After <math>i \ge 0</math>:
# In ascending order, <math>R</math> contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in <math>(S[1],...,S[i])</math>; in other words, the start indexes in the range <math>(1,...,i-m+1])</math>.
# The value of <math>q</math> is the largest value <math>k</math> such that <math>(S[i-k+1],...,S[i])=(T[1],...,T[k])</math>.
To understand the rationale of the second invariant, note that <math>(S[i-k+1],...,S[i])=(T[1],...,T[k])</math> is equivalent to the informal statement that <math>(S[i-k+1],...,S[i])</math> is a candidate for an occurrence of <math>T</math>. In particular, <math>i-q+1</math> is always the "most advanced" candidate (and <math>q=0</math> means that, at the moment, there is no candidate at all).

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==
'''Abstract view:'''
# <math>R</math> is empty.
# The initial value of <math>q</math> is zero.
# The look-up table <math>\Delta</math> must be built.

'''Implementation:'''
# Set <math>R:=\emptyset</math>.
# Set <math>q:=0</math>.
# For <math>c\in \Sigma</math>: If <math>T[1]=c</math>, set <math>\Delta [0,c]:=1</math>; otherwise, set <math>\Delta[0,c]:=0</math>.
# For <math>j\in \{ 1,...,m\}</math> and <math>c \in \Sigma</math>:
## Set <math>k:=\min \{ m,j+1 \}</math>.
## While <math>k>0</math> and <math>(T[1],...,T[k]) \neq (T[j-k+2],...,T[j],c)</math>, decrease <math>k</math> by <math>1</math>.
## Set <math>\Delta[j,c]:=k</math>.

'''Proof:''' Nothing is to show for <math>R</math> and <math>q</math>, so consider <math>\Delta</math>. We have to show that the above-described intended semantics of <math>\Delta</math> is indeed fulfilled, because these intended semantics of <math>\Delta</math> will be the basis for the correctness proof of the induction step.

Correctness of Step 3 is also easy to see, so consider Step 4.

According to its intended semantics, <math>\Delta [j,c]</math> can neither be larger than <math>m</math> nor larger than <math>j+1</math>; in fact, any string longer than <math>m</math> is not a prefix of <math>T</math>, and any string longer than <math>j+1</math> is not a suffix of <math>(T[1],...,T[j],c)</math>. This observation justifies the initialization of <math>k</math> in Step 4.1.

Now, the countdown of <math>k</math> in Step 4.2 will terminate at the moment when, for the first time, <math>k</math> fulfills <math>(T[1],...,T[k])=(T[j-k+2],...,T[j],c)</math>. Note that this equality is tantamount to the statement that the prefix <math>(T[1],...,T[k])</math> of <math>T</math> is a suffix of <math>(T[j-k+2],...,T[j],c)</math>. Due to the countdown, <math>k</math> is largest, so <math>\Delta [j,c]</math> conforms to its intended semantics. On the other hand, if the countdown terminates with <math>k=0</math>, there was no such non-empty substring, so it is <math>\Delta [j,c]=0</math>, which conforms to the intended semantics in this case as well.

==Induction step==
'''Abstract view:'''
# The current maximum prefix length <math>q</math> is to be updated to reflect the situation after reading <math>S[i]</math>.
# If <math>q=m</math>, <math>i</math> completes an occurrence of <math>T</math> in <math>S</math>, so the start index of this occurrence is to be appended to <math>R</math>.

'''Implementation:'''
# Set <math>q:=\Delta [q,S[i]]</math>.
# If <math>q=m</math>, append <math>i-m+1</math> to <math>R</math>.

'''Correctness:''' If the invariant on <math>q</math> is maintained by Step 1, it is <math>q=m</math> if, and only if, <math>i</math> is the last index of an occurrence of <math>T</math>. This proves correctness of Step 2 and thus maintenance of the first invariant, provided maintenance of the second invariant (the invariant on <math>q</math>) is proved. So it remains to show that the invariant on <math>q</math> is indeed maintained.

Recall that the correctness proof of the induction basis has proved that <math>\Delta</math> fulfills the intended semantics as described above. Therefore, the new value of <math>q</math> after the <math>i</math>-th iteration is the largest length <math>k</math> of a prefix <math>(T[1],...,T[k]</math> that is identical to <math>(T[i-k+2],...,T[i],S[i])</math>. As described above, this is the new "most advanced candidate", so the new value of <math>q</math> is correct.

==Complexity==
'''Statement:''' The worst-case complexity is in <math>\mathcal{O}(m^3 * |\Sigma | + n)</math>.

'''Proof:''' The first summand results from Step 4 of the induction basis. In fact, for each <math>j \in \{ 1,...,m\}</math> and each <math>c \in \Sigma</math>, the value of <math>\Delta [q,c]</math> is to be computed. The countdown to compute <math>\Delta [q,c]</math> takes at most <math>m</math> iterations. Finally, for the comparison of the two substrings within one step of the countdown, at most <math>m</math> pairs of characters have to be compared.

The second summand is the asymptotic complexity of the main loop: the number of iterations is at most <math>n</math>, and each iteration takes constant time.

==Further information==
There is a more sophisticated approach to computing <math>\Delta</math>, which results in <math>\mathcal{O}(m*|\Sigma |)</math> worst-case complexity

String matching based on finite automaton

2014-10-01T14:08:01Z

Cuozzo: /* Further information */

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A current '''maximum prefix length''' <math>q\in \{ 0,...,m\}</math>.
# A look-up table <math>\Delta</math> with rows <math>\{ 0,...,m\}</math> and one column for each character in the alphabet <math>\Sigma</math>. Intended semantics: The value <math>\Delta [j,c]</math> is the length of the longest [[Strings|prefix]] of <math>T</math> that is also a [[Strings|suffix]] of <math>(T[1],...,T[j],c)</math>.

==Abstract view==
'''Invariant:''' After <math>i \ge 0</math>:
# In ascending order, <math>R</math> contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in <math>(S[1],...,S[i])</math>; in other words, the start indexes in the range <math>(1,...,i-m+1])</math>.
# The value of <math>q</math> is the largest value <math>k</math> such that <math>(S[i-k+1],...,S[i])=(T[1],...,T[k])</math>.
To understand the rationale of the second invariant, note that <math>(S[i-k+1],...,S[i])=(T[1],...,T[k])</math> is equivalent to the informal statement that <math>(S[i-k+1],...,S[i])</math> is a candidate for an occurrence of <math>T</math>. In particular, <math>i-q+1</math> is always the "most advanced" candidate (and <math>q=0</math> means that, at the moment, there is no candidate at all).

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==
'''Abstract view:'''
# <math>R</math> is empty.
# The initial value of <math>q</math> is zero.
# The look-up table <math>\Delta</math> must be built.

'''Implementation:'''
# Set <math>R:=\emptyset</math>.
# Set <math>q:=0</math>.
# For <math>c\in \Sigma</math>: If <math>T[1]=c</math>, set <math>\Delta [0,c]:=1</math>; otherwise, set <math>\Delta[0,c]:=0</math>.
# For <math>j\in \{ 1,...,m\}</math> and <math>c \in \Sigma</math>:
## Set <math>k:=\min \{ m,j+1 \}</math>.
## While <math>k>0</math> and <math>(T[1],...,T[k]) \neq (T[j-k+2],...,T[j],c)</math>, decrease <math>k</math> by <math>1</math>.
## Set <math>\Delta[j,c]:=k</math>.

'''Proof:''' Nothing is to show for <math>R</math> and <math>q</math>, so consider <math>\Delta</math>. We have to show that the above-described intended semantics of <math>\Delta</math> is indeed fulfilled, because these intended semantics of <math>\Delta</math> will be the basis for the correctness proof of the induction step.

Correctness of Step 3 is also easy to see, so consider Step 4.

According to its intended semantics, <math>\Delta [j,c]</math> can neither be larger than <math>m</math> nor larger than <math>j+1</math>; in fact, any string longer than <math>m</math> is not a prefix of <math>T</math>, and any string longer than <math>j+1</math> is not a suffix of <math>(T[1],...,T[j],c)</math>. This observation justifies the initialization of <math>k</math> in Step 4.1.

Now, the countdown of <math>k</math> in Step 4.2 will terminate at the moment when, for the first time, <math>k</math> fulfills <math>(T[1],...,T[k])=(T[j-k+2],...,T[j],c)</math>. Note that this equality is tantamount to the statement that the prefix <math>(T[1],...,T[k])</math> of <math>T</math> is a suffix of <math>(T[j-k+2],...,T[j],c)</math>. Due to the countdown, <math>k</math> is largest, so <math>\Delta [j,c]</math> conforms to its intended semantics. On the other hand, if the countdown terminates with <math>k=0</math>, there was no such non-empty substring, so it is <math>\Delta [j,c]=0</math>, which conforms to the intended semantics in this case as well.

==Induction step==
'''Abstract view:'''
# The current maximum prefix length <math>q</math> is to be updated to reflect the situation after reading <math>S[i]</math>.
# If <math>q=m</math>, <math>i</math> completes an occurrence of <math>T</math> in <math>S</math>, so the start index of this occurrence is to be appended to <math>R</math>.

'''Implementation:'''
# Set <math>q:=\Delta [q,S[i]]</math>.
# If <math>q=m</math>, append <math>i-m+1</math> to <math>R</math>.

'''Correctness:''' If the invariant on <math>q</math> is maintained by Step 1, it is <math>q=m</math> if, and only if, <math>i</math> is the last index of an occurrence of <math>T</math>. This proves correctness of Step 2 and thus maintenance of the first invariant, provided maintenance of the second invariant (the invariant on <math>q</math>) is proved. So it remains to show that the invariant on <math>q</math> is indeed maintained.

Recall that the correctness proof of the induction basis has proved that <math>\Delta</math> fulfills the intended semantics as described above. Therefore, the new value of <math>q</math> after the <math>i</math>-th iteration is the largest length <math>k</math> of a prefix <math>(T[1],...,T[k]</math> that is identical to <math>(T[i-k+2],...,T[i],S[i])</math>. As described above, this is the new "most advanced candidate", so the new value of <math>q</math> is correct.

==Complexity==
'''Statement:''' The worst-case complexity is in <math>\mathcal{O}(m^3 * |\Sigma | + n)</math>.

'''Proof:''' The first summand results from Step 4 of the induction basis. In fact, for each <math>j \in \{ 1,...,m\}</math> and each <math>c \in \Sigma</math>, the value of <math>\Delta [q,c]</math> is to be computed. The countdown to compute <math>\Delta [q,c]</math> takes at most <math>m</math> iterations. Finally, for the comparison of the two substrings within one step of the countdown, at most <math>m</math> pairs of characters have to be compared.

The second summand is the asymptotic complexity of the main loop: the number of iterations is at most <math>n</math>, and each iteration takes constant time.

==Further information==
There is a more sophisticated approach to computing <math>\Delta</math>, which results in <math>\mathcal{O}(m*|\Sigma |)</math> worst-case complexity

String matching based on finite automaton

2014-10-01T14:06:31Z

Cuozzo: /* Complexity */

String matching based on finite automaton

2014-10-01T14:00:50Z

Cuozzo: /* Induction step */

String matching based on finite automaton

2014-10-01T13:51:21Z

Cuozzo: /* Induction basis */

String matching based on finite automaton

2014-10-01T13:23:30Z

Cuozzo:

String matching based on finite automaton

2014-10-01T13:04:38Z

Cuozzo:

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Type of algorithm:'''

'''Auxiliary data:'''

==Abstract view==

==Induction basis==

==Induction step==

==Complexity==

==Further information==

Main Page

2014-10-01T10:31:55Z

Cuozzo: /* String Matching Algorithms */

== News ==
* <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!

== Divison of labor ==
* Fabio Cuozzo - Heaps
* Daniel Kratschmann - Problems
* Jan Hohmann - B-Tree
* Jan Rathjens - Ford-Fulkerson
* Thomas Lautenschläger - ???

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

== To Do ==
=== Notations ===
* [[Asymptotic 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]]
*** [[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]]
*** [[Insert an element in a sequence]]
*** [[Median]]
*** [[Merging two sorted sequences]]
** [[Pattern Matching]]
*** [[One-dimensional string matching]]
*** [[String matching]]
** [[Sorting]]
*** [[Sorting based on pairwise comparison]]
*** [[Sorting Sequences of Strings]]

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

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

=== Sorting Algorithms ===
* [[Bubble]]
* [[Insertion Sort]]
* [[Quick Sort]]
* [[Bubble Sort]]
* [[Merge Sort]]
* [[Bucket Sort]]
* [[Selection Sort]]
* [[Bogo Sort]]

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

=== 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-Child]]
* [[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]]
* [[k-partite Graph]]
* [[Negative Paths]]

=== Graph Algorithms ===
* [[Dijkstra]]
* [[Kruskal]]
* [[Prim]]
* [[Bellman-Ford]]
* [[Floyd-Warshall]]
* [[Union Find]]
* [[A*]]
* [[Alternating paths algorithm]]
* [[Johnson]]

=== Flow Algorithms ===
* [[Ford-Fulkerson]]
=== Data Structures ===
* [[Linked List]]
* [[Array List]]
* [[First In - First Out]]
* [[First In - Ieast Out]]
* [[Double Linked List]]
* [[Heaps]] (DONE (Heap as Array))
* [[Min-Max Heaps]]
* [[Hash Table]]
* [[Directed Tree]]
* [[Binary Search Tree]]
* [[B-Trees]]
* [[Decision Tree]]
* [[Red-Black Tree]]
* [[Graphs]]

=== Other Algorithms (LOCKED) ===
* [[B*]]
* [[Cyclic Redundancy Check]]
* [[Eulcid]]
* [[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 Round]]
* [[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]]

Simple string matching algorithm

2014-10-01T10:31:03Z

Cuozzo:

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

==Abstract view==
'''Invariant:''' After <math>i\ge 0</math> iterations:
# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.
# In ascending order, <math>I</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==
'''Abstract view:''' <math>R</math> and <math>I</math> have to be empty.

'''Implementation:'''
# <math>R:=\emptyset</math>
# <math>I:=\emptyset</math>

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

==Induction step==
'''Abstract view:'''
# For each start index in <math>I</math>, we decide whether this is still a candidate after we have seen <math>S[i]</math>. If not, we remove this start index from <math>I</math>.
# Afterwards:
## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.
## If start index <math>i-m+1</math> is at the head of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.

'''Implementation:''' Obvious.

'''Correctness:'''
# Due to the second invariant, the induction hypothesis implies that all elements of <math>I</math> immediately before the <math>i</math>-th iteration must be from the set <math>\{i-m+1,...,i-1\}</math>. Therefore, if <math>i-m+1</math> is in <math>I</math>, it is the smallest element. Since the elements of <math>I</math> are in ascending order, <math>i-m+1</math> is then at the head of <math>I</math>.
# A start index <math>j</math> in <math>I</math> is to be dropped if, and only if, it turns out not to be a promising candidate anymore. As the induction hypothesis implies <math>(S[j],...,S[i-1])=(T[1],...,T[i-j])</math>, this is the case if, and only if, <math>S[i]\neq T[i-j+1]</math>.
# Clearly, it would be incorrect to transfer any element of <math>I</math> except <math>i-m+1</math> to <math>R</math>. Thus, we are right to focus on <math>i-m+1</math> in Step 2.2. Now, <math>i-m+1</math> is in <math>I</math> if, and only if, (1) it was present immediately before the <math>i</math>-th iteration and (2) it has survived the first step of the <math>i</math>-th iteration. The induction hypothesis implies <math>(S[i-m+1],...,S[i-1])=(T[1],...,T[m-1])</math>, so it is correct to transfer <math>i-m+1</math> to <math>R</math> if, and only if, it is <math>S[i]=T[m]</math> as well.
# Clearly, it would also be incorrect to add any element to <math>I</math> except <math>i</math>. So we are right to focus on <math>i</math> in Step 2.1. Obviously, all elements of <math>I</math> are less than <math>i</math>, so we are also right to append <math>i</math> at the tail of <math>I</math> in case <math>S[i]=T[1]</math>.

==Complexity==
'''Statement:''' Let <math>r\in \mathbb{N}</math> denote the maximal number of candidates to be considered simultaneously. Then the worst-case run time is in <math>\mathcal{O}(n*r)</math>.

'''Proof:''' Obviously, the first step of an iteration takes <math>\mathcal{O}(r)</math> time, and the other steps take constant time. The loop has <math>n</math> iterations.

==Further information==

Simple string matching algorithm

2014-10-01T10:29:30Z

Cuozzo: /* Complexity */

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

==Abstract view==
'''Invariant:''' After <math>i\ge 0</math> iterations:
# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.
# In ascending order, <math>I</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==
'''Abstract view:''' <math>R</math> and <math>I</math> have to be empty.

'''Implementation:'''
# <math>R:=\emptyset</math>
# <math>I:=\emptyset</math>

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

==Induction step==
'''Abstract view:'''
# For each start index in <math>I</math>, we decide whether this is still a candidate after we have seen <math>S[i]</math>. If not, we remove this start index from <math>I</math>.
# Afterwards:
## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.
## If start index <math>i-m+1</math> is at the head of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.

'''Implementation:''' Obvious.

'''Correctness:'''
# Due to the second invariant, the induction hypothesis implies that all elements of <math>I</math> immediately before the <math>i</math>-th iteration must be from the set <math>\{i-m+1,...,i-1\}</math>. Therefore, if <math>i-m+1</math> is in <math>I</math>, it is the smallest element. Since the elements of <math>I</math> are in ascending order, <math>i-m+1</math> is then at the head of <math>I</math>.
# A start index <math>j</math> in <math>I</math> is to be dropped if, and only if, it turns out not to be a promising candidate anymore. As the induction hypothesis implies <math>(S[j],...,S[i-1])=(T[1],...,T[i-j])</math>, this is the case if, and only if, <math>S[i]\neq T[i-j+1]</math>.
# Clearly, it would be incorrect to transfer any element of <math>I</math> except <math>i-m+1</math> to <math>R</math>. Thus, we are right to focus on <math>i-m+1</math> in Step 2.2. Now, <math>i-m+1</math> is in <math>I</math> if, and only if, (1) it was present immediately before the <math>i</math>-th iteration and (2) it has survived the first step of the <math>i</math>-th iteration. The induction hypothesis implies <math>(S[i-m+1],...,S[i-1])=(T[1],...,T[m-1])</math>, so it is correct to transfer <math>i-m+1</math> to <math>R</math> if, and only if, it is <math>S[i]=T[m]</math> as well.
# Clearly, it would also be incorrect to add any element to <math>I</math> except <math>i</math>. So we are right to focus on <math>i</math> in Step 2.1. Obviously, all elements of <math>I</math> are less than <math>i</math>, so we are also right to append <math>i</math> at the tail of <math>I</math> in case <math>S[i]=T[1]</math>.

==Complexity==
'''Statement:''' Let <math>r\in \mathbb{N}</math> denote the maximal number of candidates to be considered simultaneously. Then the worst-case run time is in <math>\mathcal{O}(n*r)</math>.

'''Proof:''' Obviously, the first step of an iteration takes <math>\mathcal{O}(r)</math> time, and the other steps take constant time. The loop has <math>n</math> iterations.

==Further information==

Simple string matching algorithm

2014-10-01T10:24:36Z

Cuozzo: /* Induction step */

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

==Abstract view==
'''Invariant:''' After <math>i\ge 0</math> iterations:
# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.
# In ascending order, <math>I</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==
'''Abstract view:''' <math>R</math> and <math>I</math> have to be empty.

'''Implementation:'''
# <math>R:=\emptyset</math>
# <math>I:=\emptyset</math>

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

==Induction step==
'''Abstract view:'''
# For each start index in <math>I</math>, we decide whether this is still a candidate after we have seen <math>S[i]</math>. If not, we remove this start index from <math>I</math>.
# Afterwards:
## If <math>S[i]=T[1]</math>, <math>i</math> is a new candidate and is thus appended at the tail of <math>I</math>.
## If start index <math>i-m+1</math> is at the head of <math>I</math>, this start index is removed from <math>I</math> and appended at the tail of <math>R</math>.

'''Implementation:''' Obvious.

'''Correctness:'''
# Due to the second invariant, the induction hypothesis implies that all elements of <math>I</math> immediately before the <math>i</math>-th iteration must be from the set <math>\{i-m+1,...,i-1\}</math>. Therefore, if <math>i-m+1</math> is in <math>I</math>, it is the smallest element. Since the elements of <math>I</math> are in ascending order, <math>i-m+1</math> is then at the head of <math>I</math>.
# A start index <math>j</math> in <math>I</math> is to be dropped if, and only if, it turns out not to be a promising candidate anymore. As the induction hypothesis implies <math>(S[j],...,S[i-1])=(T[1],...,T[i-j])</math>, this is the case if, and only if, <math>S[i]\neq T[i-j+1]</math>.
# Clearly, it would be incorrect to transfer any element of <math>I</math> except <math>i-m+1</math> to <math>R</math>. Thus, we are right to focus on <math>i-m+1</math> in Step 2.2. Now, <math>i-m+1</math> is in <math>I</math> if, and only if, (1) it was present immediately before the <math>i</math>-th iteration and (2) it has survived the first step of the <math>i</math>-th iteration. The induction hypothesis implies <math>(S[i-m+1],...,S[i-1])=(T[1],...,T[m-1])</math>, so it is correct to transfer <math>i-m+1</math> to <math>R</math> if, and only if, it is <math>S[i]=T[m]</math> as well.
# Clearly, it would also be incorrect to add any element to <math>I</math> except <math>i</math>. So we are right to focus on <math>i</math> in Step 2.1. Obviously, all elements of <math>I</math> are less than <math>i</math>, so we are also right to append <math>i</math> at the tail of <math>I</math> in case <math>S[i]=T[1]</math>.

==Complexity==

==Further information==

Simple string matching algorithm

2014-10-01T10:06:00Z

Cuozzo: /* Induction basis */

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

==Abstract view==
'''Invariant:''' After <math>i\ge 0</math> iterations:
# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.
# In ascending order, <math>I</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==
'''Abstract view:''' <math>R</math> and <math>I</math> have to be empty.

'''Implementation:'''
# <math>R:=\emptyset</math>
# <math>I:=\emptyset</math>

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

==Induction step==

==Complexity==

==Further information==

Simple string matching algorithm

2014-10-01T09:59:59Z

Cuozzo: /* Abstract view */

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

==Abstract view==
'''Invariant:''' After <math>i\ge 0</math> iterations:
# In ascending order, <math>R</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie completely in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>R</math> contains the start indexes in the range <math>S[1],...,S[i-m+1]</math>, where <math>m</math> is the length of <math>T</math>.
# In ascending order, <math>I</math> contains exactly the start indexes of all occurrences of <math>T</math> in <math>S</math> that lie partially in the substring <math>(S[1],...,S[i])</math> of <math>S</math>. In other words, <math>I</math> contains the start indexes in the range <math>S[i-m+2],...,S[i]</math>.

'''Variant:''' <math>i</math> increases by <math>1</math>.

'''Break condition:''' <math>i=n</math>.

==Induction basis==

==Induction step==

==Complexity==

==Further information==

Simple string matching algorithm

2014-10-01T09:51:50Z

Cuozzo:

__NOTOC__
[[Category:Algorithm]]
[[Category:Main Algorithm]]
'''Algorithmic problem:''' [[One-dimensional string matching]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data''' A [[FIFO queue]] <math>I</math> of natural numbers, which always contains the start indexes of all occurrences of <math>T</math> in <math>S</math> that have been seen only partially thus far.

==Abstract view==

==Induction basis==

==Induction step==

==Complexity==

==Further information==

Numbers

2014-10-01T09:41:50Z

Cuozzo:

[[Category:Checkup]]
[[Category:Background]]
==Natural numbers==
<math>\mathbb{N}</math> denotes the set of positive integral numbers:

: <math>\mathbb{N} := \{1,2,3,...\}</math>

: <math>\mathbb{N}_{0} := \mathbb{N} \cup \{0\}</math>

We say that <math>\mathbb{N}_{0}</math> is the set of all '''natural numbers'''.

==Real numbers==
<math>\mathbb{R}</math> denotes the set of all '''real numbers'''. We also define the following sets:

: <math>\mathbb{R}^+ := \{x\mid x\in \mathbb{R},x>0\}</math> (set of all positive real numbers)
: <math>\mathbb{R}^+_0 := \mathbb{R}^+ \cup \{ 0 \}</math>

Additionally <math>+\infty</math> or, for short, <math>\infty</math>, denotes the unique number that is larger than all real numbers. Analogously, <math>-\infty</math> is the unique number that is smaller than all real numbers. By convention the following properties hold for all <math>x\in\mathbb{R}</math>:
: <math>x+\infty = \infty + x = \infty + \infty = \infty</math>

We say that <math>+\infty</math> and <math>-\infty</math> are the '''neutral elements''' of the minimum and maximum operation, respectively:
: <math>\min\emptyset = +\infty</math>
: <math>\max\emptyset = -\infty</math>

==Empty sets and intervals==
# For <math>i>j</math>, we define <math>\{ x_i,...,x_j\}:=\emptyset</math>.
# For <math>a>b</math>, we define <math>[a,b]:=\emptyset</math>

==Boolean==
<math>\mathbb{B}</math> denotes the set of binary truth values ('''Boolean''' values).
: <math>\mathbb{B}:=\{ true,false\}</math>

Heap as array: insert

2014-10-01T09:06:31Z

Cuozzo:

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category: Method of an implementation of a data structure]]
'''Algorithmic problem:''' [[Bounded priority queue|Bounded priority queue: insert]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A '''current index''' <math>k \in \mathbb{N}</math>.
# An auxiliary index <math>k' \in \mathbb{N}</math>.
# A number <math>ID</math> storing the ID to be eventually returned for the new heap element.

==Abstract view==
'''Invariant:''' Before and after each iteration:
# The value of <math>N</math> is one higher than immediately before the call to this method; one heap item has been inserted, and the key of this heap item is the input key.
# The heap property is fulfilled for all heap items except for the one at position <math>\lfloor k/2 \rfloor</math> (for that one, the heap property may or may not be fulfilled).

'''Variant:''' <math>k</math> is at least halved.

'''Break condition:''' One of the following two conditions is fulfilled:
# either it is <math>k = 1</math>;
# or, otherwise, the heap property is fulfilled by the heap item at position <math>\lfloor k/2 \rfloor</math>.

==Induction basis==
'''Abstract view:'''
# Attach the new heap item at position <math>N + 1</math>.
# Increase <math>N</math> by one.
# Take a position <math>i</math> from <math>Unused</math> and associate <math>Positions[i]</math> with the new heap item.

'''Implementation:'''
# Set <math>N:=N+1</math>.
# Set <math>TheHeap[N].key:=K</math>.
# Extract some <math>i</math> from <math>Unused</math>.
# Set <math>Positions[i]:=N</math>.
# Set <math>TheHeap[N].ID:=i</math>.
# Set <math>ID:=i</math>.

'''Proof:''' Obvious.

==Induction step==
'''Abstract view:'''
# If the current heap item has no parent or the parent fulfills the heap property, terminate the algorithm.
# Otherwise, exchange the current heap item with its parent. The index <math>k</math> follows the heap item.

'''Implementation:'''
# If <math>k=1</math>, terminate the algorithm and return <math>ID</math>.
# Set <math>k' := \lfloor k/2 \rfloor </math>.
# If <math>TheHeap[k'].key \le TheHeap[k].key</math>, terminate the algorithm and return <math>ID</math>.
# Swap <math>Positions[TheHeap[k].ID]</math> and <math>Positions[TheHeap[k'].ID]</math>.
# Swap <math>TheHeap[k].key</math> and <math>TheHeap[k'].key</math>.
# Swap <math>TheHeap[k].ID</math> and <math>TheHeap[k'].ID</math>.
# Set <math>k := k'</math>.

'''Correctness:''' Obviously, the heap item at the old <math>k</math> now fulfills the heap property, and the new <math>k</math> is now the only index that does not necessarily fulfill it.

==Complexity==
'''Statement:''' The asymptotic complexity is logarithmic in the worst case.

'''Proof:''' Obvious.

==Further information==
Note that the loop is identical to the loop in [[Heap as array: decrease key]].

Heap as array: extract minimum

2014-10-01T09:05:53Z

Cuozzo:

__NOTOC__
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Method of an implementation of a data structure]]
'''Algorithmic problem:''' [[Bounded priority queue|Bounded priority queue: extract minimum]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''
# A '''current index''' <math>k \in \mathbb{N}</math>.
# An auxiliary index <math>k' \in \mathbb{N}</math>

==Abstract view==
'''Invariant:''' Before and after each iteration:
# The value of <math>N</math> is one less than immediately before the call to this method; one heap item has been removed, namely the one that was at position <math>1</math>
# The heap property is fulfilled for all heap items except for the one at index <math>k</math> (for that one, the heap property may or may not be fulfilled).

'''Variant:''' <math>k</math> is at least doubled.

'''Break condition:''' The heap property is fulfilled by <math>k</math> (note that the heap property is trivially fulfilled by <math>k</math> once <math>2 * k > N</math>).

==Induction basis==
'''Abstract view:'''
# Overwrite <math>TheHeap[1]</math> by <math>TheHeap[N]</math>.
# Decrease <math>N</math> by one.
# Update <math>Positions</math> and <math>Unused</math> accordingly.

'''Implementation:'''
# Insert <math>TheHeap[1].ID</math> in <math>Unused</math>.
# Set <math>TheHeap[1].key := TheHeap[N].key</math>.
# Set <math>TheHeap[1].ID := TheHeap[N].ID</math>.
# Set <math>N := N-1</math>.
# Set <math>Positions[TheHeap[1].ID] := 1</math>.
# Set <math>k := 1</math>.

'''Proof:''' Obvious.

==Induction step==
'''Abstract view:'''
# If the current heap item fulfills the heap property, terminate the algorithm.
# Otherwise, exchange the current heap item with one of its children, viz. the smaller one (ties arbitrarily broken). The index <math>k</math> follows the heap item.

'''Implementation'''
# If <math>2*k>N</math>, terminate the algorithm.
# If <math>2*k+1>N</math>, set <math>k' := 2*k</math>.
# Otherwise, set
## <math>k' := 2*k</math> if <math>TheHeap[2k] \le TheHeap[2k+1]</math>;
## <math>k' := 2*k+1</math>, otherwise.
# If <math>TheHeap[k] \le TheHeap[k']</math>, terminate the algorithm.
# Swap <math>Positions[TheHeap[k].ID]</math> and <math>Positions[TheHeap[k'].ID]</math>.
# Swap <math>TheHeap[k].key</math> and <math>TheHeap[k'].key</math>.
# Swap <math>TheHeap[k].ID</math> and <math>TheHeap[k'].ID</math>.
# Set <math>k := k'</math>.

'''Correctness:''' Obviously, the heap item at the former position <math>k</math> now fulfills the heap property, and the new <math>k</math> is now the only index that does not necessarily fulfill it.

==Complexity==
'''Statement:''' The asymptotic complexity is logarithmic in the worst case.
'''Proof:''' Obvious.

==Further information==