Midterm Prep

41 real exam questions mapped to course topics

Every question below appeared in an actual BME Theory of Algorithms midterm. They are organized by topic so you can practice exactly what will be tested. Each question is worth 10 points.

Total Questions

Midterm 1 Topics

Midterm 2 Topics

Exam Sources

Midterm 1 Simulation

6 practice exams with 7 questions each — timed, scored, and reviewed. Test yourself under real exam conditions.

Start

Midterm 1 Coverage

MT1

You are responsible for Weeks 1, 7, 8, 10 & 11

Week 1 Week 7 Week 8 Week 10 Week 11

Big-O, DFS/BFS, Dijkstra, DAG paths, Dynamic Programming

Midterm 2 Coverage

MT2

You are responsible for Weeks 2, 4, 5, 6, 9 & 12

Week 2 Week 4 Week 5 Week 6 Week 9 Week 12

Heaps, BSTs, 2-3 Trees, Hashing, MST, NP-completeness, Data Structures

Expected Question Distribution

Estimated from patterns across all past midterms — 7 questions, 10 points each, 70 total

Midterm 1

Big-O Determination & Proof

W110 pts

Dynamic Programming

W1010 pts

DFS / BFS Graph Problem

W710 pts

DFS / BFS or DAG Paths

W710 pts

Dijkstra's or Graph Application

W810 pts

Dijkstra's Q Table Analysis

W810 pts

Dynamic Programming (harder)

W1010 pts

Total70 pts

Midterm 2

Heap Operations

W410 pts

BST / Sorting / Array Problem

W510 pts

BST / 2-3 Tree / Hashing

W510 pts

Balanced Trees / MST / Sorting

W510 pts

NP / coNP Proof

W1210 pts

NP-completeness Reduction

W1210 pts

Data Structure Design

W410 pts

Total70 pts

Most Tested Topics

How many times each topic appeared across all past midterms

Dijkstra's AlgorithmMT1

Week 8

Sample MT1Sample MT1 2024MT1 (x3)MT1 Repeat (x3)

Dynamic ProgrammingMT1

Week 10

Sample MT1 (x2)Sample MT1 2024 (x2)MT1 (x2)MT1 Repeat

DFS / Graph TraversalsMT1

Week 7

Sample MT1 (x2)Sample MT1 2024 (x2)MT1MT1 Repeat (x2)

BSTs & Balanced TreesMT2

Week 5

Sample MT2 (x2)MT2MT2 Repeat (x3)

NP / coNP / NP-completenessMT2

Week 12

Sample MT2 (x2)MT2 (x2)MT2 Repeat (x2)

Big-O / Asymptotic AnalysisMT1

Week 1

Sample MT1Sample MT1 2024MT1MT1 Repeat

HeapsMT2

Week 4

Sample MT2 (x2)MT2

Data Structure DesignMT2

Week 4 Week 5

Sample MT2MT2 Repeat (x2)

Greedy / Graph ModelingMT1

Week 11

Sample MT1Sample MT1 2024

Sorting / Array ProblemsMT2

Week 2

Sample MT2MT2 Repeat

MST (Prim's/Kruskal's)MT2

Week 9

MT2MT2 Repeat

Hash TablesMT2

Week 6

MT2

Midterm 1 Questions

Covers: Big-O, DFS/BFS, Dijkstra, DAG paths, Dynamic Programming

Sample Midterm 1Q1hardWeek 1: Basics & Notation

Big-O Determination & Proof

Determine which of three given functions is in O(n²), prove it with constants c and n₀, and show one of the remaining functions is NOT in O(n²).

Midterm 1Q1hardWeek 1: Basics & Notation

Big-O Proof with Chain of Inequalities

Prove f(n) = 2023n² log n - 27√n is O(g(n)) where g(n) = (1/10¹⁰)n³ + n log n. Find constants c and n₀.

Midterm 1 RepeatQ1hardWeek 1: Basics & Notation

Big-O Proof by Contradiction

Show that 37n² log n + 17√n + 7 is NOT in O(n²) by proving no valid c, n₀ exist.

Sample Midterm 1Q3hardWeek 7: Graph Basics & Traversals

DFS Edge Possibility (Undirected Graph)

Given DFS tree edges on an undirected graph, determine if specific edges can exist in the original graph.

Sample Midterm 1Q4hardWeek 7: Graph Basics & Traversals

BFS with Colourful Edges

Find shortest path from a to b using only 'colourful' edges (endpoints have different colors). O(n+m) time.

Midterm 1Q3hardWeek 7: Graph Basics & Traversals

DFS on Directed Graph

Given partial DFS order on a directed graph, determine the full discovery and finish order with reasoning.

Midterm 1 RepeatQ2mediumWeek 7: Graph Basics & Traversals

BFS on Cycle Graph (Jump Problem)

Given a cycle with jump values, find minimum jumps from A to B in O(n) time.

Midterm 1 RepeatQ3hardWeek 7: Graph Basics & Traversals

DFS Degree Analysis

Given DFS tree edges on an undirected graph with 8 vertices, find the minimum and maximum possible degree of a specific vertex.

Sample Midterm 1Q6hardWeek 8: Shortest Paths

Dijkstra's Q Table Reading

Given Dijkstra's Q table on an undirected graph, determine which edges definitely exist and their weights.

Midterm 1Q4hardWeek 8: Shortest Paths

DAG Longest Path (Grid Problem)

Given an n×n grid with integers, find the longest 'legal path' where each step goes from value x to adjacent cell with value x+1. O(n²) time.

Midterm 1Q5hardWeek 8: Shortest Paths

Dijkstra's Q Table Analysis (Directed Graph)

Given Dijkstra's Q table on a directed graph, determine if specific edges can exist and their possible weights.

Midterm 1Q6mediumWeek 8: Shortest Paths

Dijkstra's for Free vs Paid Roads

Find the extra travel time when using only free roads vs. all roads. O(n²) with adjacency matrix.

Midterm 1 RepeatQ4hardWeek 8: Shortest Paths

DAG Shortest Path (Nearest Chocolate)

In a DAG, find the distance from each vertex to the nearest chocolate vertex. O(n²) time.

Midterm 1 RepeatQ5hardWeek 8: Shortest Paths

Dijkstra's with Parameter x

Run Dijkstra's on a graph with edge weight x (a positive real parameter). Show Q table and results as a function of x.

Midterm 1 RepeatQ6mediumWeek 8: Shortest Paths

Dijkstra's for Ambulance Stations

Check if every city is reachable from at least one ambulance station within M minutes. O(n²).

Sample Midterm 1Q2hardWeek 10: Dynamic Programming

DP: Maximum Product Subarray

Find the subarray A[i:j] with the maximum product of positive numbers (values can be < 1). O(n) algorithm using M[j] = max product of subarray ending at j.

Sample Midterm 1Q7hardWeek 10: Dynamic Programming

DP: Constrained Multiplication in Sum

Given a₁+a₂+...+aₙ, replace some '+' with '×' (no two consecutive) to maximize the result. O(n) algorithm.

Midterm 1Q2mediumWeek 10: Dynamic Programming

DP: Advertising Budget (Knapsack Variant)

Maximize people reached by n advertising methods within budget M. Each method has cost pᵢ and reach eᵢ. O(Mn) time.

Midterm 1Q7hardWeek 10: Dynamic Programming

DP: Largest Value Increasing Subsequence

Find the strictly increasing subsequence maximizing (product of elements) + (last element). O(n²).

Midterm 1 RepeatQ7hardWeek 10: Dynamic Programming

DP: Grid Path with Dangerous Cells

In an n×n grid, find the max-value path from top-left to bottom-right (right/down only) stepping on at most 1 dangerous cell. O(n²).

Sample Midterm 1Q5hardWeek 11: Greedy & Amortized Analysis

Festival Scheduling

Maximize total days at festivals (full duration, start new one day after). O(f squared).

Midterm 2 Questions

Covers: Heaps, BSTs, 2-3 Trees, Hashing, MST, NP-completeness, Data Structures

Sample Midterm 2Q2mediumWeek 2: Sorting I

Sorting + Algorithm Design

Given n distinct numbers, determine if two have a difference of exactly 42 using at most O(n log n) comparisons.

Midterm 2 RepeatQ3mediumWeek 2: Sorting I

Sorting + Array Intersection

Given two arrays of n distinct integers, determine if at least n/2 numbers occur in both arrays using O(n log n) time.

Sample Midterm 2Q1mediumWeek 4: Binary Heaps & Priority Queues

Heap Operations (Insert + DELETEMIN)

Draw a min-heap from array [3,8,4,12,10,6,21,33] as a tree, insert 5, then perform DELETEMIN. Show all steps.

Midterm 2Q1hardWeek 4: Binary Heaps & Priority Queues

Heap with Unknown Values

Min-heap [3,5,y,x,12,10,100,7,16,21] — draw as tree, perform DELETEMIN so y becomes root, find all possible x and y values.

Sample Midterm 2Q7hardWeek 4: Binary Heaps & Priority Queues

Two-Heap Data Structure for Middle Element

Design a data structure with two heaps that supports INSERT and DELETE-MIDDLE in O(log k) time.

Sample Midterm 2Q3mediumWeek 5: BSTs & Balanced Trees

BST from Preorder Traversal

Given preorder 3, 10, 4, 8, 7, 9, draw the BST and justify using preorder + BST properties.

Sample Midterm 2Q4hardWeek 5: BSTs & Balanced Trees

2-3 Tree Analysis (Sequential Insert)

Show that inserting 1,2,...,n in order into a 2-3 tree produces at most O(log n) three-nodes.

Midterm 2Q2hardWeek 5: BSTs & Balanced Trees

BST Search Path Analysis

In a BST containing all distinct integers, the search path for 11 is: 3, 17, 8, z, 11. Find all possible values of z.

Midterm 2 RepeatQ1hardWeek 5: BSTs & Balanced Trees

BST + Red-Black Tree Feasibility

Insert 3,2,1,8,5,7,6 into an empty BST. Can the result be colored as a valid Red-Black Tree?

Midterm 2 RepeatQ2hardWeek 5: BSTs & Balanced Trees

2-3 Tree Drawing and Insertion

Draw the unique 2-3 tree containing {2,5,10,12,14,15,19,21} with a 3-node root, then insert 11.

Midterm 2 RepeatQ4hardWeek 5: BSTs & Balanced Trees

Augmented RB-Tree (Order Statistics)

Design a data structure for INSERT(i) and FIND-SMALLEST(k) both in O(log n), using an augmented Red-Black tree.

Midterm 2Q3hardWeek 6: Hash Tables

Open-Address Hash Table with Deletion

Given a partially filled hash table with a deleted marker, determine search steps for a value and find all possible deleted values.

Midterm 2Q4mediumWeek 9: Minimum Spanning Trees

Prim's Algorithm Application (Bicycle Lanes)

Design bicycle lanes connecting all city nodes while minimizing eliminated parking spaces. Give O(n²) algorithm.

Midterm 2 RepeatQ5hardWeek 9: Minimum Spanning Trees

Prim's Algorithm with Parameter x

Run Prim's from vertex A on a graph where one edge has weight x. Determine which edges are selected and for what values of x.

Sample Midterm 2Q5hardWeek 12: Complexity Theory & NP-Completeness

coNP: DEG4SPANNING-TREE

Show that {G | every spanning tree of G has a degree-4 vertex} is in coNP.

Sample Midterm 2Q6hardWeek 12: Complexity Theory & NP-Completeness

NP-completeness: kINDPDT-SET-CLIQUE

Show that {(G,k) | G has both a k-clique and a k-independent-set} is NP-complete.

Midterm 2Q5mediumWeek 12: Complexity Theory & NP-Completeness

NP: 42-CYCLE

Show that 42-CYCLE (vertex set partitioned into exactly 42 disjoint cycles) is in NP.

Midterm 2Q6hardWeek 12: Complexity Theory & NP-Completeness

NP-completeness: 42-CYCLE

Show 42-CYCLE is NP-complete by reducing HAMCYCLE to it.

Midterm 2 RepeatQ6hardWeek 12: Complexity Theory & NP-Completeness

coNP: DIFF-SUBSET-SUM

Show {(s1,...,sn) | all subset sums are distinct} is in coNP.

Midterm 2 RepeatQ7hardWeek 12: Complexity Theory & NP-Completeness

NP-completeness: RED-BLACK-HAMCYCLE

Show RED-BLACK-HAMCYCLE (Hamiltonian cycle where red and black vertices each form contiguous blocks) is NP-complete.

Midterm Study Strategy

- Midterm 1 focuses on: Big-O proofs (always Q1), DFS/BFS graph problems, Dijkstra table reading, and DP algorithm design
- Midterm 2 focuses on: Heap operations, BST/RB-tree/2-3 tree analysis, hashing, MST applications, NP/coNP proofs, and data structure design
- Every midterm has exactly 7 questions worth 10 points each
- Practice with pen and paper — trace algorithms by hand just like the exam requires
- For DP questions, always follow the 8-step template: subproblems, order, start, continue, end, correctness, running time, optimal object
- For NP-completeness: always show (1) the problem is in NP with a witness, and (2) reduce FROM a known NP-complete problem TO yours

Back to Dashboard