Main Page: Difference between revisions
Jump to navigation
Jump to search
m (→Problems) |
No edit summary |
||
| (45 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
=== Notations === | === Notations === | ||
* [[ | * [[Big O notation]] | ||
* [[L' Hospital]] | * [[L' Hospital]] | ||
* [[Master theorem]] | * [[Master theorem]] | ||
* [[Asymptotic comparison of functions]] | |||
=== Problems === | === Problems === | ||
* [[Maximum matching problem]] | * [[Matchings in graphs#Cardinality-maximal matching|Maximum matching problem]] | ||
* [[Max-Flow Problems]] | * [[Max-Flow Problems]] | ||
* [[Min-Cost Flow Problems]] | * [[Min-Cost Flow Problems]] | ||
| Line 32: | Line 12: | ||
** [[All pairs shortest paths]] | ** [[All pairs shortest paths]] | ||
*** [[Floyd-Warshall]] | *** [[Floyd-Warshall]] | ||
*** [[Bellman-Ford]] | *** [[Bellman-Ford]] (DONE) | ||
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford) | *** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford) | ||
** [[Single source shortest paths]] | ** [[Single source shortest paths]] | ||
*** [[Dijkstra]] | *** [[Dijkstra]] | ||
** [[Single source single target shortest paths]] | ** [[Single source single target shortest paths]] | ||
*** [[A*]] | *** [[A*]] (Empty in old wiki) | ||
* [[Maximum spanning forest]] | * [[Maximum spanning forest]] | ||
* [[Problems on Sequences]] | * [[Problems on Sequences]] | ||
** [[Basic Problems on Sequences]] | ** [[Basic Problems on Sequences]] | ||
*** [[Find an element in a sequence]] | *** [[Find an element in a sequence]] (DONE) | ||
*** [[Insert an element in a sequence]] | *** [[Insert an element in a sequence]] (Empty in old wiki?!) | ||
*** [[Median]] | *** [[Median]] (DONE) | ||
*** [[Merging two sorted sequences]] | *** [[Merging two sorted sequences]] (DONE) | ||
** [[Pattern Matching]] | ** [[Pattern Matching]] | ||
*** [[One-dimensional string matching]] (DONE) | *** [[One-dimensional string matching]] (DONE) | ||
*** [[String matching]] (DONE) | *** [[String matching]] (DONE) | ||
** [[Sorting]] | ** [[Sorting]] | ||
*** [[Sorting based on pairwise comparison]] | *** [[Sorting based on pairwise comparison]] (DONE) | ||
*** [[Sorting Sequences of Strings]] | *** [[Sorting Sequences of Strings]] (DONE) | ||
=== Coding Basics === | === Coding Basics === | ||
* [[ | * [[Inheritance]] | ||
* [[Generics]] | * [[Generics]] | ||
* [[Collections]] | * [[Collections]] | ||
| Line 65: | Line 45: | ||
=== Sorting Algorithms === | === Sorting Algorithms === | ||
* [[Bubble]] | * [[Bubble]] | ||
* [[Insertion | * [[Insertion sort]] | ||
* [[ | * [[Quicksort]] | ||
* [[ | * [[Bubblesort]] | ||
* [[ | * [[Mergesort]] | ||
* [[ | * [[Bucketsort]] | ||
* [[Selection | * [[Selection sort]] | ||
* [[ | * [[Bogosort]] | ||
=== Search Algorithms === | === Search Algorithms === | ||
* [[Binary | * [[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 === | === Tree Algorithms === | ||
* [[Depth- | * [[Depth-first search]] | ||
* [[Breadth- | * [[Breadth-first search]] | ||
* [[B- | * [[B-tree: find]] | ||
* [[B- | * [[B-tree: minimum]] | ||
* [[B- | * [[B-tree: maximum]] | ||
* [[B- | * [[B-tree: insert]] | ||
* [[B- | * [[B-tree: insert and rearrange]] | ||
* [[B- | * [[B-tree: merge two siblings]] | ||
* [[B- | * [[B-tree: remove]] | ||
* [[B- | * [[B-tree: shift key to sibling]] | ||
* [[B- | * [[B-tree: split]] | ||
* [[Binary search tree: find]] | |||
* [[Binary search tree: minimum]] | |||
* [[Binary | * [[Binary search tree: maximum]] | ||
* [[Binary | * [[Binary search tree: insert]] | ||
* [[Binary | * [[Binary search tree: remove]] | ||
* [[Binary | * [[Binary search tree: remove node]] | ||
* [[Binary | * [[Binary search tree: traverse]] | ||
* [[Binary | |||
* [[Binary | |||
=== Graph Theory === | === Graph Theory === | ||
* [[Directed | * [[Directed graph]] | ||
* [[Bipartite | * [[Bipartite graph|Bipartite graph]] (DONE) | ||
* [[k-partite | * [[k-partite graph]] | ||
* [[Negative | * [[Negative paths]] | ||
=== Graph Algorithms === | === Graph Algorithms === | ||
| Line 108: | Line 104: | ||
* [[Kruskal]] | * [[Kruskal]] | ||
* [[Prim]] | * [[Prim]] | ||
* [[Bellman-Ford]] | * [[Bellman-Ford]] (DONE) | ||
* [[Floyd-Warshall]] | * [[Floyd-Warshall]] | ||
* [[Union Find]] | * [[Union Find]] | ||
| Line 114: | Line 110: | ||
* [[Alternating paths algorithm]] | * [[Alternating paths algorithm]] | ||
* [[Johnson]] | * [[Johnson]] | ||
* [[Union-find with disjoint trees: find]] | |||
* [[Union-find with lists: unite]] | |||
* [[Max-flow min-cut]] | |||
=== Flow Algorithms === | === Flow Algorithms === | ||
* [[Ford-Fulkerson]] | * [[Ford-Fulkerson]] | ||
=== Data Structures === | * [[Edmonds-Karp]] | ||
* [[Linked | |||
* [[Array | === 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 - First Out]] | ||
* [[First In - | * [[First In - Last Out]] | ||
* [[Directed Tree]] | * [[Directed Tree]] | ||
* [[Decision Tree]] | * [[Decision Tree]] | ||
=== Other | === Other === | ||
* [[ | * [[Model computer]] | ||
Latest revision as of 15:13, 30 November 2020
Notations
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
- Single source single target shortest paths
- A* (Empty in old wiki)
- All pairs shortest paths
- 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
- Basic Problems on Sequences
Coding Basics
String Matching Algorithms
Sorting Algorithms
Search Algorithms
Auxillary Algorithms
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: 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
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
Abstract Data Structures
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