Answers.Body: <p>MergeSort is fairly easy to implement in Python and it's a straightforward divide-and-conquer algorithm.  You keep splitting the collection in half until it is in trivial-to-sort pieces.  This splitting reduces sorting from O(n^2) to O(nlog(n)).</p>
  
  <p>Second example:  computing integer powers.  if the power is even, square base and integer divide exponent by 2.  If it's odd, do the same and multiply by a factor of the base.  This algorithm is O(log(n)) instead of O(n), which would come from computing an integer power with a simple loop.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-10T17:17:15.220Z
Answers.Text: Would you mind providing a bit more explanation for why you think merge sort is a good example to use for teaching divide and conquer? Not every divide and conquer algorithm will be useful for teaching the concept of divide and conquer, so why do you think merge sort is?
Answers.UserDisplayName: thesecretmaster
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-09T23:59:54.230Z
Answers.LastActivityDate: 2019-09-12T23:46:40.277Z
Answers.LastEditDate: 2019-09-12T23:46:40.277Z
Answers.UserDisplayName: ncmathsadist
Answers.Body: <p>The typical examples for introducing divide and conquer are binary search and merge sort because they are relatively simple examples of how divide and conquer is superior (in terms of runtime complexity) to naive iterative implementations. FFT can also be used in that respect.</p>
  <p>Among these, merge sort is the best example. Binary search is a degenerate case for explaining divide and conquer because you divide the problem into two subproblems, but you discard one of them almost trivially, so you are not actually combining the solution of several subproblems but just solving one of them.</p>
  <p>But on my experience (I have lectured that several years), merge sort makes it also very hard for many novice students to grasp the idea of divide and conquer because it combines too many different conceptual problems at the same time. In order to implement merge sort efficiently, they will need to understand the technique of divide and conquer, the execution tree that occurs under the hood, the implementation of the division phase (thus working with indices if you want efficiency) and the implementation of the conquer phase (linearly).</p>
  <p>You can start with an easier example such as computing the average of an array:</p>
  <pre class="lang-py prettyprint-override"><code>def average(arr):
      assert arr, 'Expected non-empty array'
      if len(arr)==1:
          avg = arr[0]
          n = 1
      else:
          mid = len(arr)//2 # or any value with 0 &lt; mid &lt; len(arr)
          avgL, nL = average(arr[:mid])
          avgR, nR = average(arr[mid:])
          n = nL + nR
          avg = (avgL*nL + avgR*nR) / n
      return (avg, n)
  </code></pre>
  <p>This example introduces the idea (instead of the advantages) of divide and conquer in a way that all students can intuitively understand. The key point is to highlight that the recursive calls solve exactly the same problem but for small instances, and that you can use those solutions of smaller instances to solve the problem for the large instance.</p>
  <p>The example may appear trivial for many professors, but it is already shocking for many students and it will let them focus on understanding the technique itself and its execution, rather than details and optimizations. The example can also serve as guinea pig for analyzing the complexity of several different scenarios, such as when the array is copied on each call instead of being passed as a slice reference, or when mid is chosen as one third or as a constant.</p>
  <p>Moreover, this example will naturally raise questions among students about its complexity and the possibility of parallelizing the computation, which may make some of them enthusiastic and creative.</p>
  <p>Afterwards you must of course explain and analyze merge sort and binary search, emphasizing on how important they are because they beat naive iterative implementations.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-17T20:09:07.490Z
Answers.Text: This is the first time I've ever encountered multiple multiple assignments in a single statement like that.  Weird!
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T17:57:32.380Z
Answers.Text: That's rather typical in python. It's called iterator unpacking.
Answers.UserDisplayName: Carlos Pinzón
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-17T14:11:01.677Z
Answers.LastActivityDate: 2020-12-17T14:11:01.677Z
Answers.UserDisplayName: Carlos Pinzón
Answers.Body: <p>Back around 1985, Susan Merritt created an <a href="https://dl.acm.org/citation.cfm?id=214925" rel="noreferrer">Inverted Taxonomy of Sorting Algorithms</a>. The idea is that to sort an array you have two phases, the split phase and the join phase. She divided the various algorithms into two types <em>easy split/hard join</em> and <em>hard split/easy join</em> varieties. Merge sort is of the former type. Quick sort is the latter. </p>
  
  <p>But all sorts, envisioned in this way are divide and conquer. Her original paper (part of her doctoral work) is a wonder and worth exploring by any CS teacher. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-21T14:34:54.397Z
Answers.LastActivityDate: 2019-07-21T14:34:54.397Z
Answers.UserDisplayName: Buffy
Answers.Body: <p>The simplest example that still bears enough complexity to show what's going on is probably merge sort. It's no coincidence that this algorithm is the classical example to begin explaining the divide and conquer technique.</p>
  
  <p>I am not sure at what level you teach, but your students should be comfortable with both recursion and inductive proofs before venturing far into this territory.</p>
  
  <p>Coincidentally, there is a list of divide and conquer algorithms found <a href="https://www.geeksforgeeks.org/divide-and-conquer/" rel="noreferrer">here</a>.  It's a pretty long list, and might have cast too wide a net.  I'm not convinced that I agree that all of the algorithms are genuinely divide and conquer.  However, it could be that upon closer inspection, they are. </p>
  
  <p>In any case, it's a great starting point to find algorithms to present to your students. Just be sure that you can clearly explain the central divide/conquer/combine throughline for any algorithms you choose to bring to your students.  This area of algorithms is full of traps for unwary beginners, so your students will benefit greatly from thought and care put into your presentation.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-21T10:36:49.543Z
Answers.LastActivityDate: 2019-07-21T10:36:49.543Z
Answers.UserDisplayName: Ben I.
Answers.Body: <p>These sorts of patterns are a bit tricky in real life.  In nice easy computer-science land, every step is the same, just smaller.  Merge sort is clearly the ultimate easy example of this.</p>
  
  <p>In real life, we tend to break things up along useful lines.  If we're sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together.  When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that.  In war, we divide an opponent into pieces which cannot work as a cohesive unit, then crush them.</p>
  
  <p>We see this in real life more often than blind divisions because we, as humans, know we can divide along <em>useful</em> lines.  The closest I know of that is quicksort's attempt to find a middle index to partition with.</p>
  
  <p>One thing I find tricky about these divide and conquer algorithms is that they <em>look</em> like an infinite regression.  You keep proving you can sort lists as long as you can sort smaller lists.... which you know you can do because you can sort smaller lists... so on and so forth.  Infinite regression is a serious faux pas in modern logic, so I think people may get confused by that.  Showing that "if I can sort a list of length n, I can sort a list of length 2n" would be the more traditional mathematical induction approach.</p>
  
  <p>Then again, all may be for naught, for it is quite clear the best use for divide an conquer in real life is to put together <a href="https://www.youtube.com/watch?v=ywWBy6J5gz8" rel="nofollow noreferrer">a thrilling Hungarian dance</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T12:41:10.880Z
Answers.Text: +1 for the Hungarian dance example :)
Answers.UserDisplayName: DavidPostill
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-22T02:48:04.310Z
Answers.LastActivityDate: 2019-07-22T02:48:04.310Z
Answers.UserDisplayName: Cort Ammon
Answers.Body: <p>If you want to divide a long loaf of bread in 8 or 16 equal pieces, generally people cut it into two equal halves first and then cut each half into two equal halves again, repeating the process until you get as many pieces as you want - 8, 16, 32, or whatever. Almost nobody tries to divide the loaf into 8 pieces all at once - people can guess halves much better than eighths.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T18:14:18.613Z
Answers.Text: Hello, and welcome to Computer Science Educators SE! While your example is good, you may want to add some explanation of why your example appropriately addresses the question. Thanks!
Answers.UserDisplayName: auden
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-23T09:20:00.357Z
Answers.LastActivityDate: 2019-07-31T18:13:21.220Z
Answers.LastEditDate: 2019-07-31T18:13:21.220Z
Answers.UserDisplayName: sparsh sharma
Body: <p>Can someone give a real world example for the divide and conquer method? For example, I've heard the boomerang used to explain the idea of a loop back address. What is a real world example we can use to teach students about the divide and conquer method before going to more complex algorithms?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-21T22:45:38.703Z
Comments.Text: You will have to enlighten us on “boomerang”.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-21T23:23:42.750Z
Comments.Text: Divide and Conquer was originally a military term. You can look for example at the British conquest of India.
Comments.UserDisplayName: njzk2
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-22T01:01:01.870Z
Comments.Text: Related: https://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently
Comments.UserDisplayName: David says Reinstate Monica
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-22T12:40:47.037Z
Comments.Text: My teacher used the way we look for a word in a dictionary.
Comments.UserDisplayName: Jimbot
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-22T13:43:41.710Z
Comments.Text: My mother taught me binary search for finding words in a dictionary in the 1950's.
Comments.UserDisplayName: Patricia Shanahan
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-31T18:17:25.947Z
Comments.Text: @ctrl-alt-delor if I had to guess, OP is referring to the 'throw and it returns to you' boomerang, since OP is talking about a *loop back* address.
Comments.UserDisplayName: auden
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-31T23:25:05.537Z
Comments.Text: @heather. I don't see how that relates to divided and conquer. And it seems like a very bad analogy to loopback. With network loopback the packet does not leave (so has no need to come back). A better analogy to a loopback address is “home”.
Comments.UserDisplayName: ctrl-alt-delor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-08-01T01:33:45.357Z
Comments.Text: @ctrl-alt-delor it doesn't relate to divide and conquer, I don't think - seems like OP is saying 'just like we use this real world example for this thing, what real world example can we use for divide and conquer?' I also can't really comment on the quality of the boomerang analogy; I was just trying to guess as to what the OP meant =)
Comments.UserDisplayName: auden
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-08-28T19:40:49.820Z
Comments.Text: @PatriciaShanahan and Jimbot: You should expand your comment into an answer. To me, this seems to be the most obvious application of divide and conquer in real life, and everybody immediately understands the process. Another one might be guessing a number where you're just told whether your guess is too high or too low.
Comments.UserDisplayName: Pascal
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-19T03:09:41.163Z
Comments.Text: A boomerang would be a good analogy for a ping, not for loopback!
Comments.UserDisplayName: csabinho
Tags: <teaching-analogy><algorithms>
Title: A real world example for the divide and conquer method
ThreadText: # A real world example for the divide and conquer method
  
  (Asked by: username_0 on 2019-07-21)
  
  Can someone give a real world example for the divide and conquer method? For example, I've heard the boomerang used to explain the idea of a loop back address. What is a real world example we can use to teach students about the divide and conquer method before going to more complex algorithms?
  
  **Tags:** teaching-analogy, algorithms
  
  > **Comments:**
  > **username_1**: You will have to enlighten us on “boomerang”.  
  > **username_2**: Divide and Conquer was originally a military term. You can look for example at the British conquest of India.  
  > **username_3**: Related: https://stackoverflow.com/questions/14415881/how-to-pair-socks-from-a-pile-efficiently  
  > **username_4**: My teacher used the way we look for a word in a dictionary.  
  > **username_5**: My mother taught me binary search for finding words in a dictionary in the 1950's.  
  > **username_6**: @username_1 if I had to guess, OP is referring to the 'throw and it returns to you' boomerang, since OP is talking about a *loop back* address.  
  > **username_1**: @heather. I don't see how that relates to divided and conquer. And it seems like a very bad analogy to loopback. With network loopback the packet does not leave (so has no need to come back). A better analogy to a loopback address is “home”.  
  > **username_6**: @username_1 it doesn't relate to divide and conquer, I don't think - seems like OP is saying 'just like we use this real world example for this thing, what real world example can we use for divide and conquer?' I also can't really comment on the quality of the boomerang analogy; I was just trying to guess as to what the OP meant =)  
  > **username_7**: @username_5 and username_4: You should expand your comment into an answer. To me, this seems to be the most obvious application of divide and conquer in real life, and everybody immediately understands the process. Another one might be guessing a number where you're just told whether your guess is too high or too low.  
  > **username_8**: A boomerang would be a good analogy for a ping, not for loopback!  
  
  ---
  
  ## 6 answers
  
  ### Answer by username_13 on 2019-07-21. Score: 13
  
  Back around 1985, Susan Merritt created an [Inverted Taxonomy of Sorting Algorithms](https://dl.acm.org/citation.cfm?id=214925). The idea is that to sort an array you have two phases, the split phase and the join phase. She divided the various algorithms into two types *easy split/hard join* and *hard split/easy join* varieties. Merge sort is of the former type. Quick sort is the latter.
  
  But all sorts, envisioned in this way are divide and conquer. Her original paper (part of her doctoral work) is a wonder and worth exploring by any CS teacher.
  
  
  ---
  
  ### Answer by username_12 on 2019-07-21. Score: 7
  
  The simplest example that still bears enough complexity to show what's going on is probably merge sort. It's no coincidence that this algorithm is the classical example to begin explaining the divide and conquer technique.
  
  I am not sure at what level you teach, but your students should be comfortable with both recursion and inductive proofs before venturing far into this territory.
  
  Coincidentally, there is a list of divide and conquer algorithms found [here](https://www.geeksforgeeks.org/divide-and-conquer/). It's a pretty long list, and might have cast too wide a net. I'm not convinced that I agree that all of the algorithms are genuinely divide and conquer. However, it could be that upon closer inspection, they are.
  
  In any case, it's a great starting point to find algorithms to present to your students. Just be sure that you can clearly explain the central divide/conquer/combine throughline for any algorithms you choose to bring to your students. This area of algorithms is full of traps for unwary beginners, so your students will benefit greatly from thought and care put into your presentation.
  
  
  ---
  
  ### Answer by username_14 on 2019-07-22. Score: 4
  
  These sorts of patterns are a bit tricky in real life. In nice easy computer-science land, every step is the same, just smaller. Merge sort is clearly the ultimate easy example of this.
  
  In real life, we tend to break things up along useful lines. If we're sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together. When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that. In war, we divide an opponent into pieces which cannot work as a cohesive unit, then crush them.
  
  We see this in real life more often than blind divisions because we, as humans, know we can divide along *useful* lines. The closest I know of that is quicksort's attempt to find a middle index to partition with.
  
  One thing I find tricky about these divide and conquer algorithms is that they *look* like an infinite regression. You keep proving you can sort lists as long as you can sort smaller lists.... which you know you can do because you can sort smaller lists... so on and so forth. Infinite regression is a serious faux pas in modern logic, so I think people may get confused by that. Showing that "if I can sort a list of length n, I can sort a list of length 2n" would be the more traditional mathematical induction approach.
  
  Then again, all may be for naught, for it is quite clear the best use for divide an conquer in real life is to put together [a thrilling Hungarian dance](https://www.youtube.com/watch?v=ywWBy6J5gz8).
  
  > **Comments:**
  > **username_15**: +1 for the Hungarian dance example :)  
  
  ---
  
  ### Answer by username_16 on 2019-07-23. Score: 2
  
  If you want to divide a long loaf of bread in 8 or 16 equal pieces, generally people cut it into two equal halves first and then cut each half into two equal halves again, repeating the process until you get as many pieces as you want - 8, 16, 32, or whatever. Almost nobody tries to divide the loaf into 8 pieces all at once - people can guess halves much better than eighths.
  
  > **Comments:**
  > **username_6**: Hello, and welcome to Computer Science Educators SE! While your example is good, you may want to add some explanation of why your example appropriately addresses the question. Thanks!  
  
  ---
  
  ### Answer by username_9 on 2019-09-09. Score: 1
  
  MergeSort is fairly easy to implement in Python and it's a straightforward divide-and-conquer algorithm. You keep splitting the collection in half until it is in trivial-to-sort pieces. This splitting reduces sorting from O(n^2) to O(nlog(n)).
  
  Second example: computing integer powers. if the power is even, square base and integer divide exponent by 2. If it's odd, do the same and multiply by a factor of the base. This algorithm is O(log(n)) instead of O(n), which would come from computing an integer power with a simple loop.
  
  > **Comments:**
  > **username_10**: Would you mind providing a bit more explanation for why you think merge sort is a good example to use for teaching divide and conquer? Not every divide and conquer algorithm will be useful for teaching the concept of divide and conquer, so why do you think merge sort is?  
  
  ---
  
  ### Answer by username_11 on 2020-12-17. Score: 1
  
  The typical examples for introducing divide and conquer are binary search and merge sort because they are relatively simple examples of how divide and conquer is superior (in terms of runtime complexity) to naive iterative implementations. FFT can also be used in that respect.
  
  Among these, merge sort is the best example. Binary search is a degenerate case for explaining divide and conquer because you divide the problem into two subproblems, but you discard one of them almost trivially, so you are not actually combining the solution of several subproblems but just solving one of them.
  
  But on my experience (I have lectured that several years), merge sort makes it also very hard for many novice students to grasp the idea of divide and conquer because it combines too many different conceptual problems at the same time. In order to implement merge sort efficiently, they will need to understand the technique of divide and conquer, the execution tree that occurs under the hood, the implementation of the division phase (thus working with indices if you want efficiency) and the implementation of the conquer phase (linearly).
  
  You can start with an easier example such as computing the average of an array:
  
  ```py
  def average(arr):
      assert arr, 'Expected non-empty array'
      if len(arr)==1:
          avg = arr[0]
          n = 1
      else:
          mid = len(arr)//2 # or any value with 0 < mid < len(arr)
          avgL, nL = average(arr[:mid])
          avgR, nR = average(arr[mid:])
          n = nL + nR
          avg = (avgL*nL + avgR*nR) / n
      return (avg, n)
  
  ```
  
  This example introduces the idea (instead of the advantages) of divide and conquer in a way that all students can intuitively understand. The key point is to highlight that the recursive calls solve exactly the same problem but for small instances, and that you can use those solutions of smaller instances to solve the problem for the large instance.
  
  The example may appear trivial for many professors, but it is already shocking for many students and it will let them focus on understanding the technique itself and its execution, rather than details and optimizations. The example can also serve as guinea pig for analyzing the complexity of several different scenarios, such as when the array is copied on each call instead of being passed as a slice reference, or when mid is chosen as one third or as a constant.
  
  Moreover, this example will naturally raise questions among students about its complexity and the possibility of parallelizing the computation, which may make some of them enthusiastic and creative.
  
  Afterwards you must of course explain and analyze merge sort and binary search, emphasizing on how important they are because they beat naive iterative implementations.
  
  > **Comments:**
  > **username_12**: This is the first time I've ever encountered multiple multiple assignments in a single statement like that.  Weird!  
  > **username_11**: That's rather typical in python. It's called iterator unpacking.  
  
  ---
  
  