Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks

Apologies for the OT post, but I'm really stuck here. I have and algorithms assignement that I would like to do in perl (so this is a bit related.)

The requirement: find a real life problem, model it in divide-and-conquer, decrease-and-conquer, and transform-and-conquer algorithms, then implement the three solutions in the language of your choice and benchmark your results.

I can't for the life of me figure out any problem that fits these three types of algorithms besides "sorting" lists.

Can you please give me ideas on problems that can be solved using these three techniques? I don't need the algorithms themselves or the code, I just need to be pointed in the right direction.

thank you for your time, and sorry again for this post.

Replies are listed 'Best First'.
Re: [OT][HOMEWORK] Algorithms Help
by Abigail-II (Bishop) on May 28, 2004 at 11:12 UTC
    Yeah, this can be fun! Consider for instance the problem of finding the convex hull of a set of points. Divide and conquer would mean an algorithm where you take the set of points, if the set contains three points or less, the convex hull is determined trivially. Otherwise, you divide the set into two, find the convex hull for both smaller sets, then combine both convex hulls. A decrease and conquer technique starts with three (or two, or just one) of the points, finds the convex hull of that set, and than adds one point at the time, adding to the convex hull if necessary. With transform and conquer you actually solve a different problem. For instance, you determine the first order Voronoi diagram of the set of points, and determine the convex hull from that.

    Oh, wait, you said real life problem. Take for instance US foreign politics. To make sure the US gets a steady supply of oil, you divide the rest of the world: those who are with us (Tony Blair) and those who are against (the rest of the world). Then you attack countries one-by-one, decreasing the number to conquer: first Afghanistan, then Iraq, with Iran, Syria and North Korea getting low pay out by the bookies for who's next. Finally, if everyone but Bush and Blair are convinced that Iraq never had weapons of mass destruction, you just transform your reason to conquer to something like "Saddam had bad breath".

    Abigail

[reply]

      Ah, this brings up a memory. I had written the decrease and conquer algorithm once for the convex hull problem in C. It's not quite efficent, the whole thing is 240 lines. It was "homework" too: http://www.komal.hu/verseny/2001-12/I.h.shtml.

      But the other algorithms for finding the convex hull might be more difficult to write.

[reply]
Re: [OT][HOMEWORK] Algorithms Help
by BrowserUk (Patriarch) on May 28, 2004 at 11:06 UTC

    Given the hieght, width and length of a room, and the length & width of a roll, determine how many rolls of wallpaper are required to paper the room.

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
[reply]
      That's easy. You always need one more roll than you bought. And you only find out after the shop closes. And if you do find it out before the shop closes, they are out of the pattern you picked.

      Abigail

[reply]

        Hey! That's brilliant. So, regardless of the size of the room, all I have to do is buy two rolls in the knowledge that if I had bought one, I would have needed one more but it wouldn't have been available to me!

        Saves time and expense:)

        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
[reply]
Re: [OT][HOMEWORK] Algorithms Help
by tbone1 (Monsignor) on May 28, 2004 at 12:39 UTC
    Divide-and-conquer? How about a group of female coworkers trying to trick a monied bachelor into marrying a single mom? I mean, if you need a real life situation ...

    Then again, I don't think a group of conspiring female coworkers could be mapped to an algorithm. Not a legal one, anyway.

    --
    tbone1, YAPS (Yet Another Perl Schlub)
    And remember, if he succeeds, so what.
    - Chick McGee

[reply]

Back to Seekers of Perl Wisdom