Data Structures and Algorithms: Finding the Largest Circle's Area

This assignment provides a detailed solution to the problem of finding the largest circle that fits inside a target circle, using data structures and algorithms. The solution begins by breaking down the problem into sub-problems, employing a divide and conquer approach. These sub-problems include calculating the area of the target circle, calculating areas of individual circles, comparing areas to find the largest, and finally, comparing the largest circle to the target circle. The plans involve using formulas, for loops, and functions for comparison. The implementation is demonstrated through C++ code, including the use of loops, functions, and conditional statements. The solution undergoes testing to ensure it provides the correct results. The complete C++ code is provided, along with a bibliography citing the sources used. The solution covers the process from problem definition to the final code implementation, offering a complete and practical understanding of the algorithm.

1
Data Structures and Algorithms
Name
Institution
Topic
Instructor

2
Data Structures and Algorithms
The problem................................................................................................................................................3
Split into sub problems................................................................................................................................3
Plans to solve the sub problems..................................................................................................................4
Implementation of the plans.......................................................................................................................4
Test solution................................................................................................................................................5
Complete code for the program in C++.......................................................................................................7
Bibliography................................................................................................................................................9

3
Data Structures and Algorithms
The problem
The problem being solved by this algorithm is to find the largest circle that is completely inside
the target circle from a list of circles provided.
The input to this algorithm is the list of the circles, the target circles and their radiuses.
Examples
The following represents the list of inputs of the circles available
(Weiss 2012)
Below is a representation of the circles’ radiuses.
A representation of the target circle input
The output is the largest circle that is completely inside the target circle.
Split into sub problems
The problem is sub divided into sub problems through divide and conquer algorithm (Blelloch
et.al 2008, January). The sub problems are then easy to solve. Once the solutions for the sub
problems are found, they are put together to form a complete solution to the problem.
The problem has been broken down into four sub problems
First calculate the target circle area from the input of its radius acquired from the user.
Calculation of the areas of the individual circles from the inputs acquired from the user or the
person administering the system.

4
Data Structures and Algorithms
Compare the areas of the individual circles to one another to figure out which one is the largest
of them all.
Finally compare area of the largest circles from the list to the area of the target circle.
Plans to solve the sub problems
Calculation of the area of the target circle is done directly by stating the formula of calculating
the area of a circle from the radius provided.
Calculation of the areas of the circles in the list is to be done using for loop
Comparison of the individual circle areas from the circle array list to find the maximum area is
done using a function.
Comparison of the largest circle to the target circle is done using the if statement
Implementation of the plans
Calculation of the area of the target circle
Use of for loop to calculate the area of the individual circles in the array list (Hundt 2011)
The for loop code calculate the areas of the circles in the array in an incremental manner starting
with the circle at index zero continuing depending on the number of items in the array. In this
case the array consists of six items.

5
Data Structures and Algorithms
Use of a function in the comparison of the individual areas which are held in an array of areas
(Deitel and Deitel 2008)
The function (Takenaka et.al 2012) float largest compares the areas in every index of the array of
areas of the individual circles. After comparing the values in every index, the function returns
the maximum value.
Use of if statement to compare the maximum circle from the array to the target circle.
If the largest area from the array of areas is less than the area of the target circle, then the largest
candidate circle that is completely inside the target circle is found and displayed.
Test solution
This is the deployment of the combination of the sub solutions to form the complete solution to
the problem. The aim of this stage is to find out whether the code work as programmed or give
the required feedback.

6
Data Structures and Algorithms
The results are as expected according to the above test program
The program calculates the area of the target circle from the input of radius.
The program calculates the areas of the individual circles in the array and outputs the values for
each circle and compares them to one another to find the circle that has the maximum area from
the list.
It finally compares the area of the target circle with the area of the largest circle from the list.
After comparing and finds that the largest circle from the list is small it outputs the area of the
largest candidate circle that is completely inside the target circle.

7
Data Structures and Algorithms
Complete code for the program in C++
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch,
system("pause") or input loop */
float largest(float area[], int a)
{
int i;
float max = area[0];
for (i = 1; i < a; i++)
if (area[i] > max)
max = area[i];
return max;
}
int main(int argc, char** argv) {
int circles[6] = {0,1,2,3,4,5};
const int size = sizeof(circles);
float radius[6];
float area[6];
float pie = 3.142;
int n;
float radiusofTarget;
float areaofTarget;

8
Data Structures and Algorithms
cout<<"Enter the radius of the target radius\n";
cin>>radiusofTarget;
areaofTarget = 2*pie*radiusofTarget*radiusofTarget;
cout<<"Area of Target Circle is"<< areaofTarget<<"\n";
for(n=0; n<=5; n++){
cout<<"Enter radius for circle"<< n<<"\n";
cin>>radius[n];
area[n] = 2*pie*radius[n]*radius[n];
cout<<area[n]<<"\n";
}
int a = sizeof(area)/sizeof(area[0]);
if(largest(area, a) < areaofTarget){
cout<<"Largest circle is"<< largest(area, a);
}
return 0;
}

9
Data Structures and Algorithms
Bibliography
Blelloch, G.E., Chowdhury, R.A., Gibbons, P.B., Ramachandran, V., Chen, S. and Kozuch, M.,
2008, January. Provably good multicore cache performance for divide-and-conquer algorithms.
In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (pp.
501-510). Society for Industrial and Applied Mathematics.
Kay, A(Lecturer).(2018, May 5).Data Structures and Algorithms. A Problem Solving- Process.
Retrieved from https://dsaa.werp.site/post/a-problem-solving-process/
Takenaka, T., Takagi, M. and Inoue, H., 2012, August. A scalable complex event processing framework
for combination of SQL-based continuous queries and C/C++ functions. In Field Programmable Logic and
Applications (FPL), 2012 22nd International Conference on (pp. 237-242). IEEE.
Hundt, R., 2011. Loop recognition in c++/java/go/scala. Proceedings of Scala Days, 2011, p.38.
Weiss, M.A., 2012. Data structures & algorithm analysis in C++. Pearson Education.
Deitel, P.J. and Deitel, H.M., 2008. C++ how to Program. PearsonPrentice Hall.