Dynamic Programming: Top-Down Programming

    Dynamic Programming: Top-Down Programming

      It's always nice to bake a birthday cake—especially if it's someone's birthday. Just be sure to pay attention to the expiration dates on ingredients and don't use eggs that smell like something rotting. They're not supposed to smell like that.

      Pro Tip: Anything that smells like it's rotting is better left in the garbage than in your cake.

      Baking is a step-by-step process, just like top-down programming. You know what the final product will probably be (or at least what it's supposed to be) and you have some idea of how to get it done. You'll probably follow steps like:

      • Make sure you have ingredients and supplies (and none of them expired or even questionable)
      • Make the cake
      • Lick the leftover frosting from the bowl
      • Clean up the kitchen
      • Serve the cake

      Those big steps are the broad strokes, though. You can't just follow those directions without breaking them down into a little more detail:

      Check Supplies

      • Scour Pinterest for the perfect cake recipe (we'd recommend a churro cake because who wouldn't love it?) 
      • Head to the store to get your ingredients
      • Measure out the ingredients to make sure you have enough of everything
      • Run to the store because you forgot the butter, sugar, and flour
      • Find the right sized pan, beaters, and spatula

      Make the Cake

      • Beat butter and sugar, then add eggs and any other wet ingredients
      • Add dry ingredients
      • Spread batter in pan
      • Bake the cake
      • Make the frosting as it's baking
      • Clean up the kitchen
      • Wash dishes 
      • Clean counters
      • Remove cooled cake from the pan
      • Frost the cake

      Lick the Leftover Frosting from the Bowl

      • Lick the frosting

      (As usual, the most important step is also the simplest.)

      Serve the Cake

      • Gather dessert plates and forks
      • Find, add, and light the candles 
      • Sing, "Happy Birthday," and serve the cake
      • Make same tired jokes about how old the birthday person's getting

      Maybe some steps need even more details than that. For example, before spreading the batter in the pan, you need to grease and flour the pan. Or if you decide that step's for timid cake bakers, you'll need to add way more detail to your cleanup step than you'd first thought.

      Where were we?

      Right. Top-down programming starts with a high-level requirement like needing a cake. That's the big picture view. Usually a main procedure (the first place the computer goes to when it reads your code) acts as the outline of the program. From that main starting point, the code will call in more detailed program modules, functions, or procedures to handle the details.

      These modules/functions/whatever you want to call them are created after the original outline's been figured out. They drill down on one particular step to make sure all its details are taken care of.

      Because they're so focused on that one result, these functions usually end up so specific to that one problem that you can't re-use them in other applications. If you're still on the baking metaphor, there's no good way to repurpose your churro cake batter for apple pie crust. Limited reusability is a big drawback of top-down programming.

      Top-down programming is called "top-down" because…you're working from the top—the main problem—down to the individual details. Not the most creative name, but it gets the job done.

      It also relies on your knowing just about every detail about how the program should be made. That being said, dynamic programming doesn't use a top-down approach because dynamic problems don't know that many details up front. Bummer.

      At least you've got cake?