Lesson 3

Objectives

By the end of this lesson you will be able to:

• Understand what an algorithm is and how to create one
• Understand what pseudo code is and how to write it
• Understand what a flow chart is and how to create one
• Understand what a decision table is and how to read them
• Understand the importance of writing clean code
• Explain the principles utilized to write clean code

Anatomy of a Computer Program

A computer program is a collection of precise instructions to complete a task. In order to help determine which tasks a computer program needs to accomplish and the instructions required to complete those tasks, a certain amount of analysis and design needs to occur before the programmer can begin the development, testing, and implementation of a computer program.

Earlier in this course you learned about the software development life cycle, in this section you will examine the software design step in greater depth.

Designing a Solution

Before a computer program can be written, first the specifications of the program need to be documented. In addition to specifying the input(s) and the output, the steps necessary to convert the input into the correct output also need to be defined. In the following video the presenter demonstrates how computer programmers go about defining and documenting a simple problem, giving directions on how to get from point A to point B.

Introducing Algorithms

An algorithm is "a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time."

During the design phase of developing a computer program each task that the program must perform is broken down into a series of logical steps. These steps are commonly represented by Pseudocode, Flowcharts, and/or Decision Tables. The image below shows another example of an algorithm, how to prepare a dessert. The step-by-step instructions for how to prepare the dessert are the algorithm in this example.

Once we have formally specified an algorithm, we can build a machine (or write a program or hire a person) to carry out the steps contained in the algorithm. The machine (or program or person) need not understand the concepts or ideas underlying the solution. It merely has to do Step 1, Step 2, Step 3, . . . exactly as written. In computer science terminology, the machine, robot, person, or thing carrying out the steps of the algorithm is called a computing agent.

“. . . a well-ordered collection . . .”

An algorithm is a collection of operations, and there must be a clear and unambiguous ordering to these operations. Ordering means that we know which operation to do first and precisely which operation to do next as each step is successfully completed. After all, we cannot expect a computing agent to carry out our instructions correctly if it is confused about which instruction it should be doing next. Consider the following “algorithm” that was taken from the back of a shampoo bottle and is intended to be instructions on how to use the product.

Algorithm for Washing Your Hair

At Step 4, what operations should be repeated? If we go back to Step 1, we will be unnecessarily wetting our hair. (It is presumably still wet from the previous operations.) If we go back to Step 3 instead, we will not be getting our hair any cleaner because we have not reused the shampoo. The Repeat instruction in Step 4 is ambiguous in that it does not clearly specify what to do next. Therefore, it violates the well-ordered requirement of an algorithm. (It also has a second and even more serious problem—it never stops! We will have more to say about this second problem shortly.) Statements such as:

• Go back and do it again. (Do what again?)

• Start over. (From where?)

• If you understand this material, you may skip ahead. (How far?)

• Do either Part 1 or Part 2. (How do I decide which one to do?)

are ambiguous and can leave us confused and unsure about what operation to do next. We must be extremely precise in specifying the order in which operations are to be carried out. One possible way is to number the steps of the algorithm and use these numbers to specify the proper order of execution. For example, the ambiguous operations just shown could be made more precise as follows:

• Go back to Step 3 and continue execution from that point.

• Start over from Step 1.

• If you understand this material, skip ahead to Line 21.

• If you are 18 years of age or older, do Part 1 beginning with Step 9; otherwise, do Part 2 beginning with Step 40

“ . . .of unambiguous and effectively computable operations. . .”

Algorithms are composed of things called “operations,” but what do those operations look like? What types of building blocks can be used to construct an algorithm? The answer to these questions is that the operations used in an algorithm must meet two criteria—they must be unambiguous, and they must be effectively computable. Here is a possible “algorithm” for making a cherry pie:

Algorithm for Making a Cherry Pie

For a professional baker, this algorithm would be fine. He or she would understand how to carry out each of the operations listed. Novice cooks, like most of us, would probably understand the meaning of Steps 3 and 4. However, we would probably look at Steps 1 and 2, throw up our hands in confusion, and ask for clarification. We might then be given more detailed instructions.

With this additional information, most people—even inexperienced cooks—would understand what to do and could successfully carry out this baking algorithm. However, there might be some people, perhaps young children, who still do not fully understand each and every line. For those people, we must go through the simplification process again and describe the ambiguous steps in even more elementary terms.

For example, the computing agent executing the algorithm might not know the meaning of the instruction “Sift the flour” in Step 1.2, and we would have to explain it further.

Now, even a child should be able to carry out these operations. But if that were not the case, then we would go through the simplification process yet one more time, until every operation, every sentence, every word was clearly understood.

An unambiguous operation is one that can be understood and carried out directly by the computing agent without further simplification or explanation. When an operation is unambiguous, we call it a primitive operation, or simply a primitive of the computing agent carrying out the algorithm. An algorithm must be composed entirely of primitives. Naturally, the primitive operations of different individuals (or machines) vary depending on their sophistication, experience, and intelligence, as is the case with the cherry pie recipe, which varies with the baking experience of the person following the instructions. Hence, an algorithm for one computing agent might not be an algorithm for another.

One of the most important questions we will answer in this text is, what are the primitive operations of a typical modern computer system? Which operations can a hardware processor “understand” in the sense of being able to carry out directly, and which operations must be further refined and simplified?

However, it is not enough for an operation to be understandable. It must also be doable by the computing agent. If an algorithm tells me to flap my arms really quickly and fly, I understand perfectly well what it is asking me to do. However, I am incapable of doing it. “Doable” means there exists a computational process that allows the computing agent to complete that operation successfully. The formal term for “doable” is effectively computable.

For example, the following is an incorrect technique for finding and printing the 100th prime number. (A prime number is a whole number not evenly divisible by any numbers other than 1 and itself, such as 2, 3, 5, 7, 11, 13, ...)

Algorithm for Finding and Printing the 100th Prime Number

The problem with these instructions is in Step 1, “Generate a list L of all the prime numbers....” That operation cannot be completed. There are an infinite number of prime numbers, and it is not possible in a finite amount of time to generate the desired list L. No such computational process exists, and the operation described in Step 1 is not effectively computable. Here are some other examples of operations that, under certain circumstances, may not be effectively computable:

• Set number to 0.
• Set average to (sum 4 number). (Division by 0 is not permitted.)
• Set N to -1.
• Set the value of result to √N. (You cannot take the square root of negative values using real numbers.)
• Add 1 to the current value of x. (What if x currently has no value?)

. . .that produces a result. . .

Algorithms solve problems. To know whether a solution is correct, an algorithm must produce an observable result to a user, such as a numerical answer, a new object, or a change to its environment. Without some observable result, we would not be able to say whether the algorithm is right or wrong or even if it has completed its computations. In the case of the DVR algorithm (Figure 1.1), the result will be a set of recorded TV programs. The addition algorithm (Figure 1.2) produces an m-digit sum. Note that we use the word result rather than answer. Sometimes it is not possible for an algorithm to produce the correct answer because for a given set of input, a correct answer does not exist. In those cases, the algorithm may produce something else, such as an error message, a red warning light, or an approximation to the correct answer. Error messages, lights, and approximations, although not necessarily what we wanted, are all observable results.

. . .and halts in a finite amount of time.

Another important characteristic of algorithms is that the result must be produced after the execution of a finite number of operations, and we must guarantee that the algorithm eventually reaches a statement that says, “Stop, you are done” or something equivalent. We have already pointed out that the shampooing algorithm was not well ordered because we did not know which statements to repeat in Step 4. However, even if we knew which block of statements to repeat, the algorithm would still be incorrect because it makes no provision to terminate. It will essentially run forever, or until we run out of hot water, soap, or patience. This is called an infinite loop, and it is a common error in the design of algorithms.

This figure shows an algorithmic solution to the shampooing problem that meets all the criteria discussed in this section if we assume that you want to wash your hair twice. The algorithm of Figure 1.3 is well ordered. Each step is numbered, and the execution of the algorithm unfolds sequentially, beginning at Step 1 and proceeding from instruction i to instruction i 1 1, unless the operation specifies otherwise. (For example, the iterative instruction in Step 3 says that after completing Step 6, you should go back and start again at Step 4 until the value of WashCount equals 2.) The intent of each operation is (we assume) clear, unambiguous, and doable by the person washing his or her hair. Finally, the algorithm will halt. This is confirmed by observing that WashCount is initially set to 0 in Step 2. Step 6 says to add 1 to WashCount each time we lather and rinse our hair, so it will take on the values 0, 1, 2, . . . However, the iterative statement in Step 3 says stop lathering and rinsing when the value of WashCount reaches 2. At that point, the algorithm goes to Step 7 and terminates execution with the desired result: clean hair. (Although it is correct, do not expect to see this algorithm on the back of a shampoo bottle in the near future.)

As is true for any recipe or set of instructions, there is always more than a single way to write a correct solution. For example, the algorithm of Figure 1.3 could also be written as shown in Figure 1.4. Both of these are correct solutions to the shampooing problem. (Although they are both correct, they are not necessarily equally elegant.

Algorithmic Origins

The word algorithm is derived from the last name of Muhammad ibn Musa Al-Khowarizmi, a famous Persian mathematician and author from the eighth and ninth centuries. Al-Khowarizmi was a teacher at the House of Wisdom in Baghdad and the author of the book Kitab al jabr w’al muqabala, which in English means “The Concise Book of Calculation by Reduction.” Written in AD 820, it is one of the earliest mathematical textbooks, and its title gives us the word algebra (the Arabic word al jabr means “reduction”). In AD 825, Al-Khowarizmi wrote another book about the base-10 positional numbering system that had recently been developed in India. In this book, he described formalized, step-by-step procedures for doing arithmetic operations, such as addition, subtraction, and multiplication, on numbers represented in this new decimal system. In the twelfth century, this book was translated into Latin, introducing the base-10 Hindu-Arabic numbering system to Europe, and Al-Khowarizmi’s name became closely associated with these formal numerical techniques. His last name was rendered as Algoritmi in Latin characters, and eventually the formalized procedures that he pioneered and developed became known as algorithms in his honor.

Representing Algorithms

Before presenting any algorithms, we must first make an important decision. How should we represent them? What notation should we use to express our algorithms so that they are clear, precise, and unambiguous?

One possibility is natural language, the language we speak and write in our everyday lives. (This could be English, Spanish, Arabic, Japanese, Swahili, or any language.) This is an obvious choice because it is the language with which we are most familiar. If we use natural language, then our algorithms would read much the same as a term paper or an essay.

One of the problems with using natural language to represent algorithms is that natural language can be extremely verbose, causing the resulting algorithms to be rambling, unstructured, and hard to follow. An unstructured, “free-flowing” writing style might be wonderful for novels and essays, but it is horrible for algorithms. The lack of structure makes it difficult for the reader to locate specific sections of the algorithm because they are buried deep within the text. Without any clues to guide us, such as indentation, line numbering, or highlighting, locating the beginning of say a loop can be a daunting and time-consuming task.

A second problem is that natural language is too “rich” in interpretation and meaning. Natural language frequently relies on either context or a reader’s experiences to give precise meaning to a word or phrase. This permits different readers to interpret the same sentence in totally different ways. This may be acceptable, even desirable, when writing poetry or fiction, but it is disastrous when creating algorithms that must always execute in the same way and produce identical results.

Fortunately, algorithms have been around long enough that several proven methods have been adopted and used by the development community at-large. Most computer programmers use pseudocode to design and represent algorithms, but flow charts and decision tables also have their place in algorithmic design.

Introducing Pseudocode

One simple way to write out a program's logic is to break each task that the program must perform into a series of logical steps. Using the example in figure 2 which is a flowchart representing a program that compares two numbers and outputs the larger of the two, you might write out the steps in this fashion:

1. Input the first number and assign it to variable x
2. Input the second number and assign it to variable y
3. Compare the value of x to y
4. If the value of x is greater than the value of y, display the value of x
5. If the value of y is greater than the value of x, display the value of y

This is an example of an algorithm written in pseudocode. It is not written out in any particular programming language, but it can be used as a starting point for writing the actual programming code.

Introducing Flowcharts

A flowchart is a graphical representation of an algorithm. Figure 1 shows commonly used flowchart symbols available in the Microsoft Visio program. In figure 2 you see an algorithm designed to compare two numbers and display the larger of the two. Flowcharts can also be helpful to application developers in thinking through how an algorithm will be implemented in code.

Introducing Decision Tables

Decision tables are a precise yet compact way to model complex rule sets and their corresponding actions. Decision tables are usually represented in coding structures as a series of if-else statements or a switch block.

Decision tables are made up of four quadrants: conditions, condition alternatives, actions, and action entries.

1. Conditions represent under what condition an action should be applied.
2. Condition alternatives are boolean values indicating which action entries apply or don't apply
3. Actions indicate one or more actions to apply
4. Action entries are values or check-marks indicating what value to apply or in the case of multiple actions, check-marks indicating which actions apply.

In this example (figure 3), the decision table represents an algorithm for calculating discounts based on the quantity of product purchased. If the buyer purchases less than 10 items they will receive a 5% discount, if they purchase between 10 to 49 items they will receive a 10% discount, if they purchase 50 to 99 items they will get a 15% discount, and any purchase of 100 or more items will result in a 20% discount.

 

We'll have a chance to write this Decision Table out as actual C# code at the end of this lesson. First, you need to learn some basics about integrated development environments (IDEs) and how to use them to write a computer program.

Clean Coding

"In software, 80% or more of what we do is quaintly called “maintenance”: the act of repair." (from James O. Coplien in Robert Martin's Clean Code). Clean coding is a coding philosophy written about by author, software engineer, and programming guru Robert Martin (Uncle Bob). The following is an excerpt from Martin's introduction to Clean Code.

"Which door represents your code? Which door represents your team or your company? Why are we in that room? Is this just a normal code review or have we found a stream of horrible problems shortly after going live? Are we debugging in a panic, poring over code that we thought worked? Are customers leaving in droves and managers breathing down our necks? How can we make sure we wind up behind the right door when the going gets tough? The answer is: craftsmanship.

There are two parts to learning craftsmanship: knowledge and work. You must gain the knowledge of principles, patterns, practices, and heuristics that a craftsman knows, and you must also grind that knowledge into your fingers, eyes, and gut by working hard and practicing.

You can be taught the physics of riding a bicycle. Indeed, the classical mathematics is relatively straightforward. Gravity, friction, angular momentum, center of mass, and so forth, can be demonstrated with less than a page full of equations. Given those formulae I could prove to you that bicycle riding is practical and give you all the knowledge you needed to make it work. And you’d still fall down the first time you climbed on that bike.

Coding is no different. We could write down all the “feel good” principles of clean code and then trust you to do the work (in other words, let you fall down when you get on the bike), but then what kind of teachers would that make us, and what kind of student would that make you?

No. That’s not the way this class is going to work.

Learning to write clean code is hard work. It requires more than just the knowledge of principles and patterns. You must sweat over it. You must practice it yourself, and watch yourself fail. You must watch others practice it and fail. You must see them stumble and retrace their steps. You must see them agonize over decisions and see the price they pay for making those decisions the wrong way."

The 5S Philosophy

 James O. Coplien writes in the forward of Robert Martin's Clean Code book, "[i]n about 1951, a quality approach called Total Productive Maintenance (TPM) came on the Japanese scene. Its focus is on maintenance rather than on production. One of the major pillars of TPM is the a set of principles known as the "5S" principles.

The 5S philosophy comprises these concepts:

• Seiri, or organization (think “sort” in English). Knowing where things are—using approaches such as suitable naming—is crucial. You think naming identifiers isn’t important?
• Seiton, or tidiness (think “systematize” in English). There is an old American saying: A place for everything, and everything in its place. A piece of code should be where you expect to find it—and, if not, you should re-factor to get it there.
• Seiso, or cleaning (think “shine” in English): Keep the workplace free of hanging wires, grease, scraps, and waste. What do the authors here say about littering your code with comments and commented-out code lines that capture history or wishes for the future? Get rid of them.
• Seiketsu, or standardization: The group agrees about how to keep the workplace clean. Meaning, having a consistent coding style and set of practices within the group.
• Shutsuke, or discipline (self-discipline). This means having the discipline to follow the practices and to frequently reflect on one’s work and be willing to change.

SOLID Principles of Object-Oriented Design

Although you have not yet been introduced to how to create a class in an object-oriented programming architecture, you should at least be aware of the SOLID principles of object-oriented design.

Next Steps:

1. Complete and Submit: Journal 3.
2. Complete and Submit: Assignment 3.
3. Complete and Submit: Quiz 3.