C++

2.3.1 Representation of binary string

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 ip 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 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.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 o spring after mutation. You are also required to derives three classes from Mutator:

BitFlip: The mutate function in this class read the binary string and \ ips" 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 ip the second digit.

BitFlipProb: The mutate function in this class goes through every digit in the bi-nary string and \ ips" 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 de ned 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 o spring. Your execute function should decide on which mutator to use based on the actual type of the Mutator.

2.5 Complexity

In a seperate le 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 nal 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 rst and the second Individual

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 o spring. 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