top of page

/////////////////////////////////////////////////////////////////////////////////////////////////////////////

Divide and Conquer ?

The most well-known algorithm

Example 

{ 1 }

Sorting

Merge Sort

 

  1. Divide the unsorted list into n sublists until containing 1 element.

  2. Compare two elements and merge sorted array.

  3. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Binary Search

{ 2 }

Efficient for searching element at sorted array

 

  1. Mid-element is datum point

  2. Compare mid-element with key.

  3. Smller than key, search left
    Larger than key, search right.

  4. Repeat the process until finding key
     

{ 0 }

Other algorithms

  • Multiplication of large integers

  • Matrix multiplication : Strassen's algorithm

  • Closest-pair algorithms

  • Convex-hull algorithms

Convex-hull algorithm

GROUP PROJECT

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Find the fake Broom

  1. Divide brooms into 2 part.

  2. Choose the less-weighted part

  3. Divide again and choose less-weight

  4. Repeat until finding fake broom

  1.  Divide problem into a number of smaller units problem to make it easier to solve the problem.

  2. Solve the divided problem recursively

  3.  In order to get the original answer to the problem, combine the answer of the sub-problems.

Quick Sort

 

    1. Select the pivot

the fisrt or last element that is choosen by me

    2. Compare i  and j with pivot.

i has to be smaller than pivot,

j has to be larger that pivot.

     3. If either i or j does not satisfy the above,

         i and j move to the next location.

         If both does not satisfy, change i and j.

         If i and j meet, change number of this digits and the pivot.

      4.  Repeat again 

SOLUTION

bottom of page