Data Structure and Algorithm Algorithms Syllabus

Algorithms syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Algorithms in Data Structure and Algorithm, not a summary of it.

1. 1

   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
2. 2

   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
3. 3

   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
4. 4

   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
5. 5

   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
6. 6

   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
7. 7

   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
8. 8

   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
9. 9

   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
10. 10

    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

Algorithms flashcards for Data Structure and Algorithm

23 of 50 cards from the Algorithms deck — real questions with worked answers.

1. 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.

2. 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$.

3. 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.

4. 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)$.

5. 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!)$.

6. 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$.

7. 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).

8. 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}$.

9. 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.

10. 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.

11. 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.

12. 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)$.

13. 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.

14. 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)$.

15. 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.

16. 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)$.

17. 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.

18. 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.

19. 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.

20. 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)$.

21. 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.

22. 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)$.

23. 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.

See more Algorithms flashcards →

Planning Algorithms for Data Structure and Algorithm

Algorithms (Data Structure and Algorithm) FAQ