York University

CSE 3101 Fall 2013 – Unit Test 5 of 5

Instructor: Jeff Edmonds
1. Art therapy question: When half done the exam, draw a picture of how you are feeling.
2. Dynamic Programming:
Example Decoding Table
Consider an encoding of characters into binary strings in which different
Character Encoding
characters may be encoded into strings of different length. We may de-
A 0
scribe such an encoding scheme by a table with two columns, where each
B 10
character on the left is encoded by the bit string given on the right. See
C 01
the example on the right.
D 11
Using this table the encoding of ACDC is 0011101 (which comes from 0 01 11 01 , but the decoder
is not given the separation between the code-words). Notice that there may potentially be several
decodings of a given bit string. For instance, 001110 can be decoded either as AADB or as ACDA.
Your task is to devise an efficient algorithm which, given an encoded string ha1 , . . . , an i ∈ {0, 1}n
and a decoding table, decodes the string into one of its possible string of characters. For example, if
ha1 , . . . , an i = 001110 and the DecodingTable is as above, then optSol is either AADB or ACDA.

(a) Choose one of these bird questions and argue why it is the best.
i. What is the first character decoded?
ii. How many bits of the input do I use in the code for the last letter?
iii. How many characters are there in the final decoded string?
iv. What is the last character decoded?
v. What is encoding of the last character decoded?
Give a bird-friend algorithm for this problem.
• Answer: (i) is ecstatically bad because it is asking about the beginning of the solution. (iii)
does not seem useful at all. (iv) and (v) are identical because they identify the same row of
the table used. The number of bird answers is the number of rows in the table. Note that for
most of these bird answers, the algorithm will know that bird is wrong because they do not
correspond to the bits at the end of the input string. (ii) gives us the required information,
but the number of bird answers is much much smaller. It is the number of different lengths
of codes.
The algorithm is almost identical to Pretty Print. The question to the bird with PP is “How
many words do I put on the last line?” With Decoding, it is “How many bits of the input
do I use in the code for the last letter?” With an answer k, you take the last k bits of your
input and look them up in the decoding table. If no letter corresponds to them, then you
tell the bird that she is wrong. If say letter C corresponds to them, then delete these k bits
from your input and give the rest to your friend. He decodes this. Our solution is the friend’s
decoded message concatenated with the bird’s letter C.
(b) Give the code for the dynamic programming algorithm. (Be sure to explain each part of the code
as I have been doing.)
algorithm Decode (ha1 , . . . , an i , DecodingT able)
hpre−condi: An instance consists of a coded message ~a and a DecodingTable.
hpost−condi: optSol is a decoded messages.
For example, if ha1 , . . . , an i = 001110 and the DecodingTable is as above, then optSol is
either AADB or ACDA.
The program also returns the ”cost” of the solution, which is 1 if it is a valid decoding
and 0 if it is not.

This study source was downloaded by 100000866485891 from CourseHero.com on 12-08-2023 10:26:36 GMT -06:00

https://www.coursehero.com/file/56427981/test5pdf/
 begin

• Answer:
% For each i ∈ [n], subI[i] is the subinstance ha1 , a2 , . . . , ai i consisting of the i bit prefix.
% We would store its optimal solution in optSol[i], but this takes too much time and space.
% Hence, we only store the cost of this solution and its bird answer.
table[0..n] birdAdvice, cost
% Base Cases.
birdAdvice[0] = ∅
cost[0] = 1
% Loop over subinstances in the table.
for i = 1 to n
% Fill in entry hii for ha1 , a2 , . . . , ai i.
% Try possible bird answers, k = number of bits in the last letter.
for k = 1 to K including only the lengths of the codes that are in the table.
if( hai−k+1 , ai−k+2 , . . . , ai i is the code for a letter C ) then
% Get help from friend
% subSolk = subSol[i − mk ] + C
costk = cost[i − mk ] % i.e. ours is valid if our friend’s is valid.
else
costk = 0 % Bird was wrong.
end if
end for
% Take the best bird answer.
kmax = “a k that maximizes costk ”
birdAdvice[i] = kmax
% subSol[i] = subSolkmax
cost[i] = costkmax
end for
optSol = DecodeW ithAdvice (ha1 , . . . , an i , code, birdAdvice)
return hoptSol, cost[n]i
end algorithm
(c) What is the running time to fill in the table? Be sure to specify where your numbers come from.
In particular, think about what the running time should be when each letter in the table has the
exact same length.
• Answer: As is usual, the running time is “the number of bird answers” times “the number
of subinstances.” The number of bird answers is K the number of different lengths of the
codes that are in the table. The number of subinstance is n. This gives a running time of
Θ(K × n).
Note that if the code for each letter in the table has the exact same length, then no bird is
needed, K = 1, and the running time is Θ(n) as is expected.

This study source was downloaded by 100000866485891 from CourseHero.com on 12-08-2023 10:26:36 GMT -06:00

https://www.coursehero.com/file/56427981/test5pdf/
Powered by TCPDF (www.tcpdf.org)