# Introduction A complementary resource for learning fundamental data structures and algorithms. Aligned with [CS2040S](https://nusmods.com/courses/CS2040S/data-structures-and-algorithms) taught by [Prof Seth Gilbert](https://www.comp.nus.edu.sg/cs/people/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. If you find this resource helpful, consider giving the [GitHub repo](https://github.com/4ndrelim/data-structures-and-algorithms) a ⭐ — it helps others discover it! *** ## Data Structures | Structure | Description | | -------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | [AVL Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/avltree) | Self-balancing BST with height-balance property | | [B-Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/btree) | Self-balancing tree optimized for disk access | | [Binary Search Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/binarysearchtree) | Ordered tree structure | | [Disjoint Set / Union Find](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/disjointset) | [Quick Find](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/disjointset/quickfind), [Weighted Union](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/disjointset/weightedunion) with path compression | | [Fenwick-Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/fenwicktree) | AKA Binary Indexed Tree for prefix sum queries | | [Hash Set](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/hashset) | [Chaining](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/hashset/chaining), [Open Addressing](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/hashset/openaddressing) | | [Heap](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/heap) | Binary max heap | | [Linked List](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/linkedlist) | Singly linked list with sorting | | [LRU Cache](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/lrucache) | Hash map + doubly linked list | | [Queue](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/queue) | [Deque](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/queue/deque), [Monotonic Queue](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/queue/monotonicqueue) | | [Red-Black Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/rbtree) | Self-balancing BST with color invariants | | [Segment Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/segmenttree) | Range queries with point updates | | [Stack](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/stack) | LIFO with monotonic stack discussion | | [Trie](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/trie) | Prefix tree for string operations | ## Algorithms ### Sorting | Algorithm | Variants | | ----------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | [Bubble Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/bubblesort) | Basic comparison sort | | [Insertion Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/insertionsort) | Efficient for small/nearly sorted arrays | | [Selection Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/selectionsort) | Simple O(n²) sort | | [Merge Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/merge-sort/iterative) | [Recursive](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/merge-sort/recursive), [Iterative](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/merge-sort/iterative) | | [Quick Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/quicksort) | [Hoare's](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/quicksort/hoares), [Lomuto's](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/quicksort/lomuto), [Paranoid](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/quicksort/paranoid), [3-way](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/quicksort/threewaypartitioning) | | [Counting Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/countingsort) | Integer sorting in O(n + k) | | [Radix Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/radixsort) | Digit-by-digit sorting | | [Cyclic Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/cyclicsort) | [Simple](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/cyclicsort/simple), [Generalized](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/cyclicsort/generalised) | ### Searching | Algorithm | Description | | -------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------- | | [Binary Search](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/binarysearch) | Standard and [templated](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/binarysearch/binarysearchtemplated) versions | | [Orthogonal Range Searching](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/orthogonal-range-searching/onedim) | Range trees for multi-dimensional queries | ### Graph Algorithms | Algorithm | Description | | ------------------------------------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | [Graph Traversals](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph) | [BFS](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/bfs), [DFS](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/dfs) (recursive & iterative) | | [Dijkstra](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/dijkstra) | Single-source shortest path (non-negative weights) | | [Bellman-Ford](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/bellmanford) | Single-source shortest path (handles negative weights) | | [Floyd-Warshall](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/floydwarshall) | All-pairs shortest path | | [Topological Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/topologicalsort) | Linear ordering of DAG vertices (Kahn's algorithm) | | [Minimum Spanning Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/minimumspanningtree) | [Prim's](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/minimumspanningtree/prim), [Kruskal's](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/minimumspanningtree/kruskal) | ### String Algorithms | Algorithm | Description | | -------------------------------------------------------------------------------------------- | ----------------------------------- | | [KMP](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/patternfinding) | Knuth-Morris-Pratt pattern matching | *** ## CS2040S Syllabus Reference
Click to expand syllabus mapping 1. **Basic Structures**: [Linked List](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/linkedlist), [Stack](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/stack), [Queue](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/queue) 2. [**Binary Search**](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/binarysearch): Peak finding, [templated search](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/binarysearch/binarysearchtemplated) 3. **Sorting**: [Bubble](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/bubblesort), [Insertion](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/insertionsort), [Selection](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/selectionsort), [Merge](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/merge-sort/iterative), [Quick](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/quicksort), [Counting](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/countingsort), [Radix](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/sorting/radixsort) 4. **Trees**: [BST](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/binarysearchtree), [AVL](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/avltree), [Trie](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/trie), [B-Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/btree), [Segment Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/segmenttree), [Red-Black Tree](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/rbtree), [Orthogonal Range Searching](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/orthogonal-range-searching/onedim) 5. [**Binary Heap**](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/heap) 6. [**Disjoint Set / Union Find**](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/disjointset) 7. [**Hashing**](https://andreas-3.gitbook.io/data-structures-and-algorithms/data-structures/hashset) 8. [**Graphs**](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph): [BFS](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/bfs), [DFS](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/dfs), [Dijkstra](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/dijkstra), [Bellman-Ford](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/bellmanford), [Floyd-Warshall](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/floydwarshall), [Topological Sort](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/graph/topologicalsort) 9. [**Minimum Spanning Tree**](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/minimumspanningtree): [Prim](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/minimumspanningtree/prim), [Kruskal](https://andreas-3.gitbook.io/data-structures-and-algorithms/algorithms/minimumspanningtree/kruskal)