# 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)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://andreas-3.gitbook.io/data-structures-and-algorithms/readme.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.