ENGG1340 / COMP2113, Assignment 1

ENGG1340 / COMP2113, Assignment 1

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.
Sample test cases are provided with each problem in this document. Note that the test cases
may or may not cover all boundary cases for the problem. It is also part of the assessment
whether you are able to design proper test cases to verify the correctness of your program.
We will also use additional test cases when marking your submission.
Input and output format
Your C++ programs should read from the standard input. Also, your answer should be
printed through the standard output. If you failed to follow this guide, the tester may not able
to give a score for your program. Additionally, you should strictly follow the sample output
format (including space, line breaker, etc.), otherwise, your answer might be considered as
wrong.
How to use the sample test cases
Sample test cases in text file formats are made available for you to check against your work
to avoid formatting errors which might fail the tester. Here's how you may use the sample test
cases. Take Problem 2 test case 3 as an example. The sample input and the expected output
are given in the files input2_3.txt and output2_3.txt , respectively. Suppose that your
program is named "2", do the followings at the command prompt of the terminal to check if
there is any difference between your output and the expected output.
./2 < input2_3.txt > myoutput.txt
diff myoutput.txt output2_3.txt
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:
g++ -pedantic-errors -std=c++11 [yourprogram].cpp
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.
While you may develop your work on your own environment, you should always try your
program (compile & execute & check results) on our standard environment before submission.
Submission
Name your C++ programs as in the following table and put them together into one directory.
Make sure that the folder contains only these source files ( *.cpp ) and no other files.
Compress this directory as a [uid].zip file where [uid] is your university number and
check carefully that the correct zip file have been submitted. We suggest you to download
your submitted file from Moodle, extract them, and check for correctness. You will risk
receiving 0 marks for this assignment if you submit incorrect files. Resubmission after the
deadline is not allowed.
Problem Code templates provided Files to Submit
1 - 1.cpp
2 2.cpp 2.cpp
3 3.cpp 3.cpp
4 4.cpp 4.cpp
Late submission
If submit within 3 days after the deadline, 50% deduction. After that, no mark.
Evaluation
Your code will be auto-graded for technical correctness. In principle, we use test cases to
benchmark your solution, and you may get zero marks for not being able to pass any of the
test cases. Normally partial credits will not be given for incomplete solution, as in many cases
the logic of the programs are not complete and an objective assessment could be difficult.
However, your work may still be considered on a case-by-case basis during the rebuttal
stage.
Academic dishonesty
We will be checking your code against other submissions in the class and from the Internet
for logical redundancy. Please be reminded that no matter whether it is providing your work to
others, assisting others to copy, or copying others will all be considered as committing
plagiarism and we will follow the departmental policy to handle such cases. Please refer to
the course information notes for details.
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.
• 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 <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:
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 <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 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 <iostream>
// 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