C++ assignment 代写代做 UML diagram 代写、代写Polymorphism and Complexity C++编程

日期：2018-08-24 09:21

1 General Instructions

All submissions for the practical assignments should be under version control. Submission

procedure remains the same with the first practical assignment.

The directory under version control for this assignment should be named as

If you get stuck on one of the hidden test cases and really cannot resolve it yourself,

please feel free to ask the practical tutors for hints.

We encourage you to finish your work before the practical session and take the session as

consulting time.

2 Problem Description

2.1 Objective

This practical will test your knowledge polymorphism and computational complexity

analysis.

2.2 Design

In a file named design.pdf, describe how you are going to solve the problem and test

your implementation with the test cases you designed based on the stages below.

Testing Hint: it’s easier if you test things as a small piece of code, rather than building

a giant lump of code that doesn’t compile or run correctly. As part of your design, you

should also sketch out how you are going to build and test the code.

2.3 Problem

DNA contains the genetic code that defines the structure of every organism on Earth.

The information in this DNA is copied and inherited across generations from individual

to individual, but may change over generations due to crossover and mutation. A more

1

COMP SCI 1103 & 2103 Algorithm Design & Data Structure Semester 1, 2018

successful individual is more likely to survive to breed, increasing the likelihood that it

will be able to pass on its particular DNA encoding.

In this practical, we are going to represent an individual with a binary “DNA” strand and

mutate it over a number of generations to get a better quality individual. The concepts in

this practical are related to Evolutionary Computation, a field of Artificial Intelligence.

Evolutionary computation has been used to solve a number of problems, including making

virtual creatures, reducing race time for athletes, designing strategies for satellite

coverage, designing turbines... the list goes on. The following articles provide some kind

of overview on evolutionary algorithms. Please have a read if you are interested.

2.3.1 Representation of binary strings

In this practical, we use a class called Individual to represent the DNA which can be

represented by a list of binary digits. Individual has a variable called binaryString

which stores the value of genes.

Your Individual class should at least have the following functions:

• string getString(): The function outputs a binary string representation of the

bitstring list (e.g.“01010100”).

• int getBit(int pos): The function returns the bit value at position pos. It

should return -1 if pos is out of bound..

• void flipBit(int pos): The function takes in the position of the certain bit and

flip the bit value.

• int getMaxOnes(): The function returns the longest consecutive sequence of ‘1’

digits in the list (e.g. calling the function on “1001110” will obtain 3).

• int getLength(): The function returns the length of the list.

• A constructor that takes in the length of the binary DNA and creates the the binary

string. Each binary value in the list should be given a value of 0 by default.

• A constructor that takes in a binary string and creates a new Individual with an

identical list. Note that this involves creating a new copy of the list.

2

COMP SCI 1103 & 2103 Algorithm Design & Data Structure Semester 1, 2018

2.4 Smooth Operator

In order to mutate the DNA, we need a class called Mutator. The Mutator class has a

virtual function mutate that takes in an Individual and an integer index k as parameter

and returns the offspring after mutation. You are also required to derives two classes from

Mutator:

• BitFlip: The mutate function in this class “flips” the k-th binary digit. If k is

greater than the length of the list, we will count in circles. For example, if the

length of the list is 10 and k = 12, then the mutate function will flip the second

digit.

• BitFlipProb: The mutate function in this class goes through every digit in the binary

string and “flips” each of the binary digit with probability p. The probability p

is of type double and in the range of (0,1). p should be initialized in the constructor.

• Rearrange: In this class, the mutate function rearranges the list. The function will

select the k-th digit in the bitstring (again, counting in circles). This digit and all

digits after it (all the way to the tail) will be moved to the start of the list. For

example, if you were rearranging the list (a,b,c,d,e) and k = 3, the function would

return an Individual with the list (c,d,e,a,b).

In your main.cpp, please add an ordinary function

Individual* execute(Individual* indPtr, Mutator* mPtr, int k),

which calls the mutate function on the Individual object and returns the offspring.

Your execute function should decide on which mutator to use based on the actual type

of the Mutator.

2.5 Complexity

In a separate file with name runtime.txt, write down the computational complexity of

your mutate functions. Please include some analysis process and the Big-Oh notation as

a final result

2.6 Main function

The test script will compile your code using g++ -o main.out -std=c++11 -O2 -Wall *.cpp.

It is your responsibility to ensure that your code compiles on the university system. g++

has too many versions, so being able to compile on your laptop does not guarantee that

it compiles on the university system. You are encouraged to debug your code on a lab

computer (or use SSH).

You are asked to create a main function (main.cpp). It takes in one line of input.

binarystr1 k1 binarystr2 k2

Two Individual objects should be created using binarystr1 and binarystr2. The BitFlip

mutation and Rearrange mutation are invoked on the first and the second Individual

3

COMP SCI 1103 & 2103 Algorithm Design & Data Structure Semester 1, 2018

with index k1 and k2 respectively through execute function. The output of your main

function should be the two resulting binary string and the longest consecutive sequence

of 1-bits of the second offspring. k1 and k2 are both positive integers. Please separate

the results using one space.

Sample input: 000000 2 0111 2

Sample output: 010000 1110 3

Sample input: 001100 7 011100 3

Sample output: 101100 110001 2

3 Marking Scheme

Deadline: 10:00am 4th May. No marks for submissions later than 10:00am

7th of May.

Your submission should contain at least design.pdf, main.cpp and other cpp files and

header files. The design document should be submitted in the first submission to the

websubmission system.

This practical is worth 3% of your final mark.

This practical assignment is marked out of 9.

• Design (2 marks):

– UML diagram of central classes and explanation of core functions (1 mark)

– Details of your own test cases/schemes (1 mark)

• Style (2 marks):

– Proper usage of C++ language elements and paradigm (1 mark)

– Comments on non-trivial code blocks and functions (1 mark)

• Functionality (2 marks):

– Passing public test cases (1 mark)

– Passing hidden test cases (1 mark)

• Complexity Analysis (3 marks):

– Runtime analysis of the three mutate functions