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.
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.
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 PDFThere 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 log_{3}N = the number of weighings.
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 log_{2}(100 -1 +1)= log_{2}(100) = 7. Hence the worst case running time is log_{2}(Max - Min + 1).
log_{2}(N) → O(log N)
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!
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
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 n^{2} sorts) | Θ(n^{2}) |
T(n) = 2 T(n/2) + Θ(n) | Mergesort (average case Quicksort) | Θ(n log n) |