## Description

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. • You may assume that M <= N and both numbers are within the range 10000 to 999999 (inclusively), and opt must be one of the chars ‘p’ , ‘t’ , ‘b’ . 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 10000 10300 p 10001 10101 10201 1_2 10000 10300 t 10000 10100 10200 10201 10300 1_3 10000 10300 b 10201 1_4 99000 110000 b 99099 99199 99299 99599 99699 99799 99899 99999 101101 102201 105501 106601 108801 1_5 (Note: there is no output in this test case) 100000 101000 b 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.1 xt + 1.5 ht) ht+1 = tanh(0.5 xt − 2 ht) 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 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: 1 1.0 1.0 -0.9053193842 0.8321596401 2_2: 5 0.0 1.0 2.0 3.0 4.0 5.0 0.4623655914 0.0751742883 0.8741722520 0.2466235712 0.9645899021 0.5249949450 0.7097382221 0.6018123354 0.8471395064 0.7048466172 2_3: 3 1.0 0.0 0.0 0.0 -0.9641167571 0.9586890814 -0.9578009493 0.8177157977 0.1904499845 0.8082908051 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’: character H e l l o W o r l d k +2 +14 +12 + 15 +2 +14 +12 + 15 +2 +14 x 7 4 11 11 14 22 14 17 11 3 y 9 18 23 0 16 10 0 6 13 17 w j s x a q k a g n r enrypted character j S X A Q k A G N R Note: For decryption, we will shift by −k instead of k. Input: • first line of input s c1 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 ◦ you may assume that the input number of characters to encrypt or decrypt (including ! ) is no greater than 50. • second line of input n v1 v2 … vn, where n is the number of characters in the key, and v1,v2,…,vn are the characters in the key. ◦ you may assume that all characters in the key is in uppercase and the number of characters in the key is at least one and no greater than 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 e ! 3 A B C ! 3_2 e a B c D e ! 2 X Y XzZbB! 3_3 d X z Z b B ! 2 X Y aBcDe! 3_4 e H e l l o E N G G 1 3 4 0 / C O M P 2 1 1 3 ! 4 C O M P jSXAQszvi1340/odod2113! 3_5 d f 3 O 3 B 3 I _ P Q R 3 _ Q K _ X 3 D I J K 3 V _ W B F 3 ! 9 C O D E I S F U N D3l3t3d_cod3_is_d3bugg3d_cod3! 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 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 may assume that the first 5 random numbers generated by rand() are all different. • 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: void DealHand(int cards[]) • 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. • You may refer to the following program on how to display the suit symbols in UTF-8 encoding (on Linux/MacOS): #include // include the following 4 lines in your program // these define the UTF-8 encoding of the suit symbols #define SPADE “\xE2\x99\xA0” #define CLUB “\xE2\x99\xA3” #define HEART “\xE2\x99\xA5” #define DIAMOND “\xE2\x99\xA6” using namespace std; int main() { cout << SPADE << CLUB << HEART << DIAMOND << endl; return 0; } 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 0 A♦ 10♥ Q♣ 5♦ 2♠ others 4_2 3 7♠ 9♥ 10♦ 4♥ 7♦ one pair 4_3 540 10♣ 6♠ 10♥ 3♠ 10♦ three of a kind 4_4 13 8♦ 8♣ 9♦ J♥ J♣ two pair