Concept of Divide and Conquer algorithm

Divide and Conquer:

This method use analogy "smaller is simpler". Divide and conquer algorithms try to form problems simpler by dividing it to sub problems which can be resolved easier than the main problem and then later it join the outcomes to generate a complete solution for the main problem.

Divide and Conquer algorithms: Merge Sort, Quick Sort, and Binary Search.

Divide & Conquer has three main steps:

A) Divide the data into parts.

B) Find sub-solutions for each of the parts recursively (usually).

C) Make the final answer for the original problem from sub-solutions

DC(P) {
  if small(P) then
    return Solve(P);
  else {
    divide P into smaller instances P1,...,Pk, k>1;
    Apply DC to each of these subproblems;
    return combine(DC(P1),...,DC(Pk));
  }
}

Binary Search is not really following the pattern of full version of Divide & Conquer, as it never combines the sub problems solution anyway. Though, let us use this illustration to exemplify the capability of this method.

Binary Search will aid you to find an item in an array. The naive version is to scan via the array one by one (that is, sequential search). Stopping whenever we found the item (success) or whenever we reach the end of array (or failure). This is the simplest and most ineffective method to find an element in an array. Though you will generally end up by employing this technique since not every array is ordered, you require sorting algorithm to sort them first.

Binary search algorithm is employing Divide and Conquer approach to decrease search space and stop whenever it found the item or whenever search space is empty.

Pre-requisite to employ binary search is the array should be an ordered array, the most generally used illustration of ordered array for binary search is searching an item in a dictionary.

Effectiveness of binary search is O(log n). This algorithm was termed "binary" since its behavior is to divide search space into two (binary) smaller parts.

Optimizing your source code:

Your code must be quick. If it can’t be ‘fast’, then it should at least ‘fast enough’. When time limit is 1 min and you’re at present program run in 1 min 10 seconds, you might want to tweak here and there instead of overhaul the complete code again.

Generating vs. filtering:

Programs which produce lots of possible answers and then select the ones which are accurate (visualize an 8-queen solver) are filters. Those which hone in exactly on the accurate answer without any false begins are generators. Usually, filters are simpler and faster to code and run slower. Do the math to see when a filter is good sufficient or if you require to try and make a generator.

Pre-Computation / Pre-Calculation:
Sometimes it is obliging to produce tables or other data structures which allow the fastest possible lookup of an outcome. This is termed as Pre-Computation (that is, in which one trades space for time). One might either compile the Pre-Computed data into a program, compute it when the program begins, or just remember outcomes as you calculate them. A program which must translate letters from upper to lower case whenever they are in upper case can do a much fast table lookup which needs no conditionals, for illustration. Contest problems frequently use prime numbers - many times it is practical to produce a long list of primes for use in another place in a program. 

Decomposition
:

While there are less than 20 basic algorithms utilized in problems, the challenge of combination problems which need a combination of two algorithms for the solution is daunting. Try to divide the cues from different portions of the problem so that you can join one algorithm with a loop or with the other algorithm to solve distinct parts of the problem independently. Note that at times you can use similar algorithm twice on different (or independent) portions of your data to appreciably enhance your running time.

Symmetries:

Most of the problems have symmetries (example: distance between a pair of points is frequently similar either way you traverse the points). The symmetries can be 2-way, 4-way, 8-way and many more. Try to exploit the symmetries to decrease execution time.

For example, with 4-way symmetry, you solve only one fourth part of the problem and then write down the four solutions which share symmetry with single answer (look out for self-symmetric solutions that must only be output once or twice obviously).

Solving forward vs. backward:

Surprisingly, most of the problems work far better whenever solved backwards than whenever employing a frontal attack. Be on lookout for the processing data in an reverse order or building an attack which looks at the data in some order or fashion other than apparent.

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.

©TutorsGlobe All rights reserved 2022-2023.