# DSA Roadmap

> A free static study site for Data Structures & Algorithms (CoSc3111, Addis Ababa University, 3rd year) in C++. It follows the official course outline at exam depth.

Core rule: Don't just watch: implement it yourself, then solve 2–3 problems.

Each topic is also available as raw Markdown by adding `.md` to its URL. The whole site as one file: https://dsa.fetehadin.com/llms-full.txt

## Chapter 01: Introduction to Data Structures

- [1.1 What Is a Data Structure?](https://dsa.fetehadin.com/learn/what-is-a-data-structure.md): A data structure is a way of organising data in memory so the operations you need are fast. Learn how they are classified and what makes a good one.
- [1.2 ADTs & Abstraction](https://dsa.fetehadin.com/learn/adt-and-abstraction.md): An Abstract Data Type says WHAT operations exist; a data structure says HOW they are built. Separating the two is the key idea of this course.
- [1.3 Arrays & 2-D Arrays (Review)](https://dsa.fetehadin.com/learn/arrays.md): Arrays store items side by side in memory, which is why reading any index is instant. 2-D arrays are stored row by row.

## Chapter 02: Algorithm & Algorithm Analysis

- [2.1 Algorithms & Their Properties](https://dsa.fetehadin.com/learn/algorithm-properties.md): An algorithm is a finite, unambiguous sequence of steps that solves a problem. Learn the 11 properties every correct algorithm must have.
- [2.2 Measuring Efficiency](https://dsa.fetehadin.com/learn/analysis-approaches.md): Empirical vs theoretical analysis, qualitative vs quantitative, the three classic avoidable inefficiencies, and the time–space trade-off.
- [2.3 Counting Time Units](https://dsa.fetehadin.com/learn/counting-time-units.md): Turn code into a formula T(n) using the instructor's counting rules. Loops become sums, and nested loops multiply.
- [2.4 Best, Average & Worst Case](https://dsa.fetehadin.com/learn/best-average-worst.md): The same algorithm can be fast or slow depending on the input. We analyse the best, average and worst case, and usually report the worst.
- [2.5 Asymptotic Notation & Big-O Proofs](https://dsa.fetehadin.com/learn/asymptotic-notation.md): O, Ω, Θ, o and ω describe how fast T(n) grows for large n. Learn the definitions, the order of growth, and how to prove f(n) = O(g(n)) by finding c and k.

## Chapter 03: Simple Sorting & Searching

- [3.1 Selection Sort](https://dsa.fetehadin.com/learn/selection-sort.md): Find the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons.
- [3.2 Bubble Sort](https://dsa.fetehadin.com/learn/bubble-sort.md): Compare neighbours and swap them if they are out of order. After each pass the biggest remaining item has "bubbled" to the end.
- [3.3 Insertion Sort](https://dsa.fetehadin.com/learn/insertion-sort.md): Grow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data.
- [3.4 Pointer Sort](https://dsa.fetehadin.com/learn/pointer-sort.md): When records are big, don't move them. Sort an array of pointers (or indices) to the records instead, and only small addresses get swapped.
- [3.5 Linear Search](https://dsa.fetehadin.com/learn/linear-search.md): Check every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n).
- [3.6 Binary Search](https://dsa.fetehadin.com/learn/binary-search.md): On a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n).
- [3.7 Recursion Primer](https://dsa.fetehadin.com/learn/recursion.md): A function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Ch 6) and merge/quick sort (Ch 8).

## Chapter 04: Linked Lists

- [4.1 Pointers, new/delete & the Heap](https://dsa.fetehadin.com/learn/pointers-and-memory.md): A pointer holds an address. new asks the heap for memory that lives until you delete it. Master this and linked lists become easy.
- [4.2 Singly Linked List](https://dsa.fetehadin.com/learn/singly-linked-list.md): Nodes on the heap, each pointing to the next. Insert at front, end or a position, delete by value, search and traverse, plus the dummy-node trick and the classic pitfalls.
- [4.3 Doubly Linked List](https://dsa.fetehadin.com/learn/doubly-linked-list.md): Each node points both forward and backward. You can walk in both directions and delete a node knowing only its address, at the cost of one extra pointer per node.

## Chapter 05: Stacks & Queues

- [5.1 Stacks with an Array](https://dsa.fetehadin.com/learn/stack-array.md): Last in, first out. The stack ADT (push, pop, peek, isEmpty, isFull) built on a fixed array with a top index, plus overflow and underflow.
- [5.2 Stacks with a Linked List](https://dsa.fetehadin.com/learn/stack-list.md): The same stack ADT, but the top is the head of a linked list. No fixed capacity, push and pop stay O(1), and the bracket-matching application.
- [5.3 Queues with an Array](https://dsa.fetehadin.com/learn/queue-array.md): First in, first out. Why a naive array queue makes dequeue O(n), how a front index makes it O(1), and the wasted-slot problem that leads to the circular queue.
- [5.4 Queues with a Linked List](https://dsa.fetehadin.com/learn/queue-list.md): Keep two pointers, front and rear. Enqueue at the rear and dequeue at the front, both O(1), with no capacity limit.
- [5.5 Circular Queue](https://dsa.fetehadin.com/learn/circular-queue.md): Let front and rear wrap around with the modulo operator, so freed slots are reused. All operations O(1) on a fixed array.
- [5.6 std::stack, std::queue & std::deque](https://dsa.fetehadin.com/learn/stl-stack-queue.md): The standard library versions you will use in real code and on LeetCode, their method names, and the classic traps (pop returns void, empty checks).

## Chapter 06: Trees

- [6.1 Binary Trees & Tree Terms](https://dsa.fetehadin.com/learn/binary-trees.md): Root, parent, child, leaf, sibling, depth, height, level, subtree; full, complete and perfect binary trees; and the Node struct with recursive count and height.
- [6.2 Binary Search Tree](https://dsa.fetehadin.com/learn/bst.md): Left is smaller, right is bigger. Insert, search, find min and max by walking one path, and why the tree's shape decides whether that is O(log n) or O(n).
- [6.3 BST Delete (3 Cases)](https://dsa.fetehadin.com/learn/bst-delete.md): Deleting a leaf, a node with one child, and a node with two children by copying the inorder successor. The most-asked BST exam question.
- [6.4 Tree Traversals](https://dsa.fetehadin.com/learn/tree-traversals.md): Preorder, inorder and postorder (depth-first, recursive) and level order (breadth-first, with a queue). Know them by hand and in code.
- [6.5 General Trees (Left-Child, Right-Sibling)](https://dsa.fetehadin.com/learn/general-trees.md): Trees where a node can have any number of children, stored with only two pointers per node using the left-child/right-sibling representation.

## Chapter 07: Graphs

- [7.1 Graph Terminology](https://dsa.fetehadin.com/learn/graph-terms.md): Vertices and edges, adjacency, degree, paths, cycles, connected graphs, weighted graphs, and how a tree is a special graph.
- [7.2 Adjacency Matrix & Adjacency List](https://dsa.fetehadin.com/learn/graph-representation.md): Two ways to store a graph in memory, what each costs, and when to choose which.
- [7.3 Directed Graphs](https://dsa.fetehadin.com/learn/directed-graphs.md): One-way edges, in-degree and out-degree, directed paths and cycles, and how the matrix and list change.
- [7.4 BFS & DFS](https://dsa.fetehadin.com/learn/bfs-dfs.md): Breadth-first search with a queue, depth-first search with recursion or a stack, the visited array, and O(V + E).

## Chapter 08: Advanced Sorting & Searching

- [8.1 Shell Sort](https://dsa.fetehadin.com/learn/shell-sort.md): Insertion sort on items a gap apart, with the gap shrinking to 1. Far-away items move in big jumps, so the final insertion sort has little work left.
- [8.2 Quick Sort](https://dsa.fetehadin.com/learn/quick-sort.md): Pick a pivot, partition so smaller items go left and bigger items go right, then sort each side recursively. Average O(n log n), worst O(n²).
- [8.3 Merge Sort](https://dsa.fetehadin.com/learn/merge-sort.md): Split the array in half, sort each half recursively, then merge the two sorted halves. Always O(n log n), stable, but needs O(n) extra space.
- [8.4 Heap Sort](https://dsa.fetehadin.com/learn/heap-sort.md): Build a max-heap in the array, then repeatedly swap the root (the largest item) to the end and sift down. O(n log n) in every case, in-place.
- [8.5 Hashing Basics](https://dsa.fetehadin.com/learn/hashing.md): A hash function turns a key into an array index, so search is O(1) on average. Collisions, separate chaining, linear probing and the load factor.

## Level Up (optional, not on the exam)

- [LU.1 Two Pointers](https://dsa.fetehadin.com/learn/two-pointers.md): Two indices that move toward each other (or in the same direction) to replace an O(n²) pair search with one O(n) pass.
- [LU.2 Sliding Window](https://dsa.fetehadin.com/learn/sliding-window.md): Keep a running answer for a contiguous range, adding the item that enters and removing the one that leaves, instead of recomputing every window.
- [LU.3 Prefix Sum](https://dsa.fetehadin.com/learn/prefix-sum.md): Precompute running totals once in O(n), then answer any range-sum query with one subtraction in O(1).
- [LU.4 Fast & Slow Pointers](https://dsa.fetehadin.com/learn/fast-slow-pointers.md): Two pointers moving through a linked list at different speeds find the middle, the n-th node from the end, and cycles (Floyd's algorithm) in one pass with O(1) space.
- [LU.5 Monotonic Stack](https://dsa.fetehadin.com/learn/monotonic-stack.md): A stack kept in sorted (decreasing) order answers "next greater element" and "how far away is it" for every index in one O(n) pass.

## Other pages

- [Labs](https://dsa.fetehadin.com/labs)
- [Glossary](https://dsa.fetehadin.com/glossary)
- [Big-O table](https://dsa.fetehadin.com/big-o)
- [How to use this guide](https://dsa.fetehadin.com/guide)