Category Archives: Algorithmic Thinking

Algorithms and Functional Decomposition With Honey Boo Boo

 

In a previous post I presented algorithms and functional decomposition. Here, we explore how to write an algorithm and then create working Java code from that algorithm.  This post’s purpose is not to present a realistic computer program. Moreover, this post omits many fundamental programming topics. But these omissions are by design. Instead suspend disbelief and focus on the simple process of turning a task into a computer program’s skeletal structure. Here we are using functional decomposition to go from a general real world task to the beginnings of a computer program.*see below

Sketti – Redneck Bolgnese

A recipe I remember from my childhood, sketti, went viral when Mama June made sketti on the The Learning Channel’s show Here Comes Honey Boo Boo. The recipe is simple: spaghetti noodles, hamburger, ketchup, and butter. But let Mama June demonstrate.

Mama June makes sketti by frying hamburger, boiling spaghetti noodles, microwaving a mixture of ketchup and margarine in a bowl, and then combining the ingredients in the pot used to boil the noodles (after draining the water first).

Observation to Algorithm

When you have a process you wish turning into a computer program, do not begin by writing code. You should first formalize the tasks involved.  Start by writing the steps involved in making sketti. Focus on the broad steps, not the details.

  1. gather ingredients
  2. boil noodles
  3. fry hamburger
  4. mix ingredients
  5. microwave sauce mixture
  6. combine ingredients
  7. serve and enjoy

These are the seven steps I get from observing Mama June make sketti. But, these steps are much too broad. And so let’s decompose these steps into more detailed sub-steps. As I’m a redneck, I wanna keep it realistic – so lets get the dishes from a dish-drainer rack rather than the cupboard. Oh, it’s also a fridge not a refrigerator – details are important.

  1. gather ingredients
    1. get hamburger from fridge
    2. get noodles from cabinet
    3. get pot from rack
    4. get pan from rack
    5. get microwavable bowl from rack
    6. get ketchup from fridge
    7. get butter from fridge
  2. boil noodles
    1. put water in pot
    2. bring water to a boil
    3. add noodles
    4. cook noodles
    5. throw noodles, three, against cabinet
    6. drain noodles
  3. fry hamburger
    1. put meat in pan
    2. fry meat
    3. drain fat (optional)
  4. make sauce
    1. put margarine in bowl
    2. put ketchup in bowl
    3. mix
    4. microwave sauce
  5. combine ingredients
    1. add meat to noodles
    2. add sauce to noodles
    3. stir

And there you have a top-level outline detailing making sketti. We can now use this outline to create the beginnings of a working Java program.

Algorithm to Java Code

Now let’s use the outline above to write the skeleton of a simple Java program that uses simple methods that do not return values. Again, suspend disbelieve, the purpose here is to demonstrate translating an outline to a simple program.

First I create a simple class named Sketti with a main method.

public class Sketti {
	public static void main(String[] args) {
	}
}

I then create methods from the top level outline methods. Note I am adding no logic to perform these tasks.

public class Sketti {
	public static void main(String[] args) {
	}
	public static void gatherIngredients(){	
	}
	public static void boilNoodles(){
	}
	public static void fryHamburger(){
	}
	public static void makeSauce(){
	}
	public static void combineIngredients(){
	}
}

Now, one of my pet-peeves is placing any logic in the main method. The main method is the program’s entry point, it should not be used for any logic. Therefore, I add a top-level method named makeSketti. This method will orchestrate the sketti making tasks.

public class Sketti {
	public static void main(String[] args) {
	}
	public static void gatherIngredients(){	
	}
	public static void boilNoodles(){
	}
	public static void fryHamburger(){
	}
	public static void makeSauce(){
	}
	public static void combineIngredients(){
	}
	public static void makeSketti(){
	}
}

Now that I have the primary tasks, I can orchestrate these tasks into making sketti.

public class Sketti {
	public static void main(String[] args) {
		makeSketti();
	}
	public static void gatherIngredients(){
	}
	public static void boilNoodles(){
	}
	public static void fryHamburger(){
	}
	public static void makeSauce(){
	}
	public static void combineIngredients(){
	}
	public static void makeSketti(){
		gatherIngredients();
		boilNoodles();
		fryHamburger();
		makeSauce();
		combineIngredients();
	}
}

I like to start with a running program, no matter how simplistic, therefore let’s add println statements to each function.

public class Sketti {
	public static void main(String[] args) {
		makeSketti();
	}
	public static void gatherIngredients(){
		System.out.println("gatherIngredients");
	}
	public static void boilNoodles(){
		System.out.println("boilNoodles");
	}
	public static void fryHamburger(){
		System.out.println("fryHamburger");
	}
	public static void makeSauce(){
		System.out.println("makeSauce");
	}
	public static void combineIngredients(){
		System.out.println("combineIngredients");
	}
	public static void makeSketti(){
		System.out.println("making sketti");
		gatherIngredients();
		boilNoodles();
		fryHamburger();
		makeSauce();
		combineIngredients();
		System.out.println("done making sketti");
	}
}

When ran the program writes the following output.

making sketti
gatherIngredients
boilNoodles
fryHamburger
makeSauce
combineIngredients
done making sketti

Now create methods for each sub-step involved in gathering ingredients. Then have the gatheringIngredients method orchestrate its sub-steps. The following code illustrates.

	public static void gatherIngredients(){
		System.out.println("gatherIngredients");
		getBurger();
		getNoodles();
		getPot();
		getPan();
		getKetchup();
		getButter();
	}
	
	public static void getBurger(){
		System.out.println("\tgetBurger");
	}
	public static void getNoodles(){
		System.out.println("\tgetNoodles");
	}
	
	public static void getPot(){
		System.out.println("\tgetPot");
	}
	
	public static void getPan(){
		System.out.println("\tgetPan");
	}
	
	public static void getKetchup(){
		System.out.println("\tgetKetchup");
	}
	
	public static void getButter(){
		System.out.println("\tgetButter");
	}

Repeat creating sub-steps and orchestration for each major step.

public class Sketti {
	public static void main(String[] args) {
		makeSketti();
	}
	public static void gatherIngredients(){
		System.out.println("gatherIngredients");
		getBurger();
		getNoodles();
		getPot();
		getPan();
		getKetchup();
		getButter();
	}
	public static void getBurger(){
		System.out.println("\tgetBurger");
	}
	public static void getNoodles(){
		System.out.println("\tgetNoodles");
	}
	public static void getPot(){
		System.out.println("\tgetPot");
	}
	public static void getPan(){
		System.out.println("\tgetPan");
	}
	public static void getKetchup(){
		System.out.println("\tgetKetchup");
	}
	public static void getButter(){
		System.out.println("\tgetButter");
	}
	public static void boilNoodles(){
		System.out.println("boilNoodles");
		pourWater();
		boilWater();
		addNoodles();
		cookNoodles();
		throwNoodles();
		drainNoodles();
	}
	public static void pourWater(){
		System.out.println("\tpourWater");
	}
	public static void boilWater(){
		System.out.println("\tgetButter");
	}
	public static void addNoodles(){
		System.out.println("\taddNoodles");
	}
	public static void cookNoodles(){
		System.out.println("\tcookNoodles");
	}
	public static void throwNoodles(){
		System.out.println("\tthrowNoodles");
	}
	public static void drainNoodles(){
		System.out.println("\tdrainNoodles");
	}
	public static void fryHamburger(){
		System.out.println("fryHamburger");
		placeMeat();
		fryMeat();
		drainFat();
	}
	public static void placeMeat(){
		System.out.println("\tplaceMeats");
	}
	public static void fryMeat(){
		System.out.println("\tfryMeat");
	}
	public static void drainFat(){
		System.out.println("\tdrainFat");
	}
	public static void makeSauce(){
		System.out.println("makeSauce");
		addMargarine();
		addKetchup();
		mix();
		microwaveSauce();
	}
	public static void addMargarine(){
		System.out.println("\taddMargarine");
	}
	public static void addKetchup(){
		System.out.println("\taddKetchup");
	}
	public static void mix(){
		System.out.println("\tmix");
	}
	public static void microwaveSauce(){
		System.out.println("\tmicrowave");
	}
	
	public static void combineIngredients(){
		System.out.println("combineIngredients");
		addMeat();
		addSauce();
		stir();
	}
	
	public static void addMeat(){
		System.out.println("\taddMeat");
	}
	public static void addSauce(){
		System.out.println("\taddSauce");
	}
	
	public static void stir(){
		System.out.println("\tstir");
	}
	
	public static void makeSketti(){
		System.out.println("Mama June's making sketti");
		System.out.println("=========================");
		gatherIngredients();
		boilNoodles();
		fryHamburger();
		makeSauce();
		combineIngredients();
		System.out.println("done making sketti");
	}
}

When you run the program, you obtain the following output.

Mama June's making sketti
=========================
gatherIngredients
	getBurger
	getNoodles
	getPot
	getPan
	getKetchup
	getButter
boilNoodles
	pourWater
	getButter
	addNoodles
	cookNoodles
	throwNoodles
	drainNoodles
fryHamburger
	placeMeats
	fryMeat
	drainFat
makeSauce
	addMargarine
	addKetchup
	mix
	microwave
combineIngredients
	addMeat
	addSauce
	stir
done making sketti

And there you have it, you have used functional decomposition to write a simple program that makes sketti. Admittedly, this is not a realistic program. But it illustrates functional decomposition.

Conclusion

Computer programming is problem solving. Computers require instructions to do anything interesting. Those instructions must be detailed. Think of writing a computer program to perform some task as similar to writing a term paper. Before writing, you decompose your paper’s topics into an outline.  That outline becomes your term paper’s structure.  The same is true for programming. When programming, your outline becomes your program’s skeleton.If you strip functional decomposition from all other tasks involved in writing a computer program, suddenly writing a reasonably detailed algorithm becomes remarkably simple. It used to be common knowledge that writing algorithms was considered a fundamental programming skill.  Somehow, this skill has gotten lost in the newer generation of programmers and the plethora of coding boot-camps that teach syntax but not programming. But If you learn this one simple skill it will place you in the top-tier of computer programmers. Your problem solving ability and systematic thinking in other endeavors will also improve. You just might start applying algorithmic thinking to your everyday life.

  • This post is geared towards students reading the book Think Java through chapter four. It purposely avoids Object-Oriented design, variable passing, and other topics so as to focus solely on functional decomposition.

Algorithms – Computer Programming’s Foundation

To many, computer programming seems an arcane topic, particularly when first introduced to it. Students learn variables, constants, conditionals, control flow, and numerous other topics. What is often lost – especially in these neophyte to guru in twelve weeks or less boot-camps – is what actually underlies all the arcane symbols comprising a computer language.*see note below

“Computer science is no more about computers than astronomy is about telescopes.”
Edsger W. Dijkstra

Edsger W. Dijkstra

Computer science, and by extension computer programming, is about problem solving. By itself, a computer is a particularly dumb conglomeration of silicon, wires, and aluminum. It does nothing but store and transport electrical charges from one location to another internally. It is not until a human, through his or her intellectual labors, harness the flow of the charges to perform some task that a computer does anything particularly interesting.  But getting computers to do something interesting require a systematic approach to performing tasks. Every step must be specified in detail and you must ensure not to overlook steps. You must devise a detailed procedure for the computer to follow to perform a task. That is computer programming’s essence: write procedures that dictate how a computer solves a  particular task.

So if computer science is not necessarily computer programming, then what exactly is computer science?  Of course, computer programming is an element of computer science, but what is computer science? The following video by “Art of the Problem” on YouTube explains.

Computer science is the science of computation. How to get computers to solve problems. The math behind pushing the boundaries of what computers can and cannot do is staggering. But this is the theoretical side to computer science. Consider the practical. A computer language is a set of instructions that humans can write to have a computer perform tasks. But as computers are dumb, those instructions must be explicit and accurate. Writing accurate instructions to perform a task require an accurate underlying algorithm.

Algorithms

Webster’s dictionary defines an algorithm as “a step-by-step procedure for solving a problem or accomplishing some end especially by a computer <cite here>.”  Here’s a humorous, yet insightful, video clip from “The Big Bang Theory” illustrating an algorithm.

A clip from “Terminator Two: Judgement Day” provides another more graphic, yet still humorous, example of an algorithm.

In the above clip, the Terminator uses one or more algorithms to obtain clothing. From visual input, he calculates the attributes of features such as height, weight, and foot size to determine the probability a person is a match. If not a match, he moves to the next person. If a match, he persuades the person to remove his or her clothes.

Computer programming is formalizing algorithms into a form usable by a computer. Algorithms are the solution to a task/problem. Code is the instructions performing the algorithm. The following video by “Art of the Problem” on YouTube introduces algorithms.

The above video assumes some knowledge of looping and conditional logic. However, if you are reading this as a supplement to “Think Java” then this post only assumes familiarity through chapter four of the book. This chapter introduces you to methods that do not return a value. You have not been introduced to methods that return values, looping, or conditional logic. So let’s consider another algorithm, purposely ignoring concepts not yet covered in “Think Java.”

Consider the task of boiling water. The following steps outline a basic algorithm.

  1. Get pot from cabinet.
  2. Take pot to the sink.
  3. Turn on water facet.
  4. Place water in pot.
  5. Turn off water facet.
  6. Place pot on stove.
  7. Turn on stove burner.
  8. Heat water until boiling.

The steps seem easy enough, but remember, computers are very dumb. These instructions are not explicit enough. For instance, consider the sub-steps involved in obtaining a pot from the cabinet.

  1. Walk over to cabinet.
  2. Open the cabinet.
  3. Reach into the cabinet.
  4. Grasp pot handle.
  5. Lift pot and take it out of the cabinet.

But of course, computers are too dumb to even understand these instructions. For instance, consider the sub-steps involved physically perform the first step, first sub-step.

  1. Turn body in direction of cabinet.
  2. Take alternating right and left steps until cabinet is reached.

But even still the computer is clueless, as these sub-sub-steps remain ambiguous. We could continue to break the steps down to the most fundamental level. For instance, instructions on how to move each muscle when walking to the cabinet.

Understanding muscular contractions is obviously taking our algorithm to a level too fundamental to be useful. Thankfully, algorithms build upon previously solved algorithms, which can be reused as a “black box.” But before considering algorithm reuse, first consider how to decompose an algorithm into more manageable sub-tasks through a process called functional decomposition.

Functional Decomposition

Functional decomposition is explained well by the following.

Societal Impact

There is a downside to our rush to formalize all problems into formal algorithms. We use computers to decide everything from product

Sometimes a computer’s formalization leads us to eschew common sense. And think about this last clip. Politics aside, I leave you with this vision of our near future. It’s not science fiction, it will be reality within a few decades at most.

* This post is particularly directed towards students that have completed chapters one through four of the book “Think Java.” by Allen B. Downey & Chris Mayfield.Note in this post I specifically avoid discussing repetition and conditional algorithms, preferring to keep this post simple. I also avoid discussing Object-Oriented analysis and design. Here, I focus on simple algorithms and functions. It is my personal belief, that understanding simple functional programming helps transition to Object-Oriented programming.