讲解CS100、辅导C/C++程序语言、讲解OJ留学生、C/C++设计辅导

CS100 Homework 4 (Fall Semester2018)

Due time: 11:59 pm, December 6,2018

Homework 4 comprises 3 problems. Important notes:

The templates for all problems have been submitted to your gitlab project repositories. It is

crucialthat you take them as astarting point,they already implement the entire I/O

functionality plus a substantial part of the interfaces. The sections that you should modify

are clearly marked.

As in the previous homework, we will use OJ for grading for unified compilation andtesting.

However, pleasebeware the rules of using OJ! Do not abuse OJ, you should submit your

solution no more than 30 times,and theshortest interval between two submissions is 2

minutes. As in the previous homework, any violations of these rules will lead to a

(cumulative!) reductionof 10% of the total score. It is implicit that you should compile and

test your code locally on your machine before you startsubmitting yoursolution to OJ.

Pleasealso beware thenaming rule. You shouldchange your name in OJ under settings to

your real Chinese name.No exceptions willbemadethis time! Please review the related

posts on Piazza!

The test examples are also uploaded toyour gitlab accounts. For convenient testing, you

may forward thetest examples to your binary such that std::cin will directly read from

the file. For example, suppose you callyour binary main, and you want to test the output of

2.in. In your bash, simply type

./main < 2.in

Problem 3 may reuse the code from problem 2, so if youcorrectly solveproblem2, it will be

of great help for problem 3 as you may simply copy-paste the code for the template matrix.

All problems are to beimplemented in a singlefile that can be copy-pasted to OJ.

This homework depends at leaston the C++-standard C++11, so please use a recent

compiler. The standard may haveto be provided to the compiler,as in

g++ -std=c++11 -stdlib=libc++ solution3.cpp -o main

Homework 4 /Problem1

Problem1 introduces a datastructure which we denote a HyperVector. The idea of the

HyperVector is to provide the benefits of a vector (which is efficient random-access to the

data, i.e. efficient look-up ofany element of the vector), while at the same time providing

similarbenefits than alist, which is a computational complexity for erase/insert/push-back

operations thatremainslargelyindependent of the overall number of elements stored in

the container. For the purpose of problem 1, the designis kept very simple, and only the

push-back functionalityis implemented.The HyperVectormay hence be explained as

follows:

The data is internallystored using a std::vector< std::vector<T>* >, where T is

a template parameter. In other words, it is a vector of vector-pointers.

The internal vectors representbucketsof dataand areallocated on demand. These buckets

may at most hold VALUES_PER_BUCKET elements. This spaceis reserved as a new bucket

When pushing back a new element into the hyper-vector,the element will be added to the

currentbucket if it isnot yetfull, respectively added to a new bucketif there is no data in

the container yet, or the previous bucket is full.

This functionality prevents the actualdata ofthe container from ever being copied around

due to insufficient contiguous memory space, data does in fact not have to be contiguous in

memory. On the other hand, efficient random access is still given, as an index into the hypervector

can easily be transformed into an external and internal bucket index (notably by VALUES_PER_BUCKET, and considering the quotient and remainder or this

operation.

As seenin class, having a container that permits random accessallows for theapplication of

the efficient std::sort algorithm. The latter however depends on the availability of STL

random-access iteratorsinto the elements of the container. An implementation of

HyperVector is already provided, your task is to implement the random-access iteratorfor

the hyper-vector, called HyperVectorIterator.

Hint: Your iterator needs to inherit from the STL iterator

std::iterator< std::random_access_iterator_tag, T >

and it needs to implement the followinginterface:

T & operator*();

T & operator->();

T & operator[](int n);

HyperVectorIterator<T> & operator++();

HyperVectorIterator<T> operator++(int);

HyperVectorIterator<T> & operator--();

HyperVectorIterator<T> operator--(int);

HyperVectorIterator<T> & operator+=( int n );

HyperVectorIterator<T> & operator-=( int n );

HyperVectorIterator<T> & operator+=( const

HyperVectorIterator<T> & that );

HyperVectorIterator<T> & operator-=( const

HyperVectorIterator<T> & that );

HyperVectorIterator<T> operator+( int n ) const;

HyperVectorIterator<T> operator-( int n ) const;

int operator+( const HyperVectorIterator<T> & that ) const;

int operator-( const HyperVectorIterator<T> & that ) const;

bool operator== ( const HyperVectorIterator<T> & that ) const;

bool operator!= ( const HyperVectorIterator<T> & that ) const;

bool operator< ( const HyperVectorIterator<T> & that ) const;

bool operator> ( const HyperVectorIterator<T> & that ) const;

bool operator<= ( const HyperVectorIterator<T> & that ) const;

bool operator>= ( const HyperVectorIterator<T> & that ) const;

Part ofthe homework task is tohave a good intuition about what these functions are

supposed to do,and research online if in doubt. The implementation is tested through a

main function that is already provided.It simply readsan arbitrary number of random real

numbersfrom the console and pushes them back  into

sorting algorithm, and finallyprints the sorted elements backto the console.

Input description: Files containing random numbers similar to the ones employed by OJ are

alreadyprovided. For local testing youmay forward them to std::cin by simply running

./main < 1.in

Ouput description: The program simply outputs the

number is followed by awhite-space, and the last whitespace is followed byand end-of-line

character. The I/O functions are pre-implemented, so you shouldnot encounter any

problems here.

Homework 4/ Problem 2

Problem2 is about the implementation of a template matrix class. The class should heavily

rely onoperators to enable convenient encoding of arithmetic operations (seemain

function in thetemplate for examples). The exact interface is as

Matrix( int rs, int cs, T val = 0 );

virtual ~Matrix();

Matrix<T> & resize( int rs, int cs, T val = 0 );

T & operator()( int r, int c );

const T & operator()( int r, int c ) const;

size_t rows() const;

size_t cols() const;

Matrix<T> block( int r, int c, int h, int w ) const;

Matrix<T> & setBlock( int r, int c, int h, int w, T & val );

Matrix<T> & setBlock( int r, int c, const Matrix<T> & val );

Matrix<T> & setIdentity();

Matrix<T> & setConstant( const T & val );

Matrix<T> & setZero();

Matrix<T> transpose() const;

Matrix<T> & transposeInPlace();

Matrix<T> operator+ ( const Matrix<T> & op ) const;

Matrix<T> & operator+=( const Matrix<T> & op );

Matrix<T> operator- ( const Matrix<T> & op ) const;

Matrix<T> & operator-=( const Matrix<T> & op );

Matrix<T> operator* ( const T & op ) const;

Matrix<T> operator* ( const Matrix<T> & op ) const;

Matrix<T> & operator*=( const T & op );

Matrix<T> hadamard ( const Matrix<T> & op ) const;

T sum() const;

Part ofthe homework isto prove an intuitive understanding of what theabove function are

supposed to do.The matrix implementation will be tested in a pre-implementedmain

function that implements a fixed sequence of arithmetic operations testing a large part of

the interface for correct functionality. It reads in a random matrix from the console starting

with a first line in which the number of rows and columns are to be provided, and finishing

with further lines eachone containing the realnumbersof that row in the matrix. The result

of the arithmetic operations isagain output onthe console.

Input description: Files containing random numbers similar to the

alreadyprovided. The first line of thefile contains the number of rows and columns in the

matrix.For local testing you may forward them to std::cin by simply running

./main < 1.in

Ouputdescription: The program simplyoutputsthe matrix results of the operations onto

the console. The results are printed row-by-rowfor each matrix. Each number is followed by

a white-space, and the last whitespace behind that lastnumber in the row is followed by an

end-of-line character. The I/O functions are pre-implemented, so you should notencounter

any problems here. No empty lines are inserted betweenthe matrices.

Homework4/ Problem 3

Problem3 consists of implementing a hyper-threaded kernel-convolution. Kernel

convolutions are important in several domains of computer science, suchas machine

learning (deep learning, CNNs,

https://en.wikipedia.org/wiki/Convolutional_neural_network ) orimageprocessing

(https://en.wikipedia.org/wiki/Kernel_(image_processing) ). In general terms,the operation

consists of generating an output matrixfrom a given input matrix of similar size. Let orc be

the value of the element in rowr and column c in the output matrix. It is given as a result of

convolving the values around the same element in the input matrix A with a small kernel

matrix K. Let (2h+1) and (2w+1) be the height and widthof the kernel. The value of an

elementin the output matrix isthen given as follows:

"# = "+,-.,#+/-0

.12:4, 012:4/

where arc denotes the element of the input A inrow r and column c. The operation may

also berewritten in terms of an element-wise matrix multiplication (also called the

Hadamard product):

"# = (, 2 + 1,2 + 1 )

where sum() is a function that returns the sum of all the elements of the matrix parameter,

* denotes the Hadamard product, and A(x,y,h,w) denotes the sub-block ofA withtop-left

corner located at (x,y) and size hxw.

Your tasks: Adda generic template matrix classto holdthe input and output matrices, as

well asthe kernel itself. The main function isalreadyimplemented, and it reads the input

matrix from the console, along with an integer denotinga kernel-type. Depending on this

integer, a certain kernel is then initialized (pre-coded). The main function also defines an

output matrix of the same size than theinput matrix. It finally starts four threads which

computethe elements ofthe output matrix according to the above equation. Each thread

notablytakes care of 25 % of the output matrix. Each thread is provided an individual

instance of

struct KernelApplicationJob {

Matrix<float> * src;

Matrix<float> * K;

Matrix<float> * dst;

size_t threadIndex;

size_t numberThreads;

};

which passes the required information to the thread (the input/src matrix, the kernel

matrix,and theoutputmatrix/dst matrix). It furthermore communicates the number of

threads, and a thread-index. The part of the image thatis being dealt with in each particular

threadshould notably be chosen as a function of the thread-index. The thread function to

be implementedhas thesignature

void kernelApplicationThread( KernelApplicationJob & my_job );

Note: The output matrixcontains a margin of width h orw for which values can not be

computed since the corresponding field from theinput matrix would exceed the image

region.These values are simplyset to0! (Beware however thath and w can be different for

each kernel).

Input description: Files containing random matrices similar to the ones employed by OJ are

alreadyprovided. The first line contains the number ofrows, columns, and the type of the

kernel to be applied (anumber between0 and 5). For local testing you may forward the prearranged

files to std::cin by simply running

./main < 1.in

Ouput description: The program simply outputs the matrix results after the convolution

onto the console. The results are printed row-by-row for each matrix. Each number is

followed by a white-space, and the lastwhitespace behind that last number in the row is

followed by andend-of-line character. The I/O functions are pre-implemented, so you

should not encounter any problems here.