Algorithms & Data Structures

Register Exam Interest

Exam at a Glance

  • Level: Undergraduate (Honors)
  • Duration: 2.5 hours
  • Format: Written, proof-based (pseudocode expected)
  • Materials: Closed-book

Why Master Algorithms & Data Structures?

  • Preparation for algorithmic problem-solving in technical interviews
  • Readiness for advanced coursework in algorithms
  • Because all computation involves organizing and transforming data efficiently

Recommended Background

Mastery of Discrete Mathematics is recommended prior to self-study for this exam.

Exam Scope

This exam assesses undergraduate (honors-level) mastery of core algorithms and data structures, with emphasis on formal correctness reasoning and runtime analysis. Solutions are expected in clear English and pseudocode; no programming-language specifics are required.

The exam is closed-book and does not provide definitions of core concepts or standard algorithms. Candidates should be able to state definitions precisely.

The scope described here is subject to refinement.

Asymptotic Analysis

  • Formal definitions of Big-O, Θ, and Ω
  • Worst-case runtime analysis; asymptotic comparisons
  • Solving recurrences (substitution, recursion tree, Master Theorem)
  • Amortized analysis (accounting and potential methods)

Algorithm Design Strategies

  • Divide-and-conquer design and analysis
  • Greedy algorithms (including correctness arguments such as exchange arguments)
  • Dynamic programming (optimal substructure; overlapping subproblems)

Data Structures

  • Arrays, stacks, queues, linked lists
  • Heaps and priority queues
  • Binary search trees (unbalanced); red–black trees
  • Hash tables (expected-performance reasoning; collision resolution strategies)
  • B-trees

Candidates are expected to be able to implement and analyze the core operations for each data structure—insert, delete, search, min, max, and enumeration/traversal—and may be asked to write correct pseudocode for these operations on demand.

Sorting and Order Statistics

  • Elementary sorts: insertion, selection, bubble (for comparison and analysis)
  • Comparison sorts: merge sort, quicksort, heap sort; properties and tradeoffs
  • Non-comparison sorts: counting, radix, bucket (assumptions and constraints)
  • Order statistics (selection; median and quantiles)

Candidates should understand average and worst-case runtime complexity, memory usage, stability, and the assumptions or constraints that distinguish these algorithms from one another.

Graph Algorithms

  • Graph representations; traversal with BFS and DFS
  • Topological sorting
  • Strongly connected components
  • Minimum spanning trees (Kruskal, Prim)
  • Shortest paths (Bellman–Ford, Dijkstra; correctness conditions)

String Algorithms

  • Dynamic programming on strings (LCS; edit distance / Wagner–Fischer)
  • Substring search (finite automata, Rabin–Karp, KMP)
  • Trie-based string processing
  • Suffix arrays (basic construction idea and typical applications)

Out of Scope

The following topics are not covered in the exam. This section is provided to clarify boundaries and help candidates focus their preparation.

  • Randomization and complexity theory

    • Randomized algorithms (Monte Carlo / Las Vegas)
    • Computational complexity theory (NP-completeness, reductions, complexity classes)
    • Approximation algorithms and approximation guarantees

  • Advanced computational models

    • Parallel, distributed, and concurrent algorithms
    • Quantum algorithms

  • Number-theoretic and cryptographic topics

    • Number-theoretic algorithms
    • Cryptographic algorithms and primitives
    • Hash function construction (as distinct from hash tables)

  • Numerical and applied domains

    • Linear and integer programming
    • Data compression and coding theory
    • Algorithms specific to machine learning or artificial intelligence

  • Specialized data structures

    • Advanced or specialized data structures beyond those listed in the exam scope

Exam Format

  • Written exam; responses in clear English with pseudocode and formal reasoning.
  • Closed-book; notes, calculators, phones, and electronic devices are prohibited.
  • Writing materials are provided; additional pens or pencils are permitted.
  • Restroom and water breaks are permitted but do not pause the exam timer.

Performance Standards

Results are reported as Mastery, Proficiency, Partial, or Insufficient.

Results reflect absolute performance against defined criteria, not relative ranking among candidates.

  • Mastery — Demonstrates comprehensive and reliable command of the subject matter. Solutions are consistently correct, well-justified, and show strong understanding, with at most minor errors or omissions.
  • Proficiency — Demonstrates substantial understanding of the subject matter, but with one or more non-trivial errors, gaps, or incomplete justifications.
  • Partial — Demonstrates limited or uneven understanding. Some correct ideas or techniques are present, but significant errors or omissions prevent full solutions.
  • Insufficient — Does not demonstrate adequate understanding of the subject matter. Solutions are largely incorrect, missing, or unsupported.

Recommended Resources

These are recommended primary resources for preparation. The exam is governed by the published scope; these texts reflect the level and style expected.

  • Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)
  • Algorithms (Sedgewick & Wayne)