dADS2
dBerLog
dDist
dOpSys
dRegAut
dSoftArk
dSik
IntMatMod
LinAlg
MatMod
AiBTaS
AiBS
dKS
DB2
VM
StrAlg
SV
P2PN
|
When I went to the exam, which was a written one, I had created an overview of the different
algorithms. This includes running time, pages in the book Introduction to Algorithms, Second edition
(Image on the right) and also what is required for the algorithm to work. I think it was usefull
since I did not have to look in the book where the algorithm was described when it was mentioned
in the paper I had to solve.
Currently missing is suffixtrees and suffixarrays. If you have the times for these algorithms, please let me know.
| Algorithm |
Pages |
Running time |
| Longest common subsequence | 353-355 | O(mn) |
| Optimal Binary Search Tree | 356-362 | Θ(n3) |
| Greedy-Activity-Selector | 376-378 | if already sorted Θ(n) |
| Huffman | 385-391 | O(nlgn) |
BFS
Directed and undirected graphs | 531-538 | O(V+E) |
DFS
Directed and undirected graphs | 540-547 | Θ(V+E) |
Topological-sort
Undirected graphs | 549-551 | Θ(V+E) |
Strongly-Connected-Components
Undirected graphs | 552-557 | Θ(V+E) |
| Minimum spanning trees | |
| Kruskal | 568-570 | O(ElgV) |
| Prim | 570-573 | | Binary heap | Fibonacci heap | | O(ElgV) | O(E+VlgV) |
|
| Single source shortest paths | |
Bellman-Ford
Weighed directed with negative weights but no negative cycles | 588-591 | O(VE) |
DAG-Shortest Path
Directed Accyclic Graph | 592-595 | Θ(V+E) |
Dijkstra
Weighed directed with no negative weights | 595-599 | | Array | Binary heap | Fibonacci heap | | O(V2) | O(ElgV) | O(E+VlgV) |
|
| All pairs shortest paths
(directed graphs with negative weigts but no negative cycles) | |
| Floyd Warshall | 629-632 | Θ(V3) |
| Transitive-closure | 632-634 | Θ(V3) |
| Maximum flow
(directed graphs) | |
| Ford Fulkerson | 651-660 | O(V|f*|) (|f*| = maximum flow) |
| Edmond-Karp | 660-663 | O(VE2) |
| Matrix multiplication | |
Strassen
On a n×n matrix | 735-741 | O(n2.81)
There is a O(n2.376) See p. 741 |
String pattern matching
| Algorithm |
Pages |
Preproccesing |
Matching |
| Naive | 909-910 | 0 | O((n-m+1)m) |
| Rabin-Karp | 911-915 | Θ(m) | O((n-m+1)m) |
| Finite automaton | 916-922 | O(m|Σ|) | Θ(n) |
| Knuth-Morris-Pratt | 923-930 | Θ(m) | Θ(n) |
Please note that Finite automaton was not a part of the curriculum when I took the course.
|
|
Last modified 10. October 2016 |
foens Dont spam me @cs.au.dk
|
|
