Initials: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Family Name: . . . . . . . . . . . . . . . . . . . . . . . . . . Other Names: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Signature: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ID Number: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Model Solutions
COMP 261 Test 4
30 May 2024

Instructions

• Time allowed: 50 minutes .

• Answer all the questions. There are 50 marks in total.
• Write your answers in the boxes in this test paper and hand in all sheets.
• If you are a remote student, then write the answers on paper and submit a photo to
the relevant submission system entry.
• If you think some question is unclear, ask for clarification.
• This test contributes 15% of your final grade
• You may use paper translation dictionaries, and non-programmable calculators.
• You may write notes and working on this paper, but make sure your answers are clear.

Questions Marks
1. Data Compression [27]
2. String Search [17]
3. Fast Fourier Transform [6]
1. Data Compression (27 marks)

***Huffman Coding***
(a) (8 marks) Suppose we have the characters {A, B, C, D, E, F, G} that need to be en-
coded using the Huffman coding method. The probabilities of each character are:
P(A) = 0.5, P(B) = 0.1, P(C) = 0.01, P(D) = 0.1, P(E) = 0.15, P(F) = 0.05, P(G) = 0.09. Please:

• Construct the relevant binary tree,

• Show the code it assigns to each character.

*Note 1: If the two nodes have the same frequency in the priority queue, pick the node with the
smaller character alphabetically. Specifically, ” ” comes before all the lowercase letters.
*Note 2: When building a parent node, use the node with the smaller frequency as the left child.
*Note 3: You can draw a ”+” to represent the non-leaf nodes when drawing a Huffman tree, like
the figure below. But DO NOT treat the non-leaf node as a real symbol of ’+’.

Draw your Huffman tree below:

The code for each character is:

A: 0
B: 100
C: 11000
D: 101
E: 111
F: 11001
G: 1101

COMP 261 (Test 4) Page 2 of 7

 (b) (2 marks) Given the coding scheme in the previous sub-question, what is the average
compression rate compared with the result of a fixed-length coding method where 3 bits
are used for representing one symbol?
Hint: The average coding length using 3-bit fixed-length encoding is 3 bits per symbol. Using the
previous coding scheme for such a probability distribution, if the expected average coding length
for one character is 2.4 bits using your coding scheme, the compression rate is 2.4/3 = 80%

SUM of code length by probability: 2.21/3 or 73.67%

(c) (2 marks) Please decode the following bit string, which is encoded using the Huff-
man coding tree shown below (The symbols are {U, X, Y, Z}): 000111110010111

UUUZZXYZ

EXTRA ANSWER BOX IF NEEDED (PLEASE INDICATE THE QUESTION IDs):

COMP 261 (Test 4) Page 3 of 7

 ***Lempel-Ziv Coding***

(d) (3 marks) Multi-choice question: What is an advantage of using the Lempel-Ziv

encoding algorithm in data compression?
A
A. It has an ability to compress data efficiently by exploiting redundancy in sequences
without needing a prior knowledge of the data.
B. It always produces the smallest possible compressed file size compared to other com-
pression algorithms.
C. It uses a predefined set of codewords, which simplifies the compression process.
D. It requires less computational power than Huffman coding when encoding.

(e) (3 marks) Multi-choice question: Which of the following statements correctly de-
scribes the Lempel-Ziv (LZ77) encoding algorithm? B
A. Lempel-Ziv encoding relies on fixed-size codewords to represent characters and uses
a predefined dictionary.
B. Lempel-Ziv encoding compresses data by replacing repeated occurrences of data with
references to a single copy of that data found earlier within a sliding window.
C. Lempel-Ziv encoding requires a prior analysis of the entire dataset to construct an
optimal dictionary for compression.
D. Lempel-Ziv encoding uses variable-length codes to represent frequently occurring
characters and fixed-length codes for less frequent characters.

(f) (3 marks) Suppose that the following tuple sequence is an encoding result by the
Lempel-Ziv encoding method:
[0, 0, ’B’][0, 0, ’A’][0, 0, ’N’][2, 1, ’N’][4, 1, ’_’][7, 3, ’D’]
Please decode the tuple sequence above to its original string:

BANANA BAND

EXTRA ANSWER BOX IF NEEDED (PLEASE INDICATE THE QUESTION IDs )

COMP 261 (Test 4) Page 4 of 7

 ***Arithmetic Coding***
(g) (6 marks) Suppose that we have an alphabet of {a, b, c}, with a probability distribu-
tion of {0.4, 0.4, 0.2}. Then we can have the following partitioning scheme:

Please choose the correct answer for each of the following questions:
(1) For the string ”ba”, which of the following options can be its 4-bits binary code se-
quences after encoding it using the arithmetic coding algorithm? D

A. 0000 B. 1000 C. 100 D. 0111

i (2) When doing on-the-fly encoding for transmitting ”bb”, when we read in the first
’b’, what binary code will be emitted and transmitted? C
Then, when we read in the second character, ‘b’, what will be transmitted? E
A. 1 B. b C. nothing D. 0 E. 10

EXTRA ANSWER BOX IF NEEDED (PLEASE INDICATE THE QUESTION IDs )

COMP 261 (Test 4) Page 5 of 7

2. String Search (17 marks)

(a) (3 marks) Multi-choice question: How does the KMP algorithm handle a mismatch
during the search phase when searching a string S through a text T? C

A. It restarts the search from the beginning of the text T.

B. It shifts the string S to the right by one position.

C. It uses the partial match table to determine the next position to check.

D. It ignores the mismatch and continues searching.

(b) (6 marks) Show the partial match table M generated for the KMP algorithm for the
search string S: ”ababaab”

S a b a b a a b
M -1 0 0 1 2 3 1

(c) (8 marks) When searching the above string S “ababaab” through the text T below
using KMP algorithm, after the first two match attempts for the position T[0] and T[1],
please show the start positions of the next four match attempts, where the KMP algo-
rithm will need to check. You only need to show the start position of each match at-
tempt (where the first character of string S is aligned).

Pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
T c a b a b c a b a b a c a a b a b a

The positions to check are: T[0], T[1], , , , , .......

T[3],T[5],T[6],T[8]

*Note: Please use “T[K]” to indicate that the start position of the string S for that match attempt.
DO NOT need to show the fail point.
*Note: You may not need to fill in all the following empty boxes if a successful matching
can be returned.

EXTRA ANSWER BOX IF NEEDED (PLEASE INDICATE THE QUESTION IDs )

COMP 261 (Test 4) Page 6 of 7

3. Fast Fourier Transform (6 marks)

(a) (3 marks) Multi-choice question: What is the advantage of using FFT for polynomial
multiplication? A

A. It reduces the time complexity from O( N 2 ) to O( NlogN ).

B. It increases the accuracy of the polynomial coefficients.

C. It simplifies the multiplication process by using only addition operations.

D. It requires less memory compared to the naive approach.

(b) (3 marks) Multi-choice question: Which of the following is a valid step in the FFT-
based multiplication of polynomials P( x ) = x + 1 and Q( x ) = x2 + x + 1 ? B

A. Calculate the product directly by multiplying the coefficients.

B. Use FFT to convert both polynomials to point-value form, multiply the results, and
use the inverse FFT.

C. Integrate both polynomials before multiplication.

D. Differentiate both polynomials and then multiply the coefficients.

**********************************END OF TEST 4 **************************************

***************

COMP 261 (Test 4) Page 7 of 7