Algorithms

Divide and Conquer Algorithm

The divide and conquor algorithm is a technique used to make a complicated problem easier to solve by splitting (or dividing) it into smaller more managable steps.


Santa's Dirty Socks

This activity introduces the idea of "divide and conquer" using a fictitious but serious problem - a pair of dirty socks have accidently been wrapped in one of the presents that Santa is about to deliver, and he needs to figure out which one to avoid a child getting a nasty surprise. You can either play the video (below), or download the PDF of the book (see the PDF files below) to read aloud or give to students. The solution in the story points out that when there are 1024 boxes to test, instead of having to open all of them until the socks are found, one half can be eliminated at a time, and repeatedly halving the problem very quickly narrows it down to one box (the size of the problem starts at 1024, then with one weighing there are 512 boxes, then 256, 128, 64, 32, 16, 8, 4, 2 and 1.) This idea comes up frequently in the design of fast computer algorithms.


Essence of Divide and Conquer

  1. Divide problem into several smaller subproblems
    • Normally, the subproblems are similar to the original

  2. Conquer the subproblems by solving them recursively
    • Base case: solve small enough problems by brute force

  3. Combine the solutions to get a solution to the subproblems
    • And finally a solution to the orginal problem

  4. Divide and Conquer algorithms are normally recursive

Because divide-and-conquer creates at least two subproblems, a divide-and-conquer algorithm makes multiple recursive calls



Computer Science Unplugged - Santas Dirty Socks

csunplugged.org

This original story introduces the idea of a divide-and-conquer algorithm using a narrated picture-book verse about the serious problem of finding a pair of dirty socks that have been accidentally wrapped with a child's present. The idea is that this can be played or read to students, and then can be used as the basis for a follow-up discussion. A set of discussion starter questions is available (http://csunplugged.org/divideAndConquer) to encourage students to engage in computational thinking and think about algorithm analysis in the story 1024 presents are searched in 10 steps, and students can be asked to extend this to other cases, and generally think about the implications of having an algorithm with logarithmic complexity.

Download PDF


Interview Puzzle: 8 balls and a weighing scale Divide and Conquer

randerson112358

There are 8 basketballs and 1 scale. 7 of them weigh the same. 1 of them has a different weight, (it's heavier or lighter). How do you find the odd ball with 2 weighs? Note: this is a log base 3 of size N problem, where N = the number of balls, and log3N = the number of weighings.



Number Guessing Game Binary Search

Let's look at the guessing game as another example of using a Divide and Conquer Algorithm by halfing our possible number of guesses. To play the guessing game, a person (player A) will choose a random numer from n to m, another person (player B) will have to guess player A's number in "x" turns. Player A will assist player B by telling player B if the number they guessed is higher than or lower than player A's randomly chosen number. The Algorithm will tell you if it is possible to guess player A's number in the given amount of turns x, and will tell the maximum amount of tries or guesses you will need in order to guess there number correctly. The Number Guessing Game uses binary search to quickly find a solution. A binary search is a dichotomic divide and conquer search algorithm. The maximum number of turns it takes to guess a number from 1 to 100 is log2(100 -1 +1)= log2(100) = 7. Hence the worst case running time is log2(Max - Min + 1).

An example of how the game works:
Player A: I am thinking of a number from 1 to 100, can you guess my number within 7 turns ?
Player B: Sure, is your number 89 ?
Player A: Nope guess a lower number.
Player B: Okay, is your number 75 ?
Player A: Nope, guess a higher number.
Player B: Okay is your number 80 ?
Player A: Nope, guess a higher number.
Player B: Okay, is your number 88 ?
Player A: Yes, congratulations you guessed my number in 4 turns you win!


Guessing Game C Program

computer science (compsci112358)

Create the number guessing game using the C programming language and a divide and conquer algorithm !

►Support this channel for FREE by doing your Amazon shopping through this link (bookmark it!): https://www.amazon.com/?tag=everythingc06-20

Get the code here:
https://github.com/randerson112358/C-Programs/blob/master/guessingGame.c


/* This is the number guessing game program */
/* This program was written in the C programing language 
    By Rodney Anderson (randerson112358)
*/

# include <stdio.h>
# include <stdlib.h>
# include <math.h>   // Library used for math in this case log() and ciel()

int main(void)
{
	//Declaring Variables to be used
	int lowRange = 1;
	int highRange = 100;
	int possibleGuesses = highRange + lowRange - 1;
	int maxTurns = (int)(log(possibleGuesses)/log(2)) + 1; // = log base 2 of possible guesses by rules of logarithms
	int yourGuess;
	int playerAnswer;
	int countNumTurns = 1;

	printf("Choose a number from %d to %d.\n", lowRange, highRange);
	printf("I will guess your number in %d turns or less.\n\n", maxTurns );

			//This loops through the algorithm
			do{
				possibleGuesses = highRange + lowRange - 1;
				yourGuess = (int) ceil(possibleGuesses / 2.0);

				printf("Is your number %d ?\n",yourGuess );
				printf("Press (1) Yes (2) Guess a lower number (3) Guess a higher number\n");
                                scanf("%d", &playerAnswer);

				if(playerAnswer == 3)//Guess was to low
					lowRange = yourGuess + 1;
				if(playerAnswer == 2) // Guess was too high
					highRange = yourGuess - 1;
				if (playerAnswer == 1)
				    break;
                               
                                 countNumTurns++;
                                
			}while(playerAnswer != 1 && countNumTurns <=maxTurns);

	//Print the end results
        if(countNumTurns > maxTurns)
    	     printf("You made a mistake somewhere, you've exceeded the maximum turns. \n");
	else
	     printf("I guessed your number in %d turns !\n", countNumTurns );

	system("pause"); //This is only for windows operating system otherwise comment it out.
}



The algorithm used to make this game, uses a divide and conquer approach by halving the possible choices/guesses !

Instructions to play:

1) Think of a number in your head from 1 to 100

2) The program will start off by guessing if your number is 50

3) You must tell the program if it's guess was lower or higher than the number you thought of in your head in step 1, if it guessed it right click correct

4) If the computer didn't guess your number continue with steps 2 - 4, else go to step 5

5) The program should have guessed your number within 7 turns. Click Refresh to play again

Think of a number from 1 to 100

I will guess your number within 7 turns: Turn #1

50


Popular Divide and Conquer Algorithms

Recurrence Algorithm Big-Theta Solution
T(n) = T(n/2) + Θ(1) Binary Search Θ(log n)
T(n) = T(n-1) + Θ(1) Sequential Search Θ(n)
T(n) = 2 T(n/2) + Θ(1) Tree Traversal Θ(n)
T(n) = T(n-1) + Θ(n) Selection Sort (other n2 sorts) Θ(n2)
T(n) = 2 T(n/2) + Θ(n) Mergesort (average case Quicksort) Θ(n log n)


Copyright © 2013, Everything Computer Science.