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