Courses/CS 1114/Lab Manual/Introducing Algorithms

From A-State Computer Science Wiki
Jump to: navigation, search
Noexternalauth.png

You do not have authorization to view all content on this page. This means some or all of the content here may be unavailable to you.
To get authorization visit this page by clicking on the link provided to you. For CSCADE users this means visiting this page by logging in and clicking on the "material" link of the assignment.

Introducing Algorithms

Introduction

This lab will introduce the concept of algorithms, discuss the relationship between algorithms and computer programs, and present the functional components of algorithms.

Topics Covered in this Lab

  • Definition of Algorithm.
  • Properties of Good Algorithms
  • Algorithms VS Computer Programs
  • Algorithm Components
  • Seeing Things from the Computing Perspective

Questions Answered in this Lab

  • What is an algorithm?
  • What properties can be found in a good algorithm?
  • How does creating an algorithm relate to creating a computer program?
  • What are the components of an algorithm and how do they relate to computer programming?
  • How can I improve my ability to create algorithms?

Demonstrable Skills Acquired in this Lab

  • The ability to create a written algorithm.
  • The ability to judge the difference between a good algorithm and a poor one.
  • An understanding of why algorithms are important in computer programming.
  • An understanding of the parts of an algorithm.
  • A better understanding of how to think algorithmically.

What is an Algorithm?

An algorithm is a specification of a behavioral process. It consists of a finite set of instructions that govern behavior step-by-step. Put simply, an algorithm is a precise, step-by-step plan for solving a problem. Examples of algorithms include a recipe for baking a cake, driving directions, or instructions for constructing an entertainment center. Algorithms are used extensively in computer programming; as programmers, we must present the computer with very precise instructions that it will then follow exactly. Since computers cannot reason on their own, the quality of the algorithms we construct will directly determine the quality of the programs we eventually write.

Properties of Good Algorithms

Well designed algorithms have three key properties: Precision, simplicity, and levels of abstraction.

Precision

If you write down instructions for solving a problem and input data (a starting point) and give them to two different people, will you get the same end result from both? If not, your instructions (algorithm) were not precise enough. People can take imprecise instructions and "fill in the blanks" to reason out what you intended – or what they think you intended. Since people think differently, two individuals might interpret a vague set of instructions differently, leading to multiple solutions. Computers cannot reason on their own. A computer, when presented with vague instructions, has only one option: fail. Therefore our algorithms must be precise and unambiguous. There must never be more than one way to interpret the steps.

Simplicity

Computers are unable to generalize. Internally, computers are capable only of performing mathematical and logical operations – they do not "think". If we intend to turn our algorithms into programs, we must write them in such a way that each step in the algorithm carries out one logical step. Exactly what "one logical step" is can be difficult to learn – or explain. For this reason, we create our algorithms with different levels of abstraction (the third property).

Levels of Abstraction

As humans, we like to keep the "big picture" in mind. We work well with generalized instructions, especially if they deal with tasks we are familiar with. Consider the instruction, "Check your email." To an experienced computer user, both the meaning of this instruction as well as the process for carrying it out are clear. For a novice, however, this instruction might not lead to a solution at all. A novice might need to know each step involved, such as:

algorithm check email
  1. turn on the computer
  2. log in to the operating system
  3. connect to the internet
  4. double-click with the left mouse button on the web browser’s icon
  5. click with the left mouse button in the address bar
  6. type the address of your web mail provider
  7. press the "Enter" key
  8. log in to your email provider’s site
  9. click on the "Inbox" link
end algorithm check email

Even some of the steps above might not be completely clear to the absolute beginner. "Connect to the internet," for example, might lead a beginner to ask "How?" The original statement "Check your email," as well as the more specific set of instructions given above, are examples of two different levels of abstraction. When we create an algorithm, we generally start at the top (or most general) level. We like to state in general terms what we would like the algorithm to accomplish – "Check your email" in this case. Then we start to refine our algorithm to fill in more details where they are necessary until we have steps that are simple and precise enough to be understood by a computer. Most well-designed algorithms contain several levels of abstraction. We need the higher levels to help us keep focused on the goal, while the computer demands that we fill in the lower levels.

Algorithms are often broken down into modules. Modules are individual sub-algorithms that explain more general steps. You might create a module to explain how to "connect to the internet" in the algorithm above, for example. These modules fill in the details of the logical steps they represent. This allows us to concentrate on the overall algorithm while still having a place to fill in the precise details. Here is a possible "connect to the internet" module:

module connect to the internet
  1. click on the Start menu
  2. move the mouse to Settings, then Network Connections, then to the name of your internet provider
  3. click on the name of your internet provider
  4. fill in user name and password
  5. click on "Connect"
end module connect to the internet

Now we could re-write the algorithm above to use this module:

algorithm check email
  1. turn on the computer
  2. log in to the operating system
  3. Invoke module connect to the internet
  4. double-click with the left mouse button on the web browser’s icon
  5. click with the left mouse button in the address bar
  6. type the address of your web mail provider
  7. press the "Enter" key
  8. log in to your email provider’s site
  9. click on the "Inbox" link
end algorithm check email

By keeping the details of how to perform each step separate from the higher-level algorithm, we can understand the main ideas without being distracted by the details. We can easily see what is being done by reading the description (name) of the module, and we can see how it is being done by looking in the module definition.

Algorithms VS Computer Programs

It has been stated above that algorithms are simply precise step-by-step plans for solving problems. Computer programs are the set of data and instructions — in a specific language — that operate a computer. What is the relationship between algorithms and computer programs? Put simply, a computer program is an implementation of an algorithm in a given programming language. The algorithm itself has no specific language associated with it, but the program must be constructed in a language the computer can understand.

It turns out that the "hard part" for most people is creating a good algorithm. Once you have learned to construct an algorithm that is precise enough to be translated into a programming language, learning that language and expressing your algorithm in it will be a much easier task. On the other hand, creating a computer program without understanding how to create a good algorithm is frustrating at best — it is impossible in all but the most trivial cases. You will also find that once you have mastered algorithmic thinking, new programming languages become much easier to learn.

Algorithm Components

There are five basic components that you will use to construct algorithms — although not all algorithms require all five:

data structures
Data are the representation of information used by an algorithm. Data structures are the "containers" used to store the data. The simplest data structures are variables and constants, where a symbolic name is used to represent a single unit of data. In a computer, a variable references a location in physical memory where the data value is stored. Variables represent data values that may change, while constants represent values that never change. More complex data structures include arrays, lists, and trees. These are used to organize many units of data in a single structure.
data manipulation instructions
These are instructions that allow the algorithm to read or write data or to transform data somehow, such as performing mathematical operations or string manipulation.
conditional expressions
Conditional expressions are the key to a computer’s ability to make decisions and act differently based on different inputs. These expressions are crucial for programming, but are also quite simple in nature. Conditional expressions are expressions whose result (answer) is either true or false. These expressions generally compare two values using relationships such as "greater-than", "less-than", "equal", "not equal", etc.
control structures
These structures determine what an algorithm will do after a decision is made. Control structures allow us to selectively execute or repeat certain portions of an algorithm. Without control structures, all algorithms would simply execute sequentially from top to bottom.
modules
Modules are used to group instructions that perform a related, logical task. Modules allow us to use higher levels of abstraction when we create our algorithms – and later our programs. They allow us to follow, trace, repair, and reuse our algorithms much more easily.

Seeing Things from the Computing Perspective

In order to create better algorithms, ones that can be easily converted to working computer programs, it helps to be able to see the world from the point of view of a computer. Another way to state this is that you need to learn to think algorithmically about problems. There are five things you need to be able to do to become skilled at "thinking like a computer":

Conceive of behavior as expressions of algorithms.
It is important to be able to look at any behavior and imagine what set of instructions are being carried out. This ability is not necessarily a "natural" way of thinking. You must learn to see something happen and hypothesize about what series of steps would produce that behavior. It is less important that your hypothesis be correct than that you are able to imagine it. It also does not matter whether your set of steps is – in reality – the algorithm being carried out. If your algorithm can reproduce the behavior, it is said to be a simulation of the behavior, and simulations are very important in computer science.
Conceive of things or beings that exhibit behavior as "processes."
A process is anything that is carrying out behavior specified by an algorithm. A process is simply a noun that is doing something. It is important to be able to generalize any thing that is carrying out any behavior as a process. As you read this lab, you are a process. In fact, every organ in your body that is functioning is a process. A rock rolling down a slope is a process. A rock sitting on level ground is not. In order to be considered a process, the thing must be (currently) doing something.
Conceive of algorithms as having levels of abstraction.
We never want an algorithm to be a giant sequential list of steps. If we created algorithms this way, the complexity would quickly overwhelm even the best programmer, and many of the things we take for granted – web browsers, for example – would be impossible to create. It is absolutely essential to be able to think of an algorithm in general terms, as a sequence of a few broad steps. Each of these broad steps can then be thought of as a series of smaller steps, and those can be broken into smaller steps. This process continues until you have the "baby steps" necessary for a computer to follow them, but we never start at the lowest level. We must always start with generalizations, then work our way carefully toward the precise steps of a programming language.
Realize that an algorithm’s usefulness can be limited by its complexity.
There is a certain amount of work that is called for by every algorithm, regardless of how fast a given processor can do that work. Some algorithms are, by their very nature, too complex to be useful in the real world. They would require too much work no matter how fast each step could be carried out. It is important to realize that not all correct algorithms are useful. There are many problems in computer science that are too complex to be practical – no matter how fast the computer – even though the algorithms themselves are sound. Such algorithms still have a place in the study of theoretical computer science, but would not be useful for applications.
Put aside (temporarily) other perspectives and view the world in terms of algorithms and data.
The computing perspective provides a new and different way of looking at and understanding reality. It is not always the right or best way to look at and study every phenomenon, but it does allow us to understand phenomena that we may not have been able to understand before. You should not ignore or forget your other ways of seeing things, but algorithmic thinking should become a new tool for exploring the world around you.

In-Lab Exercises

Information Icon.png

The in-lab problems are visible only to authorized students by linking to this page from the CSCADE site.