Practical 6: Polymorphism and Complexity

Due date: 10:00am, 4 May 2018

 

 

 

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

 

https://version-control.adelaide.edu.au/svn/aXXXXXXX/2018/s1/adds/assignment6/

 

where aXXXXXXX is your student ID.

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

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 mak- ing 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.

http://www.perlmonks.org/?node_id=298877

http://www.genetic-programming.com/published/usnwr072798.html

 

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.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 bi- nary 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

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

代写CS&Finance|建模|代码|系统|报告|考试

编程类：C代写,JAVA代写 ,数据库代写,WEB代写,Python代写,Matlab代写,GO语言,R代写

金融类：统计，计量，风险投资，金融工程，R语言，Python语言，Matlab，建立模型，数据分析，数据处理

服务类：Lab/Assignment/Project/Course/Qzui/Midterm/Final/Exam/Test帮助代写代考辅导

天才写手,代写CS,代写finance,代写statistics,考试助攻

E-mail:850190831@qq.com   微信：BadGeniuscs  工作时间：无休息工作日-早上8点到凌晨3点

---

如果您用的手机请先保存二维码到手机里面，识别图中二维码。如果用电脑，直接掏出手机果断扫描。