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.
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 |
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent