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

CS100 Homework 4 (Fall Semester2018)

Due time: 11:59pm, 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

crucial that 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 submissionsis 2

minutes. As in the previous homework, any violations of these rules will leadto 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 your solution to OJ.

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

your real Chinese name.No exceptions will be made this 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 directlyread 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 you correctly solve problem 2, 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 single file 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 sametime providing than a list, which is a computational complexityfor

operations thatremainslargelyindependent of the overall number of elements stored in

the container. For thepurposeof problem 1, the design is 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>* >,whereT is

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

The internal vectors represent bucketsof dataand areallocated on demand.These buckets

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

is installed

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

currentbucket if it isnot yetfull, respectively added to a new bucket ifthere 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

dividing by VALUES_PER_BUCKET, and considering the quotient and remainder or this

operation.

As seenin class, having a container that permits random accessallows for the application 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 iterator for

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 toimplement 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 functionsare

supposed to do,and research online if in doubt. The implementation is testedthrougha

main function that is already provided.It simply readsan arbitrary number of random real and pushes them back into a hyper-vector. It then calls the

sorting algorithm, and finally prints the sorted elements back to the console.

Input description: Files containing are

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

./main < 1.in

Ouput description: The program simply outputs the sorted numbers to the console. Each

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

character. The I/O functions are pre-implemented, so you shouldnot encounterany here.

Homework 4/ Problem 2

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

rely onoperators to enable convenient encodingof arithmetic operations (see main

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

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 number of rows and columns are to be provided, and finishing

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

of the arithmetic operations isagain output onthe console.

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

alreadyprovided. The first line of thefile contains the number of rows andcolumnsin the

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

./main < 1.in

Ouput description: The program simply outputs the matrix results of the operations onto

the console. The results are printed row-by-rowfor each matrix. Each numberis 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 shouldnot encounter

any problems here. No empty lines are inserted between the matrices.

Homework 4/ 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 similarsize. Let orc be

the value of the element in rowr and column c in the output matrix. Itis 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):

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 with top-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 itreads 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 functionalso 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 isprovided anindividual

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 theoutput matrix/dst matrix). It furthermore communicates the number of

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

thread should notably be chosen as afunction of the thread-index. The thread function to

be implemented has the signature

void kernelApplicationThread( KernelApplicationJob & my_job );

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

computed since the corresponding field from theinput matrix would exceed theimage

region.These values are simplyset to 0! (Beware however that h and w can bedifferent 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 between 0 and 5). For local testing you may forward the prearranged

files to std::cin by simply running

./main < 1.in

Ouputdescription: The program simplyoutputsthe matrix results after theconvolution

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 inthe rowis

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

should not encounter any problems here.