CS2311 Assignment 2 - Message Encoding/Decoding Scheme
Assignment 2
- Message
Encoding/Decoding Scheme
Due: 1st Apr. 2023, Saturday, 23:59 [Week 11]
1. This assignment contains ONE question with Two parts. You are required to submit a complete C++ program (.cpp only) for each part on PASS before the deadline.
2. Only a small set of the test cases are visible for the testing, and a more comprehensive set of test cases will be used for grading. In other word, passing all the visible test cases does not mean that you can get full mark for this assignment. Try your best to thoroughly test your program. Hidden test cases will not be released.
3. Themarkingofeachquestionisbasedonthepercentageofthetotaltestcases that your solution can pass. If your submitted solution leads to a compilation error on PASS, zero mark will be given to that question and no manual checking to your solution is provided in such a case; but if there is no compilation error (on meaningful codes) while no test case is passed, we will check your programming style shown on the codes and some marks may be back.
4. No late submission will be accepted. ALL submissions should be on PASS.
5. Plagiarism check will be performed.
6. You should ONLY use the library <iostream> and <cstring>. You are NOT ALLOWED to use objects from <string>.
In this assignment, you will write a C++ program that can decode a message under the following encoding scheme.
There are two parts in this encoding scheme. The first part is a character set (header) that covers all possible characters of the messages to be decoded. The second part is an encoded message to be decoded based on the keys in the encoding scheme of the first part.
Part A [2 marks] Header Encoding
Write a program that reads a line of printable characters and encodes these characters with a sequence of keys. Each key is a binary string of '0's and '1's. The sequence of keys starts with a key with length 1, followed by three keys with length 2, seven keys of length 3, fifteen keys of length 4, etc (i.e., previous value times two and then plus one). The keys of the same length are in sequence of its binary value but excluding all '0's.
An example of the encoding scheme has shown as follows.
[Example]
Assume the input header is:
n(X+# $90\"? ...
Then the Keys are:
n(X+# $90\"?...
1 01 10 11 001010011100101110 111 0001 ...
To verify the correctness of the encoding, your program should also read an input character and print the key(s) of that character.
Notes:
1. The length of the header will NOT exceed 256, and the maximum length of the key string is seven, i.e., the longest key string is "1111111".
2. The header contains only printable characters including "space", i.e., any characters in the ASCII Table with values from 32 to 126.
3. The header may have repeated characters that lead to
different keys.
4. We can assume the input is valid, i.e., no need to check the correctness of
input.
Sample Input and Output
(Text with blue color is output; text with green color is input)
Example 1
Enter Header:
n(X+# $90\"? Character?$ 011
Example 2
Enter Header:
n(X+# $90\"?# Character?#
001
0010
Example 3
Enter Header:
n(X+# $90\"?
Character?_ 010
input is a "space"
Part B [3 marks] Message Decoding
Extend your program in Part A to
decode a message based on the keys generated in
Part A.
The encoded message is a sequence of binary digits (i.e., sequence of '0's and '1's). The message should be decoded in multiple segments. Each segment starts with the first 3 digits to represent the length of keys to be decoded in the subsequent digits. The end of the segment is signified by a sequence of '0's of that length.
[Example]
Assume the input header is:
n(X+# $90\"? ...
Then if the segment is 010100100, it would be decoded as follows.
010 10 01 00
length of key decoded to be decoded to be end of segment 2X(
The message may have multiple segments and ends with the binary string "000". Your program should
1) read the header and an encoded message;
2) then decode the message and output the decoded message.
Notes:
1. Refer to the Notes of Part A.
2. The encoded message is assumed to be in one line. 3. We can assume the
Sample Input and Output
(Text with blue color is output; text with green color is input) Example 1
Explain: the message code 011001010100000001100111110000101000000 can be divided into the following segments:
011001010100000 00110 011111000 0101000 000
Example 2
Enter Header:
n(X+# $90\"?
Enter code:011001010100000001100111110000101000000 # 9n"X
Enter Header:
:-+ lkC
Enter code:011011000010101000000 C++
Example 3
Enter Header:
=>?@A pqrstuv !"#$EFSTCabgh673rs-./01cde92ieo83r
Enter code:
10011001010000010110000001000101101011000001000011000010110001 00110000001000011110100000110100001001111000010110110011100000 01001101000001111100010000110000101011001001100000100000100001 011011000000011110000101011100000010001000000000
CS2311 is a great course!
