Implementation of some well-known algorithms and data structures.
Inside the folders there are some implementations of the following algorithms:
-
Graphs
- Breadth first search
- Depth first search
- Dijkstra
- Topological sort
- Two coloring
- Cycle detection
-
Matrices
- Matrix multiplication
- Matrix chain multiplication
-
Sorting
- Bubble sort
- Insertion sort
- Selection sort
- Quicks sort
- Heap sort
- Counting sort
-
Trees
- Binary search tree
- Red-black tree
-
Strings
- Suffix tree
- Suffix array
- Pattern matching
- Counting pattern repetitions
- Longest repeating factor
- Longest suffix prefix
Some comments:
- For some algorithms on graphs an adjacency list representation is implemented, for some others an adjacency matrix representation
- Naïve, divide-et-conquera and Strassen's algorithms are implemented for matrix multiplication
- Naïve and dynamic programming solutions are implemented for chain matrix multiplication
- Insertion and deletion of a node, search of the maximum, minimum and of an arbitrary value are implemented for the tree data structures
- Naïve and Knuth-Morris algorithms are implemented for pattern matching
- The suffix tree is built using both brutal construction and McCreight`s algorithm