COMP2113 Assignment 1 Solution

If you have any questions, please post to the Moodle discussion forum on Assignment 1.
• General Instructions
• Problem 1: Palindromic Numbers (20 marks)
• Problem 2: Recurrent Neural Networks (25 marks)
• Problem 3: Shift Cipher (25 marks)
• Problem 4: A 5-Card Hand (25 marks)
Total marks: 100 marks
• 5 marks for proper code comments and indentation
• 95 marks for program correctness
A maximum of 5 marks will be deducted if you fail to follow the submission instructions strictly.

General Instructions
Read the instructions in this document carefully.
In this assignment you will solve 4 problems and a tester would automatically test your submitted program. So if your submitted files and program outputs do not conform to our instructions given here, your programs cannot be evaluated and you will risk losing marks totally.
We will also use additional test cases when marking your submission.
Input and output format
How to use the sample test cases

Testing against the sample test cases is important to avoid making formatting mistakes. The additional test cases for grading your work will be of the same formats as the sample test cases.
Coding environment
You must make sure that your program can compile, execute and generate the required outputs on our standard environment, namely, the gcc C++11 environment we have on the CS Linux servers (academy*). Make sure that the following compilation command is used to compile your programs:

As a programmer/developer, you should always ensure that your code can work perfectly as expected on a target (e.g., your client's) environment, not only on yours.
Submission
Name your C++ programs as in the following table and put them together into one directory.

Late submission
Evaluation
Academic dishonesty
Getting help
You are not alone! If you find yourself stuck on something, post your question to the course forum. We want this assignment to be rewarding and instructional, not frustrating and demoralizing. But we don’t know when or how to help unless you ask.
Please be careful not to post spoilers. Please don’t post any code that is directly related to the assignments to the discussion forums or share your work to any public domain. However you are welcome and encouraged to discuss general ideas on the discussion forums.

Problem 1: Palindromic Numbers
A palindromic number is one that reads the same both ways, from the beginning or from the end. For example, 525 and 8448 are palindromic numbers. Note that 525 and 8448 are also products of two 2-digit numbers: 525 = 15 * 35 and 8448 = 96 * 88. On the other hand, 7777 is a palindromic number but not a product of two 2-digit numbers.
Write a C++ program that prompts the user for two integers M and N and output numbers in the range of M and N (inclusively) which are either (1) palindromic only; (2) product of two 3-digit numbers only; or (3) both palindromic and product of two 3-digit numbers.
Input:
• A single line containing two integers M , N , and a char opt for the display option.
Output:
• If the input opt is the char 'p' , then output the palindromic numbers in the range of M and N (inclusively) in increasing order.
• If the output opt is the char 't' , then output the numbers which are a product of two 3-digit numbers in the range of M and N (inclusively) in increasing order.
• If the input opt is the char 'b' , then output the numbers which are both palindromic and a product of two 3-digit numbers in the range of M and N (inclusively) in increasing order.
• If there is no number within the range that matches the criteria, no line will be output.
Requirement:
• Your program must implement the following two helper functions:
◦ bool isPalindrome(int x) which returns whether the parameter x is a palindromic number.
◦ bool isProduct(int x) which returns whether the parameter x is a product of two 3-digit numbers.
• Call the helper functions in your main function to accomplish the task.
• You can ONLY use the simple data types char , bool , int , double . In other words, you are not allowed to use other data types or data structures such as arrays, strings or STL containers (e.g., vectors), etc.
Sample Test Cases
User inputs are shown in blue.
1_1

1_2

1_3

1_4

1_5 (Note: there is no output in this test case)


Problem 2: Recurrent Neural Networks
Recurrent neural networks (RNNs) are deep-learning architectures which are particularly powerful in dealing with time-series (e.g., financial) and natural language data. In this problem, you are going to write a program to simulate the basic forward propagation mechanism in an RNN using simple 1D arrays. Note that you do not need to understand what an RNN is to solve this problem; you will find all the necessary information that you need to solve this problem in the following description.
An RNN cell at time t takes an input xt and a hidden state ht from the previous cell, and computes a next state ht+1 and an output ot.

Specifically, each RNN cell computes ot and ht+1 using the following two functions:
ot = sigmoid(0.1xt + 1.5ht) ht+1 = tanh(0.5xt − 2ht)
where
sigmoid(x) = 1/(1 + e−x) tanh(x) = 2 × sigmoid(2x) − 1 and e = 2.72.
Multiple RNN cells can then be connected to form a network. The following figure depicts an RNN of T cells that accepts an input sequence x0, x1,...,xT−1 and an initial hidden state h_0 as inputs, and outputs a sequence o0, o1, ..., oT−1.

Write a C++ program that implement the above simple RNN.
Input:
• the first line contains two numbers: an integer T denoting the recurrent times ( 1 ≤ T ≤ 100 ) and a floating-point number h0 denoting the initial hidden state; and
• the second line contains the input sequences which are T floating-point numbers x0, x1,...,xT−1.
Output:
• Your program should display the hidden state sequences h1, h2, ..., hT in the first line and the output sequences o0, o1, ..., oT−1 in the second line.
• Floating-point numbers are displayed with 10 decimal places. Use setprecision(n) defined in the header <iomanip> to set the precision
parameter of the output stream.
Requirement:
• You will need to complete the following functions in the provided template
2.cpp . Read the code in the template carefully to see what have been provided for you. You will find details of the function prototypes in the in-code comments too.
◦ sigmoid() for sigmoid activation function
◦ tanh() for tanh activation function
◦ ComputeH() for computing the next hidden value in RNN cell
◦ ComputeO() for computing the output value at current time step
◦ PrintSeqs() for printing the values in a 1D array to screen
◦ main() for main function
• Use 1D arrays to store the sequences for xi, hi and oi.
• You can ONLY use the simple data types char , bool , int , double and arrays. In other words, you are not allowed to use other data types or data structures such as strings or STL containers (e.g., vectors), etc.
Sample Test Cases
User inputs are shown in blue.
2_1:

2_2:

2_3:


Problem 3: Shift Cipher
Write a C++ program which encrypts and decrypts a sequence of input characters using an algorithm adapted from the Vignѐre cipher as described below.
We first consider the algorithm to encrypt/decrypt a single character:
To encrypt (decrypt) a letter c (within the alphabet A-Z or a-z) with a shift of k positions:
1. Let x be c's position in the alphabet (0 based), e.g., position of B is 1 and position of g is 6.
2. For encryption, calculate y = x + k modulo 26; for decryption, calculate y = x − k modulo 26.
3. Let w be the letter corresponding to position y in the alphabet. If c is in uppercase, the encrypted (decrypted) letter is w in lowercase; otherwise, the encrypted (decrypted) letter is w in uppercase.
A character which is not within the alphabet A-Z or a-z will remain unchanged under encryption or decryption.
Example. Given letter B and k = 3, we have x = 1, y = 1 + 3 mod 26 = 4, and w = E . As B is in uppercase, the encrypted letter is e .
Now, to encrypt/decrypt a sequence of characters:
The number of positions, k, used to shift a character is determined by a key V of n characters. For example, if V is a 4-character key 'C', 'O', 'M', 'P', and their positions in the alphabet is 2, 14, 12 and 15, respectively. To encrypt a sequence of characters, we shift the first character by +2 positions, the second by +14, the third by +12, the fourth by +15 and repeat the key, i.e., we shift the fifth character by +2, the sixth by +14, until we encrypt all the characters in the input sequence.
Example. Consider the input sequence of characters 'H','e','l','l','o','W','o','r','l','d' and a 4-character key 'C','O','M','P':

Note: For decryption, we will shift by −k instead of k.
Input:
• first line of input sc1 c2 c3 …, where
◦ s is either the character e for encryption, or the character d for decryption
◦ c1 c2 c3 … is a sequence of space separated characters, ended by
! , to be encrypted or decrypted
• second line of input nv1 v2 … vn, where n is the number of characters in the key, and v1,v2,...,vn are the characters in the key.
10.
Output:
• the encrypted/decrypted message ended by ! . There should be no space between two consecutive characters.
Requirement:
• You are provided with a template program 3.cpp . Read the code in the template carefully to see what have been provided for you.
• You can ONLY use the simple data types char , bool , int , double and arrays. In other words, you are not allowed to use other data types or data structures such as strings or STL containers (e.g., vectors), etc.
Sample Test Cases
User inputs are shown in blue.
3_1

3_2

3_3

3_4

3_5


Problem 4: A 5-Card Hand
Write a C++ program to generate a random hand of FIVE poker cards from a deck of 52 poker cards, and determine the type of poker hand it is. The input and output of your program as are follows:
Input:
• An integer x that you would use as input parameter to srand() for initializing the random number generator (RNG).
Output:
• the first line displays the five cards in the hand. (Note that there is a space at the end of the first output line.)
• the second line tells the type of the 5-card hand, in the following categories:
◦ four of a kind (e.g., A♠ A♥ A♣ A♦ 2♣)
◦ full house (e.g., 8♠ 8♥ 8♦ 4♥ 4♣)
◦ flush (e.g., K♠ 10♠ Q♠ 5♠ 3♠ )
◦ three of a kind (e.g., 10♥ 10♦ 10♣ 5♥ J♠ )
◦ two pair (e.g., 9♦ 9♣ 2♥ 2♣ 3♥)
◦ one pair (e.g., 7♠ 7♦ A♠ Q♠ 6♠)
◦ others
(Check the wiki page "list of poker hands" for the detailed definition of
each type.)
Requirement:
• You are provided with a template program 4.cpp . Read the code in the template carefully to see what have been provided for you.
• Represent each card of the deck by an integer from 0 to 51 in the following ways:
◦ A♠, 2♠, 3♠, ..., 10♠, J♠, Q♠, K♠ are represented by 0, 1, 2, ..., 12, respectively
◦ A♥, 2♥, 3♥, ..., 10♥, J♥, Q♥, K♥ are represented by 13, 14, 15, ..., 25, respectively
◦ A♣, 2♣, 3♣, ..., 10♣, J♣, Q♣, K♣ are represented by 26, 27, 28, ..., 38, respectively
◦ A♦, 2♦, 3♦, ..., 10♦, J♦, Q♦, K♦ are represented by 39, 40, 41, ..., 51, respectively
• The array cards of 5 integers defined in the main function is used for storing a 5-card hand.
• Use the rand() function in <cstdlib> to generate random numbers. However, the RNG ONLY guarantees to generate the same sequence of random numbers given the same seed on the same OS & platform only. The sample test cases are generated on the CS academy* servers, so you have to run the program there in order to generate the same results.
• You can ONLY use the simple data types char , bool , int , double , string and arrays. In other words, you are not allowed to use other data types or data structures such as STL containers (e.g., vectors), etc.
• You program MUST contain the following 8 functions:
• The function DealHand() should read from user input an integer x and use it as seed to the RNG for generating five random numbers, each representing a card in a 52-card deck. The first five numbers generated by the RNG should be stored in the array cards[] in order.
void PrintHand(int cards[])
• The function PrintHand() should print a hand stored in cards[] . For example, if cards[0] == 0 , cards[1] == 25 , cards[2] == 14 , cards[3] == 50 , cards[4] == 36 , the line A♠ K♥ 2♥ Q♦ J♣ should be output to the screen.

The other 6 functions that you must have in your program are:
bool IsFourOfAKind(int cards[]) // return if the hand is a four of a kind bool IsFullHouse(int cards[]) // return if the hand is a full house bool IsFlush(int cards[]) // return if the hand is a flush bool IsThreeOfAKind(int cards[]) // return if the hand is a three of a kind bool IsTwoPair(int cards[]) // return if the hand is a two pair bool IsOnePair(int cards[]) // return if the hand is a one pair
These 6 functions should take a 5-card hand as input and return whether the hand is of a certain type. Note that these functions do not take the array size as an input parameter as we assume a hand always contain 5 cards in this problem (and a constant is defined in the code template).
Sample Test Cases
User inputs are shown in blue.
4_1

4_2

4_3

4_4