A complementary resource for learning fundamental data structures and algorithms. Aligned with CS2040S taught by Prof Seth Gilbert at NUS.
Each topic includes implementation, intuition, complexity analysis, and practical considerations. Useful for:
- CS2040S students - Supplement lecture content with working implementations
- Interview prep - Review fundamental DSA topics with clear explanations
- CS students - Quick refresher on core concepts
Developed by CS2040S Teaching Assistants and alumni under Prof Seth's guidance.
| Structure | Description |
|---|---|
| AVL Tree | Self-balancing BST with height-balance property |
| B-Tree | Self-balancing tree optimized for disk access |
| Binary Search Tree | Ordered tree structure |
| Disjoint Set / Union Find | Quick Find, Weighted Union with path compression |
| Hash Set | Chaining, Open Addressing |
| Heap | Binary max heap |
| Linked List | Singly linked list with sorting |
| LRU Cache | Hash map + doubly linked list |
| Queue | Deque, Monotonic Queue |
| Red-Black Tree | Self-balancing BST with color invariants |
| Segment Tree | Range queries with point updates |
| Stack | LIFO with monotonic stack discussion |
| Trie | Prefix tree for string operations |
| Algorithm | Variants |
|---|---|
| Bubble Sort | Basic comparison sort |
| Insertion Sort | Efficient for small/nearly sorted arrays |
| Selection Sort | Simple O(n²) sort |
| Merge Sort | Recursive, Iterative |
| Quick Sort | Hoare's, Lomuto's, Paranoid, 3-way |
| Counting Sort | Integer sorting in O(n + k) |
| Radix Sort | Digit-by-digit sorting |
| Cyclic Sort | Simple, Generalized |
| Algorithm | Description |
|---|---|
| Binary Search | Standard and templated versions |
| Minimum Spanning Tree | Prim's, Kruskal's |
| Orthogonal Range Searching | Range trees for multi-dimensional queries |
| Algorithm | Description |
|---|---|
| KMP | Knuth-Morris-Pratt pattern matching |
Click to expand syllabus mapping
- Basic Structures: Linked List, Stack, Queue
- Binary Search: Peak finding, templated search
- Sorting: Bubble, Insertion, Selection, Merge, Quick, Counting, Radix
- Trees: BST, AVL, Trie, B-Tree, Segment Tree, Red-Black Tree, Orthogonal Range Searching
- Binary Heap
- Disjoint Set / Union Find
- Hashing
- Graphs: BFS, DFS, Bellman-Ford, Dijkstra, Topological Sort (coming soon)
- Minimum Spanning Tree: Prim, Kruskal
git clone https://github.com/4ndrelim/data-structures-and-algorithms.git
cd data-structures-and-algorithms
./gradlew clean testFor detailed setup with IntelliJ IDEA and Java SDK configuration, see the Developer Guide.
Browse implementations directly on GitHub, or clone locally to experiment. See the scripts folder for running algorithms with custom inputs.
While we have verified correctness, there may be discrepancies with current lecture content. Please raise issues or consult your TA if you spot any concerns.
See the team!