Algorithms HOMEWORK 4 Solution

Description

• Objectives

The objective of this assignment is to make yo familiar with the object oriented programming concepts including inheritance, polymorphism and abstract base class.

Keywords: inheritance, polymorphism, abstraction, dynamic type casting

• Problem

In this assignment, you are going to implement a scenario which includes a series of biological events occuring when some types of foreign microorganisms enter into human cells. MicroOrganism and Cell will be the main classes that play the leading role. Other than those, there will be other classes which play helper role, yet very important in terms of expressing constituents of the main classes. In this homework, the ˆthings to greet you are as follows:

You are going to make each microorganism found a compatible human cell to live in. Here, the compatibility will be measured in terms of their shape and size. Shapes of microorganisms will be one of those 3 basic 2D polygons: triangle, circle or square. Cells can be any type of 2D polygons. Microorganisms and cells which have the same type of shape and size (edge length or radius) will

1. • be matched. Inputs will be provided with unique matchings.

Microorganisms will be implemented with inheritance. Each microorganism type will be classi ed according to their shapes and each shape will be stated as a di erent class: Circular, Triangular and Squadratic derived from abstract MicroOrganism base class. Each microorganism type will show a di erent reaction in the human cell and they will necessitate di erent type of implementa-

1. • tions because of their shape by nature.

Since the cells initially can not identify the microorganisms, they will refer all just as MicroOrganism. This will cost dearly to them since some of those are really harmful viruses such as Covid-19 and kill the cell.

¹asiler@ceng.metu.edu.tr All rights are reserved.

• For you, matching a cell with a microorganism will not be so easy because cells are not classi ed according to the shape of their boundary. Instead, they will have a cell wall de ning a shape for their boundary and this cell wall will consist of many partial staright and circular wall segments. In order to arise shape of the cell wall, you need to combine those partial wall segments.

In the homework, in order to express the wall segments used in the cell wall, Wall class will be used. This is nothing but just the representation of a straight line segment between two points (Points are implemented with Particle class). However, for circular segments, you are going to use CurvyWall class which is a derivation of the base class Wall. CurvyWall objects will be de ned

• by three points instead of two, where the third point is center of the curve segment.

Lastly, Tissue class is the place where you hold the cells. In fact, this class was initially designed for you to implement a plasma treatment to clean the microbic tissue by replacing it with a healthy one in some kind of R-Tree structure. Later, it was decided to remove that part since it makes the homework really tiring. Although the related method declarations were left in the headers for those who wants to struggle with “wheels within a wheel”, you are not expected to do that part.

3.2 Wall.cpp & CurvyWall.cpp

Wall class and its derived class CurvyWall will be used to give a shape to cells and microorganisms. Wall is a base class which represents straight line segments. CurvyWall is a derived class of Wall which representsˆ circular curve segments. Both Wall and CurvyWall objects can be constructed in two ways:

Wall(float) is to construct the wall by specifying just a length without de ning an exact location for it. This option is presented to you in case that you want to use those kinds of walls to de ne the shapes for microorganisms (Since Microorganisms do not have an exact location until they penetrate into a cell). Correspondingly, CurvyWall(float, float) is to construct a curvy wall by specifying just a length (for the arc segment it represents) and the radius without de ning an exact

• location for it. The right side of Figure 2 shows the examples.

Wall(const Particle&, const Particle&) is to construct the wall whose initial and nal points are the particles given in the rst and second parameters, respectively. Correspondingly, CurvyWall(const Particle&, const Particle&, const Particle&) is to construct curves whose initial, nal and center points are the particles given in the rst, second and third parameters, re-spectively. This type of walls are used to de ne the shape of cells (Cells have a de nite location). The leftt side of Figure 2 shows the examples.

y

x

Figure 2: The left side of the Figure shows the walls and curvywalls constructed with a de nite location (the second type of construction). This type of walls are used to give shape to Cells. Orange points on them are their initial, nal and center Particles. On the other hand, the right side shows the walls and curvywalls constructed with just a length and radius (the rst type of construction). This type of walls are used to give shape to Microorganisms until they get position in a certain location (inside a cell). The numbers next to them shows their ids. The ones with the same id on both left and right sides are actually the identical walls. They just di er in terms of their construction.

3.3 Cell.cpp

This is the class to de ne a cell. In this assignment, cells are the 2D geometric polygons. They can be given in any type of 2D closed pattern in the inputs. Their shapes will be de ned as a sequence of straight lines (data type is Wall, given in Section 3.2) and curves (data type is CurvyWall, given in Section 3.2). Actually, this set of line/curve sequence represents nothing but the cell wall. The walls (lines/curves) constructing the cell wall will be given in counterclockwise order. Even for the most basic type of cells such as triangles, squares and circles, the cell wall can be de ned with many partial wall segments instead of just giving 3 or 4 edges, or one curvy wall, respectively. The left side of Figure 3 shows cell examples.

Without regarding the shape of its cell wall, all cells is an object of Cell class. Each cell is located on a certain piece of some tissue. Location of a cell is naturally de ned by the cell walls which were constructed between certain 2D points (data type is Particle, given in Section 3.1). A cell can accept only the microorganisms which have the exact shape of the cell itself. The details about the microorganisms are given in Section 3.4.

y

x

Cells Microorganisms

Figure 3: The left side of the Figure shows sample cells whereas the right side shows sample microorganisms. Cells can be formed up with many Wall and CurvyWall segments. The numbers inside them are their ids and the corresponding objects with the same ids on the right side are the microorganisms identical to those cells. Note cells can be any type of 2D polygons whereas microorganisms can be either triangle (Triangular), or circle (Circular), or square (Squadratic).

In the Cell class, there is a method named as StrengthenCellWall() which is supposed to com-bine the partial wall segments connectable to each other (The details of which types of walls can be connected with which types are given in +operator() of Wall class in the header le). You can con-sider StrengthenCellWall()) method as a “simpli er” for the cell shape. It reduces the partial straight line and curve segments on the cell wall and extracts out the plain form of the cell. The e ect of StrengthenCellWall() is shown in Figure 4.

microorganism in terms of their lengths. During the construction, edges of a Triangular may not be given in a certain order (clockwise or counterclockwise).

Actually, Triangular microorganisms are Covid-19 viruses and they kill the cell that they are in. Moreover, this Covid-19 virus has a RNA which can mutate. In the homework, the RNA structure of Covid19 is represented by NucleoBase class which is given in Section 3.5. Mutation of a RNA occurs via an other Triangular microorganism’s getting involved such that two microorganisms interchange their corresponding Adenin-Urasil and Guanin-Sitozin nucleobases in non-matching parts of their RNAs. The details are in Section3.5.

other are marked in both sides of the sequences. When the di ering middle parts are detected, those are started compare and each Adenin-Urasil and Guanin-Sitozin nucleobases at the corresponding positions are replaced with each other. The other nucleobase correspondences in that middle part are deleted. An example scenario is given on strings in Figure 6.

3.8 Main.h & Input Files

In the assignment, cells and microorganisms may also be supplied from txt es (other than the ones de ned in main()). Therefore, there will be given 2 command line arguments: The rst one is the le name including cells and the second one is the le name including microorganisms. In Main.h, you are provided two implemented methods: ReadMicroOrganisms() and ReadCells() which are used to read the le of microorganisms and le of cells, respectively. You should not modify this header le. Since le reading part is already implemented for you not to exert additional e ort on reading, you do not need to know the details about content of the input les. Nonetheless, in case that you need or wonder, the format of the les are given below:

Cells.txt File

It may have a di erent name other than “Cells.txt”.

N M

//

N: number

o f

p a r t i c l e s ,

M:

number

o f c e l l s

first

particle

//

format :

i d

x

c o o r d i n a t e

y c o o r d i n a t e

second

particle

.

.

.

Nth

particle

id

W

//

f i r s t c e l l , W:

number o f

w a l l s

first

wall

//

i f

s t r a i g h t

w a l l , format : s

p1

p2

second

wall

//

>

’ s ’

f o r

s t r a i g h t

.

//

=>

p1

and

p2

a r e i d s

o f

t h e

i n i t i a l and

f i n a l p a r t i c l e s

.

Wth

wall

id W

// s e c on d c e l l

first

wall

//

i f

curvy

w a l l ,

format :

c

p1

p2

p3

second

wall

//

>

’ c ’

f o r

curvy

.

//

=>

p1 ,

p2

and p3 a r e

i d s

o f

t h e

i n i t i a l ,

f i n a l

//

and

c e n t e r p a r t i c l e s

.

Wth

wall

………

//

Another

c e l l

b l o c k

………

//

Another

c e l l

b l o c k

………

//

.

………

//

.

………

//

.

………

//

Mth

c e l l

Microorganisms.txt File

It may have a di erent name other than “Microorganisms.txt”.

N	//	N: number o f m i c r o o r g a n i s m s
id	//	i d o f t h e microorganism
microorganism data	//	format : <type> <r a d i u s / edge l e n g t h >

id			// i f ” C i r c u l a r d”
microorganism		data	//	> C i r c u l a r whose		r a d i u s		i s d
id			// i f ” S q u a d r a t i c d”
microorganism		data	//	=> S q u a d r a t i c	whose		edge	l e n g t h	i s d
Another	microorganism		//	i f ” T r i a n g u l a r	d1 d2 d3
Another	microorganism		//	xxxxxxxxxx . . . x”
.			//	=> T r i a n g u l a r whose edge				l e n g t h s	a r e d1 , d2 and d3
.			//	and whose RNA		i s	e q u a l	t o xxxxxxxxxxxxxx . . . x
.			//	where each	r e f e r s		t o a	n u c l e o b a s e .
.			//	RNA can be	o f	any	l e n g t h .
.
Another	microorganism		//	Nth microorganism

4 ˆGrading

5 ˆRegulations

Memory-leak: The class destructors must free all of the used heap memory. Any heap block, which is not freed at the end of the program will result in grade deduction. Please check your codes using valgrind –leak-check=full for memory-leaks.

Allowed Libraries: You may include the libraries supplied in header les. Use of any other library (especially the external libraries found on the internet) is forbidden.

Programming Language: You must code your program in C++. Your submission will be compiled with g++ on department lab machines. You are expected to make sure your code compiles successfully with g++ using the ags -ansi -pedantic.

Late Submission: You have a total of 10 days for late submission. You can spend this credit for any of the assignments or distribute it for all. For each assignment, you can use at most 3 days-late.

• Cheating: In case of cheating, the university regulations will be applied.

Newsgroup: You must follow the Ceng242 newsgroup on cow.ceng.metu.edu.tr for discussions and possible updates on a daily basis.

• Submission

Submission will be done via Ceng Class. Do NOT write a main function in any one of the les. You are going to submit the following les by directly compressing as HW4.zip:

Particle.h, Particle.cpp

Wall.h, Wall.cpp

CurvyWall.h, CurvyWall.cpp

Cell.h, Cell.cpp

MicroOrganism.h, MicroOrganism.cpp

Circular.h, Circular.cpp

Squadratic.h, Squadratic.cpp

Triangular.h, Triangular.cpp

• NucleoBase.h, NucleoBase.cpp Tissue.h, Tissue.cpp

You are not going to submit a Main.cpp le. I will use my own Main.cpp during grading. There is a single Main.cpp among the homework documents. You may use it while developing and debugging you codes, if you like.

Note: The submitted zip le should not contain any directories. The following command sequence is expected to run your program on a Linux system.

• unzip HW4.zip

• make clean

• make all

• make run

• -optional- make valgrind

10