COMP2113代做、C++程序语言调试、c/c++代写代写、代做Programming

日期：2019-12-23 08:48

COMP2113 Programming technologies [2019]

Assignment 2

General Instructions

Please read the instructions in this document carefully. In this assignment, you will solve FOUR

tasks and a tester would automatically test your submitted program. Sample test cases are provided

with each task in this document (user inputs are printed in blue). However, please note that we

will also use additional test cases when marking your assignment submission.

Total: 100 points

5 points for proper code comments and indentation

5 points for program modularity using appropriate functions

90 points for program correctness

Input and output format

Please follow the instructions given by each question regarding input/output requirements for your

program. If you failed to follow the instructions, 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.

Submission

You are provided with the following 4 C/C++ files, each a code template for a task. Download them

and put them together into one directory. After completing the assignment, compress this directory

as a .zip file. Make sure to only upload the source files (*.c/*.cpp). Do not submit any other files.

There should only be the 4 files in the zip archive. Please use your university number to name the

zip archive and check carefully that the correct files have been submitted. We suggest you

download your submitted files, extract them, and check for correctness. You will receive 0 marks

for this assignment if you submit incorrect files. Resubmission after the deadline is not allowed.

Filename Description

1.cpp Task 1

2.cpp Task 2

3.cpp Task 3

4.cpp Task 4

IMPORTANT: Read the comments in the given code templates carefully, and follow the

instructions there.

Deadline

The deadline is announced in Moodle. Late submission will not be accepted.

Late submission

You will receive 0 marks if you submit after the deadline.

2

Wrong submission

You will receive 0 marks if you submit incorrect files.

Evaluation

Your code will be tested for technical correctness. However, the correctness of your implementation

– not the tester’s judgments – will be the final judge of your score. If necessary, we will review your

work individually to ensure that you receive due credit for your work.

Academic Dishonesty

We will be checking your code against other submissions in the class and from the Internet for

logical redundancy. If you copy someone else’s code and submit it with minor changes, we will

know. We trust you all to submit your own work only; please don’t let us down. If you do, we will

pursue the strongest consequences available to us.

Task 1 (C++) Recurrent neural network

(20 points)

“A recurrent neural network (RNN) is a class of artificial neural network where connections

between nodes form a directed graph along a temporal sequence. This allows it to exhibit temporal

dynamic behavior. Unlike feedforward neural networks, RNNs can use their internal state (memory)

to process sequences of inputs. This makes them applicable to tasks such as unsegmented,

connected handwriting recognition or speech recognition.” (Description from Wikipedia)

In this task, we will build a simple recurrent neural network and simulate its forward propagation.

As shown the figure below, an RNN cell at time ?? takes an input ???? and a hidden state ???

from the

previous cell, and computes a next state ???+1 and an output ????

. An RNN of T cells accepts an input

sequence ??0, ??1, … , ?????1 and an initial hidden state ?0 and outputs a sequence ??0, ??1, … , ?????1.

Each RNN cell computes the following functions:

???? = sigmoid(0.2???? + 2???)???+1 = tanh(0.6???? ? 2???)

where

3sigmoid(??) =11 + ?????tanh(??) = 2 × sigmoid(2??)– 1e = 2.72

Your program should take two lines of input:

? the first line contains two numbers: an integer T denoting the recurrent times (?? ≤ 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

??0, ??1, … , ?????1 .

Your program should then display the hidden state sequences ?1, ?2, … , ??? in the first line and the

output sequences ??0, ??1, … , ?????1 in the second line.

You will need to complete the following functions in the provided template 1.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

Note:

? You may use setprecision(n) defined in the header <iomanip> to set the precision

parameter of the output stream, making them the same as the sample test case.

Sample test case 1.1

5 0.0

1.0 2.0 3.0 4.0 5.0

0.5373192913 0.1247867951 0.9140171922 0.5170662095 0.9616286607

0.5498652773 0.8139025799 0.7005903049 0.9327484189 0.8844658501

Sample test case 1.2

1 1.0

1.0

-0.8855427140

0.9003742762

Sample test case 1.3

3 1.0

0.0 0.0 0.0

-0.9641167571 0.9586890814 -0.9578009493

0.8809297009 0.1268112559 0.8719810862

4

Task 2 (C++) Path planning

(25 points)

In this task, your program will accept a map (in form of a 2D grid) and determine the smallest

number of steps it takes to go from the starting point to the destination. From any cell in the map,

one can only reach to its 4-neighbours, i.e., the top / bottom / right / left neighbours.

An example 5 x 5 map is as follows:

-1 -1 -1 -1 -1

-1 0 0 0 -1

-1 1 -1 -2 -1

-1 0 -1 0 -1

-1 -1 -1 -1 -1

We denote -1 as an obstacle, 0 as feasible space, 1 as the starting point and -2 as the destination. In

this example, there is a path from the starting point (1) to the destination (-2) by following the

feasible space marked by the red 0, and the smallest number of steps taken from the starting point

to the destination is 4.

You may assume that there is exactly one starting point and one destination in the input map. The

maximal values of the height and the width of the map are no more than 1000.

The first input line to your program contains two integers giving the height (H) and width (W) of

the map. After that, H rows times W columns of integers representing the map will follow.

You will need to complete the following function 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.

? FindPath() for finding the smallest number of steps to go from the starting point to the

destination on a given map.

You are NOT allowed to modify the main() body but you should add your own functions

wherever appropriate for better program modularity.

Here we make use of sample test case 2.6 to give you an idea of how the smallest number of steps

can be found.

Given a 5x5 map -1 -1 -1 -1 -1

-1 0 0 0 -1

-1 1 -1 0 -1

-1 0 0 -2 -1

-1 -1 -1 -1 -1

1

st iteration – reach out one step from the starting point "1" by

filling its zero-valued (i.e., feasible space) 4-neighbours with

"2"

-1 -1 -1 -1 -1

-1 2 0 0 -1

-1 1 -1 0 -1

5

-1 2 0 -2 -1

-1 -1 -1 -1 -1

2

nd iteration – reach out one step from the all "2"s by filling

their zero-valued (i.e., feasible space) 4-neighbours with "3"

-1 -1 -1 -1 -1

-1 2 3 0 -1

-1 1 -1 0 -1

-1 2 3 -2 -1

-1 -1 -1 -1 -1

3

rd iteration – reach out one step from the all "3"s by filling their

zero-valued (i.e., feasible space) 4-neighbours with "4". As we

find that we have also reached the destination "-2", hence the

number of steps taken is 3.

-1 -1 -1 -1 -1

-1 2 3 4 -1

-1 1 -1 0 -1

-1 2 3 -2 -1

-1 -1 -1 -1 -1

Think about this: how to determine that there is no valid path in the map?

Sample test case 2.1

5 5

-1 -1 -1 -1 -1

-1 0 0 0 -1

-1 1 -1 -2 -1

-1 0 -1 0 -1

-1 -1 -1 -1 -1

4

Sample test case 2.2

5 5

-1 -1 -1 -1 -1

-1 0 0 0 -1

-1 1 -1 0 -1

-1 0 -1 0 -1

-1 -1 -1 -1 -1

No

Sample test case 2.3

3 5

-1 -1 -1 -1 -1

-1 -2 -1 1 -1

-1 -1 -1 -1 -1

No

Sample test case 2.4

3 5

-1 -1 -1 -1 -1

-1 -2 0 1 -1

-1 -1 -1 -1 -1

2

Sample test case 2.5

5 5

-2 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 1

8

Sample test case 2.6

5 5

-1 -1 -1 -1 -1

-1 0 0 0 -1

-1 1 -1 0 -1

-1 0 0 -2 -1

-1 -1 -1 -1 -1

3

6

Task 3 (C++) Deletion and statistics of stop words

(25 points)

A common pre-processing of a piece of text is to remove stop words which carries little discriminating

power for information retrieval or text mining. Stop words are the most common words or short

function words, such as “a”, “an”, “the”, “where”, “and”, etc. In this task, you are going to write a C++

program to remove stop words from a piece of text.

Suppose a text file named story.txt contains the following two lines of text (spaces are shown as ? below

for clarity):

The?house?whirled?around?two?or?three?times?and?rose?slowly

through?the?air.?Dorothy?felt?as?if?she?were?going?up?in?a?balloon.

And another file named stopwords.txt contains some stop words:

We may then remove all stop words in stopwords.txt from the text in story.txt, and save the cleaned

contents in a file named cleaned_story.txt:

house?whirled?around?two??three?times??rose?slowly

through??air.?Dorothy?felt?as?if?she?were?going?up???balloon.

We may also record the number of stop words removed from story.txt in a new file stopwords_count.txt:

Specifically, the input to your program is two strings “text.txt” and “word.txt” where text and word are

any character sequence giving the file names. The file “text.txt” contains lines of text and “word.txt”

contains some stop words, one on each single line (the number of stop words do not exceed 100).

Your program should then create two files “text_cleaned.txt” and “word_count.txt”:

? The file “text_cleaned.txt” contains the same lines of text as in “text.txt” but with all stop words

in “word.txt” being removed (e.g., cleaned_story.txt in the example above).

7

? The file “word_count.txt” contains the same lines of stop words as in “word.txt” but with each

word followed by a number indicating how many times the word has been removed from

“text.txt” (e.g., stopwords_count.txt in the example above).

Your program will also output to the screen the total number of stop words removed.

If your program fails to open any input / output file, it should display "Failed to open [filename]",

where [filename] is the name of the problematic file, and the program will terminate.

You will need to complete the following function in the provide template 3.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.

? ReadStopWordFromFile() for reading stop words from a file and storing them in an array of

struct stop_words (each struct stores a stop word and the corresponding removal

count.)

? RemoveWordFromLine() for deleting all occurrences of a word from a line of text

? RemoveAllStopwordsFromLine() for deleting all occurrences of all stop words from a given

line of text; this function should call RemoveWordFromLine() to delete all occurrences of a

single stop word from the given line

? WriteStopWordCountToFile() for writing the stop words and corresponding removal counts

to an output file

? main() – the main body to read in the stop words and process the text line by line by

removing all stop words from each line, record the removal count and write to the output

files. The main function should call ReadStopWordFromFile(),

RemoveAllStopwordsFromLine(), and WriteStopWordCountToFile()

You should add your own functions wherever appropriate for better program modularity.

Sample test case 3.1

stop_words2.txt story2.txt

Number of stop words removed = 7

Input file – stop_words2.txt

is

are

be

Input file – story2.txt

Monkey is a common name that may refer to groups or species of mammals,

in part, the simians of infraorder Simiiformes. The term is applied

descriptively to groups of primates, such as families of new world

monkeys and old world monkeys. Many monkey species are tree-dwelling

(arboreal), although there are species that live primarily on the ground,

such as baboons. Most species are also active during the day (diurnal).

Monkeys are generally considered to be intelligent, especially the old

world monkeys of Catarrhini.

Output file – stop_words2_count.txt

is 2

8

are 4

be 1

Output file – story2_cleaned.txt

Monkey a common name that may refer to groups or species of mammals, in

part, the simians of infraorder Simiiformes. The term applied

descriptively to groups of primates, such as families of new world

monkeys and old world monkeys. Many monkey species tree-dwelling

(arboreal), although there species that live primarily on the ground,

such as baboons. Most species also active during the day (diurnal).

Monkeys generally considered to intelligent, especially the old world

monkeys of Catarrhini.

Sample test case 3.2 (if the input files cannot be opened)

words.txt text.txt

Failed to open words.txt

Task 4 (C++) Array split

(20 points)

In this question, you are trying to split an array into three equal sum sub-arrays.

Write a C++ program to split an array. Consider an array A of n integers. Determine if array A can

be split into three consecutive parts such that sum of each part is equal. If yes, print the index pair(i,

j) such that (1) sum(arr[0..i]) = sum(arr[i+1..j]) = sum(arr[j+1..n-1]) and (2) ‘i+j’ is the smallest among

all feasible index pairs; otherwise print -1.

Sample test case 4.1:

Input:

5

1 3 4 0 4

Output:

(1,2)

Reason:

First, Sum of subarray arr[0..1] is equal to

sum of subarray arr[2..2] and also to

sum of subarray arr[3..4]. The sum is 4. -> we have pair (1,2)

Second, Sum of subarray arr[0..1] is equal to

sum of subarray arr[2..3] and also to

sum of subarray arr[4..4]. The sum is 4. -> we have pair (1,3)

Since ‘1+2’ < ‘1+3’, we finally output (1,2)

Sample test case 4.2:

9

Input:

11

0 2 1 -6 6 -7 9 1 2 0 1

Output:

(2,7)

Reason:

0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Sample test case 4.3:

Input:

3

2 3 4

Output:

-1

Reason:

No three subarrays exist which have equal sum.

Program input. The first line contains the length of the input array. The second line consists all

array values.

Program output. If we can split the array into three equal-sum sub-arrays, then print the index pair;

Otherwise, print -1.

You will need to complete the following function in the provided template 4.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.

? findSplit() for finding a spliting solution.

Note:

? You are NOT allowed to modify the main() body but you should add your own functions

wherever appropriate for better program modularity.

Hint: You may first calculate the entire sum of the array, and check whether the sum can be split

into three equal sum set or not. If yes, you may use two variables to record sum/3 and 2*sum/3, and

then try to find such split from the beginning of the array recursively.