.
 Vyom World.com  . Let's Touch the Sky Together!  
.
. . . . . . .
 Home
VyomWorld.com Home
Free Magazines!
VyomLinks.com Home
JobsAssist.com Home
Vyom Network
Contact Us
 Jobs & Careers
Resume Submitter
Placement Papers
IT Companies Directory
Computer Jobs
Interview Questions
Online Exams
Vyom Career eMag.
 Fun
Screensavers New!
Send FREE SMS!
SMS Jokes
 Source Codes Library
Source Codes Home
ASP Source Codes
C Source Codes
C++ Source Codes
COBOL Source Codes
Java Source Codes
Pascal Source Codes
Submit Source Codes
 GATE
GATE an Overview
GATE Preparation
Study Materal
 GRE
GRE an Overview
GRE Questions
GRE Preparation
GRE Universities
 TOEFL Preparation
TOEFL Resources
 GMAT Preparation
GMAT Resources
 MBA Preparation
MBA Resources
 Networking Concepts
Networking Concepts
 Testing Preparation
Testing Resources
 Webmasters
Free Traffic Builder
Webmaster Articles
Web Hosting
 Tutorials
Hardware Tutorial
1500 Free eBooks New!
 FREE Publications
Vyom Career eMag.
 
.
Get 9,000+ Interview Questions & Answers in an eBook.


  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades

    Get it now!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    4.1 Divide and Conquer

    There are a number of general and powerful computational strategies that are repeatedly used in computer science. It is often possible to phrase any problem in terms of these general strategies. These general strategies are Divide and Conquer, Dynamic Programming. The techniques of Greedy Search, Backtracking and Branch and Bound evaluation are variations of dynamic programming idea. All these strategies and techniques are discussed in the subsequent chapters.





    The most widely known and often used of these is the divide and conquer strategy.

    The basic idea of divide and conquer is to divide the original problem into two or more sub-problems which can be solved by the same technique. If it is possible to split the problem further into smaller and smaller sub-problems, a stage is reached where the sub-problems are small enough to be solved without further splitting. Combining the solutions of the individuals we get the final conquering. Combining need not mean, simply the union of individual solutions.

    Divide and Conquer involves four steps

      1. Divide
      2. Conquer [Initial Conquer occurred due to solving]
      3. Combine
      4. Conquer [Final Conquer].

    In precise, forward journey is divide and backward journey is Conquer. A general binary divide and conquer algorithm is :

    Procedure D&C (P,Q) //the data size is from p to q

    {

    If size(P,Q) is small Then

    Solve(P,Q)

    Else

    M ¬ divide(P,Q)

    Combine (D&C(P,M), D&C(M+1,Q))

    }

    Sometimes, this type of algorithm is known as control abstract algorithms as they give an abstract flow. This way of breaking down the problem has found wide application in sorting, selection and searching algorithm.

    4.1 Binary Search:

    Algorithm:

    m¬ (p+q)/2

    If (p £ m £ q) Then do the following Else Stop

    If (A(m) = Key Then ‘successful’ stop

    Else

    If (A(m) < key Then

    q=m-1;

    Else

    p¬ m+1

    End Algorithm.

    Illustration :

    Consider the data set with elements {12,18,22,32,46,52,59,62,68}. First let us consider the simulation for successful cases.

    Successful cases:

    Key=12 P Q m Search

    1 9 5 x

    1 4 2 x

    1 1 1 successful

    To search 12, 3 units of time is required

     

    Key=18 P Q m Search

    1 9 5 x

    1 4 2 successful

    To search 18, 2 units of time is required

    Key=22 P Q m Search

    1 9 5 x

    1 4 2 x

    3 4 3 successful

    To search 22, 3 units of time is required

    Key=32 P Q m Search

    1 9 5 x

    1 4 2 x

    3 4 3 x

    4 4 4 successful

    To search 32, 4 units of time is required

    Key=46 P Q m Search

    1 9 5 successful

    To search 46, 1 unit of time is required

    Key=52 P Q m Search

    1 9 5 x

    6 9 7 x

    6 6 6 successful

    To search 52, 3 units of time is required

    Key=59 P Q m Search

    1 9 5 x

    6 9 7 successful

    To search 59, 2 units of time is required

    Key=62 P Q m Search

    1 9 5 x

    6 9 7 x

    8 9 8 successful

    To search 62, 3 units of time is required

    Key=68 P Q m Search

    1 9 5 x

    6 9 7 x

    8 9 8 x

    9 9 9 successful

    To search 68, 4 units of time is required

     

    3+2+3+4+1+3+2+4

    Successful average search time= -------------------------

    9

    unsuccessful cases

    Key=25 P Q m Search

    1 9 5 x

    1 4 2 x

    3 4 3 x

    4 4 4 x

    To search 25, 4 units of time is required

     

     

     

    Key=65 P Q m Search

    1 9 5 x

    6 9 7 x

    8 9 8 x

    9 9 9 x

    To search 65, 4 units of time is required

    4+4

    Unsuccessful search time =--------------------

    2

    average (sum of unsuccessful search time

    search = + sum of Successful search time)/(n+(n+1))

    time

     

     

     

    Study Notes Home | Next Section>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    Recently Updated: New Placement Papers added.
    Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory

    Copyright ©2003-2017 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy