Main Page

News

• The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 12th October.
• The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/
• [math]\displaystyle{ LaTeX }[/math] available now!
• ToDo List added
• Every content has to be in English!
• 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 - ???

Look here for short/uncomplete Pages Special:ShortPages

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

Auxillary Algorithms

• Pivot partitioning by scanning

Manipulation

• Array list: find
• Array list: find at position
• Array list: insert at head
• Array list: insert at position
• Array list: number
• Array list: remove
• Doubly-linked list: insert at position
• Doubly-linked list: insert at tail
• Doubly-linked list: remove
• Find element in sequence iteratively
• Find element in sequence recursively
• Hashtable: find
• Hashtable: insert

Tree Algorithms

• Depth-first search
• Breadth-first search
• B-tree: find
• B-tree: minimum
• B-tree: maximum
• B-tree: insert
• B-tree: insert and rearrange
• B-tree: merge two siblings
• B-tree: remove
• B-tree: shift key to sibling
• B-tree: rotate
• B-tree: merge
• B-tree: split
• Binary search tree: find
• Binary search tree: minimum
• Binary search tree: maximum
• Binary search tree: insert
• Binary search tree: remove
• Binary search tree: remove node
• Binary search tree: traverse

Graph Theory

• Directed graph
• Bipartite graph (DONE)
• k-partite graph
• Negative paths

Graph Algorithms

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

Flow Algorithms

• Ford-Fulkerson

Abstract Data Structures

• Network Structures
  • Graph
  • Tree
• Sequence
  • Sorted sequence
  • Bounded priority queue
  • Linear sequence
  • Priority queue
  • Sorted sequence

Implementations of Abstract Data Structures

• Linked list
• Array list
• Binary search tree
• Doubly-linked list
• Heap as array (DONE (Heap as Array))
• Hashtable
• Multi-way search tree
• Red-black tree
• B-tree

???

• Min-Max Heaps
• First In - First Out
• First In - Ieast Out
• Directed Tree
• Decision Tree

Other

• Model computer

Other Algorithms (LOCKED)

• B*
• Cyclic redundancy check
• 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