This repository is a comprehensive collection of Java and Python implementations of fundamental algorithms and data structures, inspired by the curriculum of Princeton University. It serves as an educational resource for understanding and applying key concepts in computer science, with an emphasis on applications and scientific performance analysis.
The repository is organized into two main parts:
Covers basic data structures and algorithms for sorting and searching, including:
- Union-Find
- Binary Search
- Stacks, Queues, Bags
- Various Sorting Algorithms
- Binary Heaps
- Binary Search Trees and Red-Black Trees
- Hash Tables
- Geometric Algorithms and kd-Trees
Focuses on advanced topics in graph theory and string processing, including:
- Graph Algorithms
- String-Processing Algorithms
- Compression and Encoding Algorithms
- Reductions and Intractability
| Topic | Data Structures and Algorithms | Part |
|---|---|---|
| Data Types | stack, queue, bag, union-find, priority queue | Part 1 |
| Sorting | quicksort, mergesort, heapsort | |
| Searching | BST, red-black BST, hash table | |
| Graphs | BFS, DFS, Prim, Kruskal, Dijkstra | Part 2 |
| Strings | radix sorts, tries, KMP, regexps, data compression | |
| Advanced | B-tree, suffix array, maxflow |
| Implementation | Worst-case cost (after N inserts) | Average case (after N random inserts) | Ordered iteration? | Key interface | ||||
|---|---|---|---|---|---|---|---|---|
| search | insert | delete | search hit | insert | delete | |||
| Sequential search (unordered list) | N | N | N | N/2 | N | N/2 | no | equals() |
| Binary search (ordered array) | lg N | N | N | lg N | N/2 | N/2 | yes | compareTo() |
| BST | N | N | N | 1.39 lg N | 1.39 lg N | sqrt(N) | yes | compareTo() |
| 2-3 tree | c lg N | c lg N | c lg N | c lg N | c lg N | c lg N | yes | compareTo() |
| Red-black BST | 2 lg N | 2 lg N | 2 lg N | 1.00 lg N* | 1.00 lg N* | 1.00 lg N* | yes | compareTo() |
* exact value of coefficient unknown but extremely close to 1
| Algorithm | Inplace? | Stable? | Worst | Average | Best | Remarks |
|---|---|---|---|---|---|---|
| Selection | ✔️ | N / 2 | N / 2 | N / 2 | N exchanges | |
| Insertion | ✔️ | ✔️ | N / 2 | N / 4 | N | Use for small N or partially ordered |
| Shell | ✔️ | N^2 | n^1.25 | N | Tight code, subquadratic | |
| Merge | ✔️ | N lg N | N lg N | N lg N | N log N guarantee, stable | |
| Quick | ✔️ | N / 2 | 2 N ln N | N lg N | Fastest in practice | |
| 3-way Quick | ✔️ | ✔️ | N / 2 | 2 N ln N | N | Improves quicksort in presence of duplicate keys |
| Ideal | ✔️ | ✔️ | N lg N | N lg N | N lg N | Holy sorting grail |
Each directory within this repository corresponds to a specific topic or algorithm and contains both Java and Python implementations. Detailed README files are provided in each directory to explain the concepts, applications, and performance analysis of the implementations.
Contributions to this repository are welcome.
