ITPEC FE Subject B April 2024 Question 15

Generating n-grams from text by splitting into words and assembling consecutive subsequences.

The procedure NGRAMS(n, text) splits a sentence into words and outputs all contiguous n-word sequences.

Blank A — outer loop upper bound:
For length words, the number of possible n-grams is length - n + 1 (the last n-gram starts at position length - n + 1). Example: 6 words, trigrams → starts at positions 1, 2, 3, 4 → 6 - 3 + 1 = 4.

Blank B — inner loop upper bound:
Starting from position i, we need n consecutive words: indices i through i + n - 1.

Verification with bigrams (n = 2, length = 6):
- Outer: i from 1 to 6 - 2 + 1 = 5
- At i = 1: j from 1 to 1 + 2 - 1 = 2 → words[1] + words[2] = "ITPEC includes" ✓
- At i = 5: j from 5 to 5 + 2 - 1 = 6 → words[5] + words[6] = "6 countries" ✓

Why not others:
- (a) length / n — outer loop runs too many iterations; inner loop takes only n words starting from index 1 each time, not from i
- (b) length / i + n — inner loop overshoots the array (i + n goes one position beyond the needed window)
- (c) length / i + n - 1 — outer loop runs to length, causing out-of-bounds access in the inner loop for later values of i
- (d–f) length - n / ... — outer loop stops one position too early (misses the last valid n-gram starting position)
- (g) length - n + 1 / n — inner loop always takes words from index 1 to n, producing the same n-gram every time
- (h) length - n + 1 / i + n — inner loop collects n + 1 words instead of n, producing (n+1)-grams

Key rule: For sliding-window problems over an array of size L with window size n: the window starts at positions 1 through L - n + 1, and each window covers indices i to i + n - 1.

AI-generated — may contain errors