Java Implementations of algorithms and data structures learned in my first year at ETH Zurich. The primary goal was learning how the different algorithms work, hence I decided to (partially) avoid importing external libraries.
![Title Alt text](https://github.com/wallpaper.jpg?raw=true)
In this list we mention the implemented algorithms, together with their goal and runtime. In the graphs repository, you may find additional implementations using different data structures and no imports.
Algorithm |
Goal |
Runtime |
Articulation Nodes |
Find nodes that ensure graph connectivity. |
O(n+m) |
BFS |
Perform Breadth-First-Search on the graph. |
O(n+m) |
Bellman Ford |
One-to-all shortest path, even with negative weights. |
O(nm) |
DFS |
Perform Depth-First-Search on the graph. |
O(n+m) |
Dijkstra |
One-to-all shortest path, weights must be non-negative. |
O(n log n + m) (with Fibonacci-Heaps, this version is less efficient) |
Euler Tour |
Decide if the graph contains an Euler Tour. |
O(m) |
Floyd Warshall |
All-to-all shortest path. |
O(n^3) |
Kruskal |
MST by applying the blue rule. |
O(m log m) |
Prim |
MST by applying the blue/ red rule. |
O(m log n) |
Topological Sorting |
Determine if the graph has a topological order |
O(n + m) |
Algorithm |
Key Idea |
Runtime |
Linear Search |
Check every element. |
O(n) (worst-case) |
Binary Search |
Searching in a dictionary of a foreign language. |
O(log n) (worst-case) |
Interpolation Search |
Searching in a dictionary when you have an estimate of the words distribution. |
O(log n) (worst-case) |
Exponential Search |
Find range and use binary search. |
O(log n) (worst-case) |
Algorithm |
Key Idea |
Runtime |
Bubble Sort |
Double for loop. |
O(n^2) (worst-case) |
Insertion Sort |
Sorting a deck of card. |
O(n^2) (worst-case) |
Selection Sort |
Pick the maximum of the unsorted part of the array and put it at the end. |
O(n^2) (worst-case) |
Merge Sort |
Divide and conquer. |
O(n log n) (worst-case) |
Quick Sort |
Use a (random) pivot to partition the array. |
O(n log n) average-case, but O(n^2) worst-case |
Data Structure |
Supported Operations |
Binary Search Tree |
Add, find, dele: everything O(h) (h is the height of the tree) |
Priority Queue |
Enque, Deque: both O(log n) |
Queue |
Enque, Deque: both O(1) |
Stack |
Push, Pop, Top: everything O(1) |
Union Find |
Find, Union: both O(log n) using path compression |