Algorithms

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.

Graph Theory

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)

Searching

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)

Sorting

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 Structures

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