Learning Objectives

• Explain what we mean by “Computational Thinking”.
• Describe the problem being solved in a computational algorithm.
• Explain the process for generating computational algorithms.
• Generate and test algorithms to solve computational problems.
• Evaluate computational algorithms for exactness, correctness, termination, generalizability and understandability.
• Explain the role of programming in the field of Informatics.

Introduction

The goal of this book is to teach you to solve computational problems and to think like an engineer. Computational problems are problems that can be solved by the use of computations (a computation is what you do when you calculate something). Engineers are people who solve problems – they invent, design, analyze, build and test “things” to fulfill objectives and requirements. The single most important skill for you to learn is problem solving. Problem solving means the ability to formulate problems, think creatively about solutions, and express a solution clearly and accurately. As it turns out, the process of learning to program is an excellent opportunity to practice problem-solving skills.

This book strives to prepare you to write well-designed computer programs that solve interesting problems involving data.

Computational Thinking

Figure 1: “The seven components to computational thinking”(www.ignitemyfutureinschool.org/about)

Computational Thinking is the thought processes involved in understanding a problem and expressing its solution in a way that a computer can effectively carry out. Computational thinking involves solving problems, designing systems, and understanding human behavior (e.g. what the user needs or wants) – thinking like an engineer. Computational thinking is a fundamental skill for everyone, not just for programmers because computational thinking is what comes before any computing technology.^[1]

Computer science is the study of computation — what can be computed and how to compute it whereas computational thinking is:

Conceptualizing, not programming. Computer science is not only computer programming. Thinking like a computer scientist means more than being able to program a computer. It requires thinking at multiple levels of abstraction;

Fundamental, not rote skill. A fundamental skill is something every human being must know to function in modern society. Rote means a mechanical routine;

A way that humans, not computers, think. Computational thinking is a way humans solve problems; it is not trying to get humans to think like computers. Computers are dull and boring; humans are clever and imaginative. We humans make computers exciting. Equipped with computing devices, we use our cleverness to tackle problems we would not dare take on before the age of computing and build systems with functionality limited only by our imaginations;

Complements and combines mathematical and engineering thinking. Computer science inherently draws on mathematical thinking, given that, like all sciences, its formal foundations rest on mathematics. Computer science inherently draws on engineering thinking, given that we build systems that interact with the real world;

Ideas, not artifacts. It’s not just the software and hardware artifacts we produce that will be physically present everywhere and touch our lives all the time, it will be the computational concepts we use to approach and solve problems, manage our daily lives, and communicate and interact with other people;

For everyone, everywhere. Computational thinking will be a reality when it is so integral to human endeavors it disappears as an explicit philosophy.^[2]

Algorithms

Figure 2 “Are you happy?” by Typcut http://www.typcut.com/headup/are-you-happy

An algorithm specifies a series of steps that perform a particular computation or task. Throughout this book we’ll examine a number of different algorithms to solve a variety of computational problems.

Algorithms resemble recipes. Recipes tell you how to accomplish a task by performing a number of steps. For example, to bake a cake the steps are: preheat the oven; mix flour, sugar, and eggs thoroughly; pour into a baking pan; set the timer and bake until done.

However, “algorithm” is a technical term with a more specific meaning than “recipe”, and calling something an algorithm means that the following properties are all true:

1. An algorithm is an unambiguous description that makes clear what has to be implemented in order to solve the problem. In a recipe, a step such as “Bake until done” is ambiguous because it doesn’t explain what “done” means. A more explicit description such as “Bake until the cheese begins to bubble” is better. In a computational algorithm, a step such as “Choose a large number” is vague: what is large? 1 million, 1 billion, or 100? Does the number have to be different each time, or can the same number be used again?
2. An algorithm expects a defined set of inputs. For example, it might require two numbers where both numbers are greater than zero. Or it might require a word, or a list customer names.
3. An algorithm produces a defined set of outputs. It might output the larger of the two numbers, an all-uppercase version of a word, or a sorted version of the list of names.
4. An algorithm is guaranteed to terminate and produce a result, always stopping after a finite time. If an algorithm could potentially run forever, it wouldn’t be very useful because you might never get an answer.
5. Must be general for any input it is given. Algorithms solve general problems (determine if a password is valid); they are of little use if they only solve a specific problem (determine if ‘comp15’ is a valid password)
6. It is at the right level of detail…..the person or device executing the instruction know how to accomplish the instruction without any extra information.

Once we know it’s possible to solve a problem with an algorithm, a natural question is whether the algorithm is the best possible one. Can the problem be solved more quickly or efficiently?

The first thing you need to do before designing an algorithm is to understand completely the problem given. Read the problem’s description carefully, then read it again. Try sketching out by hand some examples of how the problem can be solved. Finally consider any special cases and design your algorithm to address them.

An algorithm does not solve a problem rather it gives you a series of steps that, if executed correctly, will result in a solution to a problem.

An Example Algorithm

Let us look at a very simple algorithm called find_max.

Problem: Given a list of positive numbers, return the largest number on the list.

Inputs: A list of positive numbers. This list must contain at least one number. (Asking for the largest number in a list of no numbers is not a meaningful question.)

Outputs: A number, which will be the largest number in the list.

Algorithm:

1. Start
2. Accept a list of positive numbers; set to nums_list
3. Set max_number to 0.
4. For each number in nums_list, compare it to max_number.
   1. If the number is larger, set max_number to the larger number.
5. max_number is now set to the largest number in the list of positive numbers, nums_list.
6. End

Does this meet the criteria for being an algorithm?

• Is it unambiguous? Yes. Each step of the algorithm consists of uncomplicated operations, and translating each step into programming code is straight forward.
• Does it have defined inputs and outputs? Yes.
• Is it guaranteed to terminate? Yes. The list nums_list is of finite length, so after looking at every element of the list the algorithm will stop.
• Is it general for any input? Yes. A list of any set of positive numbers works.
• Does it produce the correct result? Yes. When tested, the results are what are expected

Figure 3: Example Algorithm

How do we know if an algorithm is unambiguous, correct, comes to an end, is general AND is at the right level of detail? We must test the algorithm. Testing means verifying that the algorithm does what we expect it to do. In our ‘bake a cake’ example we know our algorithm is ‘working’ if, in the end, we get something that looks, smells and tastes like a cake.

Verifying your Algorithm

Figure 3 “Keyboard” by Geralt is licensed under CC 2

Your first step should be to carefully read through EACH step of the algorithm to check for ambiguity and if there is any information missing. To ensure that the algorithm is correct, terminates and is general for any input we devise ‘test cases’ for the algorithm.

A test case is a set of inputs, conditions, and expected results developed for a particular computational problem to be solved. A test case is really just a question that you ask of the algorithm (e.g. if my list is the three numbers 2, 14, and 11 does the algorithm return the number 14?). The point of executing the test is to make sure the algorithm is correct, that it terminates and is general for any input.

Good (effective) test cases:

• are easy to understand and execute
• are created with the user in mind (what input mistakes will be made? what are the preconditions?)
• make no assumptions (you already know what it is supposed to do)
• consider the boundaries for a specified range of values.

Let us look at the example algorithm from the previous section. The input for the algorithm is ‘a list of positive numbers’. To make it easy to understand and execute keep the test lists short. The preconditions are that the list only contains numbers and these numbers must be positive so include a test with a ‘non-number’ (i.e. a special character or a letter) and a test with a negative number. The boundaries for the list are zero and the highest positive number so include a test with zero and a large positive number. That is it! Here is an example of three different test cases.

Manually, you should step through your algorithm using each of the three test cases, making sure that the algorithm does indeed terminate and that you get your expected result. As our algorithms and programs become more complex, skilled programmers often break each test case into individual steps of the algorithm/program and indicate what the expected result of each step should be. When you write a detailed test case, you don’t necessarily need to specify the expected result for each test step if the result is obvious.

In computer programming we accept a problem to solve and develop an algorithm that can serve as a general solution. Once we have such a solution, we can use our computer to automate the execution. Programming is a skill that allows a competent programmer to take an algorithm and represent it in a notation (a program) that can be followed by a computer. These programs are written in programming languages (such as Python). Writing a correct and valid algorithm to solve a computational problem is key to writing good code. Learn to Think First and coding will come naturally!

The Process of Computational Problem Solving

Computational problem solving does not simply involve the act of computer programming. It is a process, with programming being only one of the steps. Before a program is written, a design for the program must be developed (the algorithm). And before a design can be developed, the problem to be solved must be well understood. Once written, the program must be thoroughly tested. These steps are outlined in Figure 5.

Figure 5: Process of Computational Problem Solving[footnote]Dierbach, Charles. Introduction to Computer Science Using Python: A Computational Problem-solving Focus. Wiley Publishing, 2012, pp17-18.[/footnote]

Values and Variables

A value is one of the basic things computer programs works with, like a password or a number of errors.

Values belong to different types: 21 is an integer (like the number of errors), and ‘comp15’ is a string of characters (like the password). Python lets you give names to values giving us the ability to generalize our algorithms.

One of the most powerful features of a programming language is the ability to use variables. A variable is simply a name that refers to a value as shown below,

Whenever the variable errors appears in a calculation the current value of the variable is used.

We need some way of storing information (i.e. the number of errors or the password) and manipulate them as well. This is where variables come into the picture. Variables are exactly what the name implies – their value can vary, i.e., you can store anything using a variable. Variables are just parts of your computer’s memory where you store some information. Unlike literal constants, you need some method of accessing these variables and hence you give them names.

Programmers generally choose names for their variables that are meaningful and document what the variable is used for. It is a good idea to begin variable names with a lowercase letter . The underscore character (_) can appear in a name and is often used in names with multiple words.

A program is a sequence of instructions that specifies how to perform a computation. The computation might be something mathematical, such as solving a system of mathematical equations or finding the roots of a polynomial, but it can also be a symbolic computation, such as searching and replacing text in a document or something graphical, like processing user input on an ATM device.

What is a Program?

Figure 6: “Python Code” by nyuhuhuu is licensed under CC-BY 2.0

The details look different in different computer programming languages, but there are some low-level conceptual patterns (constructs) that we use to write all programs. These constructs are not just for Python programs, they are a part of every programming language.

input Get data from the “outside world”. This might be reading data from a file, or even some kind of sensor like a microphone or GPS. In our initial algorithms and programs, our input will come from the user typing data on the keyboard.

output Display the results of the program on a screen or store them in a file or perhaps write them to a device like a speaker to play music or speak text.

sequential execution Perform statements one after another in the order they are encountered in the script.

conditional execution Checks for certain conditions and then executes or skips a sequence of statements.

repeated execution Perform some set of statements repeatedly, usually with some variation.

reuse Write a set of instructions once and give them a name and then reuse those instructions as needed throughout your program.

Believe it or not, that’s pretty much all there is to it. Every computer application you’ve ever used, no matter how complicated, is made up of constructs that look pretty much like these. So you can think of programming as the process of breaking a large, complex task into smaller and smaller subtasks until the subtasks are simple enough to be performed with one of these basic constructs. The “art” of writing a program is composing and weaving these basic elements together many times over to produce something that is useful to its users.

Computational Problem Design Using the Basic Programming Constructs

The key to better algorithm design and thus to programming lies in limiting the control structure to only three constructs as shown below.

1. The Sequence structure (sequential execution)
2. The Decision, Selection or Control structure (conditional execution)
3. Repetition or Iteration Structure (repeated execution)

Figure 7: the 3 Programming Constructs

 Let us look at some examples for the sequential control and the selection control.

Sequential Control Example

The following algorithm is an example of sequential control.

Does this meet the criteria for being an algorithm?

• Is it unambiguous? Yes. Each step of the algorithm consists of uncomplicated operations, and translating each step into programming code is straight forward.
• Does it have defined inputs and outputs? Yes.
• Is it guaranteed to terminate? Yes. Sequential control, by its nature, always ends.
• Is it general for any input? Yes. Any two numbers work in this design.
• Does it produce the correct result? Yes. When tested, the results are what are expected.

Here is an example of three different test cases that are used to verify the algorithm.

Selection Control

The following two algorithms are examples of selection control which uses the ‘IF’ statement in most programming languages.

Does this meet the criteria for being an algorithm?

• Is it unambiguous? Yes. Each step of the algorithm consists of uncomplicated operations, and translating each step into programming code is straight forward.
• Does it have defined inputs and outputs? Yes.
• Is it guaranteed to terminate? Yes. The input is of finite length, so after accepting the user’s choice and the two numbers the algorithm will stop.
• Is it general for any input? Yes. Any two numbers work in this design and only a choice of a’m’, ‘a’, or ‘s’ will result in numeric output.
• Does it produce the correct result? Yes. When tested, the results are what are expected.

Here is an example of three different test cases that are used to verify the algorithm.

This example uses an extension of the simple selection control structure we just saw and is referred to as the ‘IF-ELSE’ structure.

Does this meet the criteria for being an algorithm?

• Is it unambiguous? Yes. Each step of the algorithm consists of uncomplicated operations, and translating each step into programming code is straight forward.
• Does it have defined inputs and outputs? Yes.
• Is it guaranteed to terminate? Yes. The input is of finite length, so after accepting the user’s number, even if it is negative, the algorithm will stop.
• Is it general for any input? Yes. Any number entered in this design will work.
• Does it produce the correct result? Yes. When tested, the results are what are expected.

Here is an example of three different test cases that are used to verify the algorithm.

Iterative Control Examples

The third programming control is the iterative or, also referred to as, the repetition structure. This control structure causes certain steps to be repeated in a sequence a specified number of times or until a condition is met. This is what is called a ‘loop’ in programming

In all programming languages there are generally two options: an indefinite loop (the Python ‘WHILE’ programming statement) and a definite loop (the Python ‘FOR’ programming statement). We can use these two constructs, WHILE and FOR, for iterations or loops in our algorithms.

The following algorithm is an example of iterative control using WHILE.

Does this meet the criteria for being an algorithm?

• Is it unambiguous? Yes. Each step of the algorithm consists of uncomplicated operations, and translating each step into programming code is straight forward.
• Does it have defined inputs and outputs? Yes.
• Is it guaranteed to terminate? Yes. The input is of finite length, so after accepting the user’s keyboard character, even if it is not a letter, the algorithm will stop.
• Is it general for any input? Yes. Any keyboard character entered in this design will work.
• Does it produce the correct result? Yes. When tested, the results are what are expected.

Here is an example of three different test cases that are used to verify the algorithm.

The following algorithm is an example of iterative control using FOR. This statement is used when the number of iterations is known in advance.

Does this meet the criteria for being an algorithm?

• Is it unambiguous? Yes. Each step of the algorithm consists of uncomplicated operations, and translating each step into programming code is straight forward.
• Does it have defined inputs and outputs? Yes.
• Is it guaranteed to terminate? Yes. The input is of finite length, so after accepting the user’s number of words to enter and any characters typed on the keyboard, even if it is not a ‘word’ per say, the algorithm will stop.
• Is it general for any input? Yes. Any positive integer greater than zero and any size ‘word’ will work.
• Does it produce the correct result? Yes. When tested, the results are what are expected.

Here is an example of two different test cases that are used to verify the algorithm.

The Role of Programming in the Field of Informatics

Figure8: iPhone apps by Jaap Arriens/NurPhoto via Getty Images (abcnews.go.com)

You see computer programming in use every day. When you use Google or your smartphone, or watch a movie with special effects, there is programing at work. When you order a product over the Internet, there is code in the web site, in the cryptography used to keep your credit card number secure, and in the way that UPS routes their delivery vehicle to get your order to you as quickly as possible.

Programming is indeed important to an informatics professional as they are interested in finding solutions for a wide variety of computational problems involving data.

When you Google the words “pie recipe,” Google reports that it finds approximately 38 million pages, ranked in order of estimated relevance and usefulness. Facebook has approximately 1 billion active users who generate over 3 billion comments and “Likes” each day. GenBank, a national database of DNA sequences used by biologists and medical researchers studying genetic diseases, has over 100 million genetic sequences with over 100 billion DNA base pairs. According to the International Data Corporation, by 2020 the digital universe – the data we create and copy annually – will reach 44 zettabytes, or 44 trillion gigabytes.

Figure 9: The Digital Universe (www.emc.com/leadership/digital-universe/2014iview/images)

 Doing meaningful things with data is challenging, even if we’re not dealing with millions or billions of things. In this book, we will be working with smaller sets of data. But much of what we’ll do will be applicable to very large amounts of data too.

Unit Summary

Computational Thinking is the thought processes involved in formulating a problem and expressing its solution in a way that a computer—human or machine—can effectively carry out.

Computational Thinking is what comes before any computing technology—thought of by a human, knowing full well the power of automation.

Writing a correct and valid algorithm to solve a computational problem is key to writing good code.

1. First, understand the problem
   1. What are the inputs?
   2. What are the outputs (or results)?
   3. Can we break the problem into parts?
2. Second, design the process (write the algorithm!).
   1. Think about the connections between the input & output.
   2. Consider designing ‘backwards’.
   3. Have you seen the problem before? In a slightly different form?
   4. Can you solve part of the problem?
   5. Did you use all the inputs?
3. Third, test your design.
   1. Can you test it on a variety of inputs?
   2. Can you think of how you might write the algorithm differently if you had to start again?
4. Last, write the program (we will be addressing this in our next Unit).
   1. Does it solve the problem? Does it meet all the requirements? Is the output correct?
   2. Does it terminate?
   3. Is it general for all cases?

Practice Problems

1. Write about a process in your life (e.g. driving to the mall, walking to class, etc.) and estimate the number of steps necessary to complete the task. Would you consider this a complex or simple task? What happens if you scale that task (e.g. driving two states away to the mall)? Is your method the most efficient? Can you come up with a more efficient way?
2. Given five cards randomly placed in a row like the ones below write an algorithm to sort the cards. How would your algorithm change if there were 10 cards? What about 100 cards?
   
3. Write an algorithm to find the average of 25 test grades out of a possible 100 points.
4. If you are given three sticks, you may or may not be able to arrange them in a triangle. For example, if one of the sticks is 12 inches long and the other two are one inch long, it is clear that you will not be able to get the short sticks to meet in the middle. For any three lengths, there is a simple test to see if it is possible to form a triangle: “If any of the three lengths is greater than the sum of the other two, then you cannot form a triangle. Otherwise, you can.”Write an algorithm that accepts three integers as arguments, and that displays either “Yes” or “No,” depending on whether you can or cannot form a triangle from sticks with the given lengths.
5. ROT13 is a weak form of encryption that involves “rotating” each letter in a word by 13 places. To rotate a letter means to shift it through the alphabet, wrapping around to the beginning if necessary, so ‘A’ shifted by 3 is ‘D’ and ‘Z’ shifted by 1 is ‘A’.
   Write an algorithm that accepts a word and an integer from the user, and that prints a new encrypted word that contains the letters from the original word “rotated” by the given amount (the integer input). For example, “cheer” rotated by 7 is “jolly” and “melon” rotated by −10 is “cubed.”
6. Write an algorithm to accept a score between 0.0 and 1.0. If the score is out of range, display an error message. If the score is between 0.0 and 1.0, display a grade using the following table:
   

   Score	Grade
   >= 0.9	A
   >= 0.8	B
   >= 0.7	C
   >= 0.6	D
   < 0.6	E

7. Write an algorithm which repeatedly accepts numbers until the user enters “done”. Once “done” is entered, display the total sum of all the numbers, the count of numbers entered, and the average of all the numbers.
8. Write an algorithm that sums a series of ten positive integers entered by the user excluding all numbers greater than 100. Display the final sum.