🌍 Data Structure and Algorithm · subject

Data Structure and Algorithm Algorithms Syllabus

Q: What is in the Data Structure and Algorithm Algorithms syllabus?

Data Structure and Algorithm Algorithms is split into 10 chapters: Introduction to Algorithms, Basic Data Structures, Sorting Algorithms, Search Algorithms, Dynamic Programming, Greedy Algorithms, Backtracking, Divide and Conquer, String Algorithms and Advanced Algorithms. Together they contain 27 topics and 94 sub-topics.

Q: How many chapters are in Data Structure and Algorithm Algorithms?

10 chapters, containing 27 topics and 94 sub-topics. The largest chapter is Basic Data Structures, with 7 topics.

Q: Are there flashcards for Data Structure and Algorithm Algorithms?

Yes — a 50-card Algorithms deck, printed in full in the flashcards section of this page and available in the Examius app with spaced repetition. The free plan covers one exam of your choice, including its flashcards; Examius Pro, a one-time purchase, unlocks every other exam and deck.

The Algorithms syllabus for Data Structure and Algorithm in full: 10 chapters, 27 topics and 94 sub-topics, every one listed below, plus 50 Algorithms flashcards with answers.

10Chapters

27Topics

94Sub-topics

50Flashcards

Algorithms syllabus: all 10 chapters

Expand any chapter to see its topics and sub-topics.

Introduction to Algorithms
2 topics
- What is an Algorithm?
  - Definition and Characteristics
  - Importance of Algorithms
  - Algorithm vs Heuristic
- Algorithm Analysis
  - Time Complexity
  - Space Complexity
  - Big O Notation
  - Big Theta and Big Omega Notations
  - Best, Worst, and Average Case Analysis
  - Amortized Analysis
Basic Data Structures
7 topics
- Arrays
  - Definition and Operations
  - Dynamic Arrays
  - Multi-dimensional Arrays
- Linked Lists
  - Singly Linked List
  - Doubly Linked List
  - Circular Linked List
- Stacks
  - Definition and Operations
  - Applications of Stacks
- Queues
  - Definition and Operations
  - Circular Queue
  - Priority Queue
  - Deque (Double-ended Queue)
- Trees
  - Binary Trees
  - Binary Search Trees
  - AVL Trees
  - Red-Black Trees
  - B-Trees
  - Tries
- Graphs
  - Graph Representations
  - Graph Traversal (BFS, DFS)
  - Directed vs Undirected Graphs
  - Weighted vs Unweighted Graphs
- Hash Tables
  - Hash Functions
  - Collision Resolution Techniques
  - Applications of Hash Tables
Sorting Algorithms
2 topics
- Comparison-based Sorting
  - Bubble Sort
  - Selection Sort
  - Insertion Sort
  - Merge Sort
  - Quick Sort
  - Heap Sort
- Non-comparison-based Sorting
  - Counting Sort
  - Radix Sort
  - Bucket Sort
Search Algorithms
3 topics
- Linear Search
  - Simple Linear Search
  - Sentinel Linear Search
- Binary Search
  - Iterative Binary Search
  - Recursive Binary Search
- Search in Data Structures
  - Search in Linked Lists
  - Search in Trees
  - Search in Graphs
Dynamic Programming
2 topics
- Introduction to Dynamic Programming
  - Principle of Optimality
  - Overlapping Subproblems
  - Memoization vs Tabulation
- Classic DP Problems
  - Fibonacci Sequence
  - Knapsack Problem
  - Longest Common Subsequence
  - Matrix Chain Multiplication
  - Coin Change Problem
Greedy Algorithms
2 topics
- Introduction to Greedy Algorithms
  - Greedy Choice Property
  - Optimal Substructure
- Classic Greedy Problems
  - Activity Selection Problem
  - Huffman Coding
  - Kruskal's Algorithm
  - Prim's Algorithm
  - Dijkstra's Algorithm
Backtracking
2 topics
- Introduction to Backtracking
  - Backtracking vs Recursion
  - Applications of Backtracking
- Classic Backtracking Problems
  - N-Queens Problem
  - Sudoku Solver
  - Knight's Tour Problem
  - Subset Sum Problem
Divide and Conquer
2 topics
- Introduction to Divide and Conquer
  - Divide and Conquer Strategy
  - Master Theorem
- Classic Divide and Conquer Problems
  - Merge Sort
  - Quick Sort
  - Binary Search
  - Strassen's Matrix Multiplication
String Algorithms
2 topics
- Pattern Matching
  - Naive Pattern Matching
  - Knuth-Morris-Pratt (KMP) Algorithm
  - Rabin-Karp Algorithm
  - Boyer-Moore Algorithm
- String Manipulation
  - Longest Palindromic Substring
  - Longest Repeated Substring
  - Z-Algorithm
Advanced Algorithms
3 topics
- Graph Algorithms
  - Shortest Path Algorithms
  - Minimum Spanning Tree
  - Network Flow Algorithms
  - Strongly Connected Components
- Approximation Algorithms
  - Introduction to Approximation Algorithms
  - Greedy Approximation Algorithms
  - Local Search Algorithms
- Parallel Algorithms
  - Introduction to Parallel Computing
  - Parallel Sorting Algorithms
  - Parallel Graph Algorithms

Data Structure and Algorithm Algorithms flashcards — 50 questions with answers

What is an algorithm?
A finite, well-defined sequence of unambiguous instructions that takes some input and produces an output, solving a specific problem in a finite number of steps. It must be correct, finite, definite, and effective.
What is the difference between an algorithm's time complexity and space complexity?
Time complexity measures how the number of basic operations grows with input size $n$; space complexity measures how the amount of memory (auxiliary storage) grows with input size $n$.
Define Big-O notation and what it bounds.
$O(g(n))$ describes an asymptotic upper bound: $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that $0 \leq f(n) \leq c\,g(n)$ for all $n \geq n_0$. It bounds the worst-case growth rate.
What do Big-Omega ($\Omega$) and Big-Theta ($\Theta$) notations represent?
$\Omega(g(n))$ is an asymptotic lower bound; $\Theta(g(n))$ is a tight bound, meaning $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$, so $c_1 g(n) \leq f(n) \leq c_2 g(n)$.
Order these common complexity classes from fastest to slowest growth: $O(n^2)$, $O(\log n)$, $O(n!)$, $O(n)$, $O(1)$, $O(n\log n)$, $O(2^n)$.
$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$.
What does it mean to analyze the 'worst-case', 'best-case', and 'average-case' complexity of an algorithm?
Worst-case is the maximum running time over all inputs of size $n$; best-case is the minimum; average-case is the expected running time over a probability distribution of inputs of size $n$.
What is amortized analysis?
A method that averages the cost of a sequence of operations over the whole sequence, giving the average cost per operation even when individual operations are occasionally expensive (e.g., dynamic array resizing gives $O(1)$ amortized insertion).
What is an array and what is the time complexity of accessing an element by index?
An array is a contiguous block of memory storing elements of the same type. Accessing element $i$ is $O(1)$ because its address is computed as $\text{base} + i \times \text{size}$.
What are the time complexities of insertion and deletion at an arbitrary position in an array?
Both are $O(n)$ in the worst case because elements must be shifted to maintain contiguity.
How does a dynamic array (e.g., ArrayList/vector) achieve $O(1)$ amortized append?
It doubles its capacity when full. Copying costs $O(n)$ but happens rarely; spreading the copy cost over all appends gives $O(1)$ amortized time per append.
What is a linked list and how does it differ structurally from an array?
A linked list is a sequence of nodes where each node stores data and a pointer to the next node. Unlike arrays, elements are not contiguous in memory and there is no $O(1)$ index access.
Compare access, search, insertion (at head), and deletion (at head) complexity for a singly linked list.
Access: $O(n)$; Search: $O(n)$; Insertion at head: $O(1)$; Deletion at head: $O(1)$.
What is the difference between a singly, doubly, and circular linked list?
Singly: each node points only to the next. Doubly: each node points to both next and previous, allowing backward traversal. Circular: the last node points back to the first (head), forming a loop.
What is a stack and what ordering principle does it follow?
A stack is a linear data structure following LIFO (Last-In, First-Out): the last element pushed is the first popped. Core operations push and pop are $O(1)$.
Name the core stack operations and give a common application of a stack.
Operations: push, pop, peek/top, isEmpty. Applications: function call/recursion management, expression evaluation, undo functionality, and balanced-parenthesis checking.
What is a queue and what ordering principle does it follow?
A queue is a linear data structure following FIFO (First-In, First-Out): the first element enqueued is the first dequeued. Enqueue and dequeue are $O(1)$.
What is the difference between a queue, a circular queue, a priority queue, and a deque?
Queue: plain FIFO. Circular queue: fixed array reused cyclically to avoid wasted space. Priority queue: elements dequeued by priority, not arrival order. Deque (double-ended queue): insertion/removal at both ends.
Define a tree and the terms root, leaf, and height.
A tree is a connected acyclic graph of nodes. The root is the topmost node (no parent); a leaf is a node with no children; height is the number of edges on the longest path from the root to a leaf.
What is a binary search tree (BST) property?
For every node, all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater. This enables search, insert, and delete in $O(h)$ time, where $h$ is the height.
What are the search/insert/delete complexities of a balanced BST versus a degenerate (unbalanced) BST?
Balanced: $O(\log n)$. Degenerate (essentially a linked list): $O(n)$.

Show the other 30 Algorithms flashcards

Name the three depth-first tree traversal orders and the order they visit nodes.
In-order: left, root, right (yields sorted order in a BST). Pre-order: root, left, right. Post-order: left, right, root.
What is a heap and what is the heap property of a max-heap?
A heap is a complete binary tree. In a max-heap, every parent's key is $\geq$ its children's keys, so the maximum is at the root. Insert and extract-max are $O(\log n)$; peek-max is $O(1)$.
What is a graph and how is it formally defined?
A graph $G = (V, E)$ consists of a set of vertices $V$ and a set of edges $E$ connecting pairs of vertices. Edges may be directed or undirected, and may carry weights.
Compare adjacency matrix and adjacency list representations of a graph in space and edge-lookup time.
Adjacency matrix: $O(V^2)$ space, $O(1)$ edge lookup. Adjacency list: $O(V + E)$ space, $O(\deg(v))$ edge lookup. Lists are better for sparse graphs; matrices for dense graphs.
Compare BFS and DFS graph traversals: data structure used and complexity.
BFS uses a queue and explores level by level; DFS uses a stack/recursion and explores as deep as possible first. Both run in $O(V + E)$ with an adjacency list.
What is a hash table and what is its average-case complexity for search, insert, and delete?
A hash table maps keys to array indices via a hash function. Average-case search, insert, and delete are $O(1)$; worst-case (many collisions) is $O(n)$.
What is a hash collision and name two strategies to resolve it.
A collision occurs when two distinct keys hash to the same index. Resolution strategies: (1) separate chaining (store colliding entries in a linked list per bucket) and (2) open addressing (probe for another slot, e.g., linear probing, quadratic probing, double hashing).
What is the load factor of a hash table and why does it matter?
The load factor is $\alpha = \frac{n}{m}$, where $n$ is the number of stored entries and $m$ is the number of buckets. A high $\alpha$ increases collisions; tables typically resize (rehash) when $\alpha$ exceeds a threshold (e.g., $0.7$) to keep operations near $O(1)$.
What is the lower bound on time complexity for any comparison-based sorting algorithm, and why?
$\Omega(n \log n)$. Any comparison sort corresponds to a decision tree with $n!$ leaves; its height is at least $\log_2(n!) = \Theta(n \log n)$.
State the worst-case and average-case time complexity of QuickSort and its space usage.
Average: $O(n \log n)$. Worst case: $O(n^2)$ (e.g., already-sorted input with poor pivot). Space: $O(\log n)$ average for the recursion stack. It is in-place but not stable.
State the time and space complexity of MergeSort and whether it is stable.
Time: $O(n \log n)$ in all cases. Space: $O(n)$ auxiliary. MergeSort is stable.
State the time and space complexity of HeapSort and whether it is stable.
Time: $O(n \log n)$ in all cases. Space: $O(1)$ auxiliary (in-place). HeapSort is not stable.
What are the best, average, and worst-case complexities of Bubble Sort, Insertion Sort, and Selection Sort?
Bubble: best $O(n)$, average/worst $O(n^2)$. Insertion: best $O(n)$, average/worst $O(n^2)$. Selection: $O(n^2)$ in all cases. All use $O(1)$ extra space.
What does it mean for a sorting algorithm to be 'stable'?
A stable sort preserves the relative order of elements that compare equal. Examples: MergeSort, Insertion Sort, Bubble Sort. Not stable: QuickSort, HeapSort, Selection Sort.
How does Counting Sort work and what is its complexity?
It counts occurrences of each key value within a known range $k$, then computes prefix sums to place elements directly. Time: $O(n + k)$; Space: $O(n + k)$. It is non-comparison-based and stable, efficient when $k = O(n)$.
How does Radix Sort work and what is its time complexity?
It sorts numbers digit by digit (least or most significant first), using a stable sort (often Counting Sort) per digit. Time: $O(d(n + k))$, where $d$ is the number of digits and $k$ is the radix/base.
How does Bucket Sort work and when is it efficient?
It distributes elements into buckets over a range, sorts each bucket (often with insertion sort), then concatenates them. Average time $O(n + k)$ when input is uniformly distributed; worst case $O(n^2)$ if all elements fall in one bucket.
Why can non-comparison sorts beat the $\Omega(n \log n)$ comparison bound?
They do not compare elements pairwise; instead they exploit structure of the keys (e.g., integer values in a bounded range or fixed digit length), so the comparison decision-tree lower bound does not apply.
How does linear search work and what is its time complexity?
It scans elements sequentially from the start until the target is found or the list ends. Time: $O(n)$ worst and average case, $O(1)$ best case. It works on unsorted data.
How does binary search work and what is its prerequisite and complexity?
It requires a sorted array. It repeatedly compares the target to the middle element and discards half the search space. Time: $O(\log n)$; Space: $O(1)$ iterative.
Write the recurrence relation for binary search and state its solution.
$T(n) = T\!\left(\frac{n}{2}\right) + O(1)$, which solves to $T(n) = O(\log n)$.
What is the typical mid-index formula in binary search and why is it written that way to avoid overflow?
$mid = low + \frac{(high - low)}{2}$ instead of $\frac{(low + high)}{2}$, because the latter can overflow when $low + high$ exceeds the integer maximum.
What is the expected search time in a balanced BST, a hash table, and a sorted array (binary search)?
Balanced BST: $O(\log n)$. Hash table: $O(1)$ average. Sorted array with binary search: $O(\log n)$. Unsorted array (linear): $O(n)$.
What is dynamic programming and what two properties must a problem have to use it?
Dynamic programming solves problems by combining solutions to overlapping subproblems, storing results to avoid recomputation. Required properties: (1) optimal substructure and (2) overlapping subproblems.
What is the difference between memoization (top-down) and tabulation (bottom-up) in dynamic programming?
Memoization is top-down recursion that caches results as subproblems are encountered. Tabulation is bottom-up, iteratively filling a table from base cases upward. Both avoid recomputation; tabulation usually avoids recursion overhead.
Give the dynamic programming recurrence for the 0/1 Knapsack problem.
$dp[i][w] = \max\big(dp[i-1][w],\; v_i + dp[i-1][w - w_i]\big)$ if $w_i \leq w$, else $dp[i][w] = dp[i-1][w]$. Time and space: $O(nW)$.
What is the recurrence and complexity for the Longest Common Subsequence (LCS) of strings $X$ and $Y$?
$dp[i][j] = dp[i-1][j-1] + 1$ if $x_i = y_j$, else $dp[i][j] = \max(dp[i-1][j],\, dp[i][j-1])$. Time and space: $O(mn)$.
What is a greedy algorithm and what property must a problem have for it to yield an optimal solution?
A greedy algorithm makes the locally optimal choice at each step, hoping to reach a global optimum. It is provably optimal only when the problem exhibits the greedy-choice property and optimal substructure.
How does the greedy approach differ from dynamic programming?
Greedy commits to one locally optimal choice at each step without revisiting it, never reconsidering. Dynamic programming explores and combines all relevant subproblem solutions, making it more powerful but typically slower and more memory-intensive.
Name three classic greedy algorithms and the problems they solve.
Dijkstra's algorithm (single-source shortest paths, non-negative weights), Huffman coding (optimal prefix-free compression), and Kruskal's / Prim's algorithms (minimum spanning tree). The activity-selection and fractional-knapsack problems are also classic greedy examples.

Data Structure and Algorithm Algorithms FAQ

What is in the Data Structure and Algorithm Algorithms syllabus?

Data Structure and Algorithm Algorithms is split into 10 chapters: Introduction to Algorithms, Basic Data Structures, Sorting Algorithms, Search Algorithms, Dynamic Programming, Greedy Algorithms, Backtracking, Divide and Conquer, String Algorithms and Advanced Algorithms. Together they contain 27 topics and 94 sub-topics.

How many chapters are in Data Structure and Algorithm Algorithms?

10 chapters, containing 27 topics and 94 sub-topics. The largest chapter is Basic Data Structures, with 7 topics.

Are there flashcards for Data Structure and Algorithm Algorithms?

Yes — a 50-card Algorithms deck, printed in full in the flashcards section of this page and available in the Examius app with spaced repetition. The free plan covers one exam of your choice, including its flashcards; Examius Pro, a one-time purchase, unlocks every other exam and deck.