COURSES
MBAData Science & AnalyticsDoctorate Software & Tech AI | ML MarketingManagement
Professional Certificate Programme in HR Management and AnalyticsPost Graduate Certificate in Product ManagementExecutive Post Graduate Program in Healthcare ManagementExecutive PG Programme in Human Resource ManagementMBA in International Finance (integrated with ACCA, UK)Global Master Certificate in Integrated Supply Chain ManagementAdvanced General Management ProgramManagement EssentialsLeadership and Management in New Age BusinessProduct Management Online Certificate ProgramStrategic Human Resources Leadership Cornell Certificate ProgramHuman Resources Management Certificate Program for Indian ExecutivesGlobal Professional Certificate in Effective Leadership and ManagementCSM® Certification TrainingCSPO® Certification TrainingLeading SAFe® 5.1 Training (SAFe® Agilist Certification)SAFe® 5.1 POPM CertificationSAFe® 5.1 Scrum Master Certification (SSM)Implementing SAFe® 5.1 with SPC CertificationSAFe® 5 Release Train Engineer (RTE) CertificationPMP® Certification TrainingPRINCE2® Foundation and Practitioner Certification
Law
Job Linked
Bootcamps
Study Abroad
Master of Business Administration (90 ECTS)Master of Business Administration (60 ECTS)Master in Computer Science (120 ECTS)Master in International Management (120 ECTS)Bachelor of Business Administration (180 ECTS)B.Sc. Computer Science (180 ECTS)MS in Data AnalyticsMS in Project ManagementMS in Information TechnologyMasters Degree in Data Analytics and VisualizationMasters Degree in Artificial IntelligenceMBS in Entrepreneurship and MarketingMSc in Data AnalyticsMS in Data AnalyticsMaster of Science in AccountancyMS in Computer ScienceMaster of Science in Business AnalyticsMaster of Business Administration MS in Data ScienceMS in Information TechnologyMaster of Business AdministrationMS in Applied Data ScienceMaster of Business AdministrationMS in Data AnalyticsM.Sc. Data Science (60 ECTS)Master of Business AdministrationMS in Information Technology and Administrative Management MS in Computer Science Master of Business Administration MBA General Management-90 ECTSMSc International Business ManagementMS Data Science MBA Business Technologies MBA Leading Business Transformation Master of Business Administration MSc Business Intelligence and Data ScienceMS Data Analytics MS in Management Information SystemsMSc International Business and ManagementMS Engineering ManagementMS in Machine Learning EngineeringMS in Engineering ManagementMSc Data EngineeringMSc Artificial Intelligence EngineeringMPS in InformaticsMPS in Applied Machine IntelligenceMS in Project ManagementMPS in AnalyticsMS in Project ManagementMS in Organizational LeadershipMPS in Analytics - NEU CanadaMBA with specializationMPS in Informatics - NEU Canada Master in Business AdministrationMS in Digital Marketing and MediaMS in Project ManagementMaster in Logistics and Supply Chain ManagementMSc Sustainable Tourism and Event ManagementMSc in Circular Economy and Sustainable InnovationMSc in Impact Finance and Fintech ManagementMS Computer ScienceMS in Applied StatisticsMS in Computer Information SystemsMBA in Technology, Innovation and EntrepreneurshipMSc Data Science with Work PlacementMSc Global Business Management with Work Placement MBA with Work PlacementMS in Robotics and Autonomous SystemsMS in Civil EngineeringMS in Internet of ThingsMSc International Logistics and Supply Chain ManagementMBA- Business InformaticsMSc International ManagementMS Computer Science with AIML ConcentrationMBA in Strategic Data Driven ManagementMaster of Business AdministrationMSc Digital MarketingMBA Business and MarketingMaster of Business AdministrationMSc Digital MarketingMSc in Sustainable Luxury and Creative IndustriesMSc in Sustainable Global Supply Chain ManagementMSc in International Corporate FinanceMSc Digital Business Analytics MSc in International HospitalityMSc Luxury and Innovation ManagementMaster of Business Administration-International Business ManagementMS in Computer EngineeringMS in Industrial and Systems EngineeringMSc International Business ManagementMaster in ManagementMSc MarketingMSc Business ManagementMSc Global Supply Chain ManagementMS in Information Systems and Technology with Business Intelligence and Analytics ConcentrationMSc Corporate FinanceMSc Data Analytics for BusinessMaster of Business AdministrationMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSMaster of Business Administration 60 ECTSMaster of Business Administration 90 ECTSBachelors in International Management
For College Students

Introduction to Divide and Conquer Algorithm

$$/$$

You may recall that in the Computational Thinking module, we discussed decomposition. Not only does decomposition make the solution to a problem easier, but it also makes it more efficient. Let’s see how.

$$/$$

As discussed by Ankit, if the problem is divided into subproblems, the number of steps required to solve it reduces significantly. In the phonebook example that we discussed, you started at the middle, thus dividing the search space into two halves. The phonebook coincidently had names starting with L in the middle. If you were looking for a name that starts with T, you would have discarded everything to the left of L and moved to the right of L. This would have saved the number of steps required to search in the left half, which is insignificant to you. So in each step, you reduce the search space by half. Therefore, if the search space initially had 128 elements, you reduced the number to 64 in the first pass, 32 in the next, 16 in the next, 8 in the next, 4 after that, 2 after that, and finally, the last element. The following table puts this in a more concise form.

Initial Size128
After Step 164
After Step 232
After Step 316
After Step 48
After Step 54
After Step 62
After Step 71

So, you reached this last element in seven steps for an initial list with 128 elements. This, if you look carefully, is log 2128. So, let’s see if it lends you another search algorithm.

 

Video Transcript
 

The name explains itself, doesn't it? Essentially, we are not going to talk about anything new. If you can recall the computational thinking module we discussed decomposition there. There we talked about breaking down a problem into smaller subproblems and solving those smaller ones makes the task easier. Let's understand it better with an example. Let's imagine you have a phone book and you are looking for a name. Chang let's say you open the phone book in the middle and you see what names is in that middle page. If the middle page has names that start in L, then to look up the names that start with C, you would look at the pages to the left of L. Now you may think, why should I start in the middle? What if the phone book has 90% of the names starting with A and 10% of the names starting with any other letter apart from A? In such a case, starting at the middle doesn't make much sense. But in reality, we don't know how many names start with A or for that matter, any other letter. So it's 

 

always a good practice to start in the middle of the phone book, since in this case, the middle page has names that start with L and we are looking for a name that starts with C. So we will discard everything that's to the right of L and we will move to the left of L and we will repeat the same process for the left side. This kind of an approach where you are dividing a problem into halves or smaller subproblems certainly looks like a more programmatic way to attack a problem. This is what divide and conquer is. You divide a problem into smaller problems. You conquer by solving those smaller subproblems. Then you construct the solution to the original problem from the solutions to the smaller sub problems. 

 

Video Recap

 

  • Divide and conquer algorithm involve breaking down a problem into smaller subproblems and solving them.

  • This approach is more programmatic and efficient.

  • The concept is explained using the example of finding a name in a phone book.

  • Starting in the middle of the phone book is a good practice, as it can help in quickly finding the required name.

  • This approach involves dividing the problem into halves or smaller subproblems.

  • The solutions to the smaller subproblems are used to construct the solution to the original problem.

 

Looking for an efficient way to solve complex problems? Learn about the divide and conquer algorithm and its benefits in our video. We explain this concept with the example of finding a name in a phone book, and provide insights on how to start in the middle to quickly locate the required name. With this approach, you can divide a problem into smaller subproblems and solve them efficiently to construct the solution to the original problem. Watch now to learn more.