Functional Problem Solving (CSC 151 2014F) : Readings
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: We consider the primary ingredients of algorithms.
You now have some experience writing an algorithm of your own. As you may have guessed, different algorithms often share some common aspects. These are the fundamental "ingredients." Those who like to cook know that many cookbooks often spend their introductory chapters going over the finer details of the cuisine's basic ingredients--one of our favorite cookbooks on Italian cuisine has several pages on olive oil alone.
Just as a skilled chef needs to know their basic ingredients in order to be able to use them creatively and effectively, it is worthwhile for us to consider the parts (or ingredients) of algorithms so we can rely on them when we write new algorithms.
In this section we will detail what we consider the five primary algorithmic ingredients.
As we write algorithms, we like to name things. Sometimes we like to use very descriptive long names, such as "the second vertical fold" or "the marker in your left hand." Other times we use shorter, more abbreviated names such as "fold-2" or "left-marker."
As we start to write more formal algorithms, we will need techniques for declaring which names we are using and indicating what thing the name refers to. It is also often useful to note what kind of thing they name.
We call these named values variables, even though they don't always vary. So long as we choose descriptive names, variables help us avoid ambiguity. Perhaps you encountered instructions on the first day's lab that had unclear references to "it" in them. Using clear variable names helps improve clarity.
Many algorithms take data as input (and generate other data as output). An algorithm to produce a paper airplane might take the dimensions of the paper as input. An algorithm to draw a smiley face might take the size of the face as input. A "find the square root" algorithm would take a number as input.
In all of these cases, the algorithm should work for many different values of the input. For example, the square root algorithm should return the correct answer whether it is given 16 or 325.8923. So long as the input is "reasonable," the algorithm should work. What would be an unreasonable input? Giving the square root algorithm a sheet of paper might be one example.
We call these inputs parameters.
At times, our algorithms have to account for different conditions, doing different things depending on those conditions. In a smiley-face drawing algorithm, we might check what kind of face we want to draw, or whether the marker is open or closed. In a paper-airplane folding algorithm, we might want to check whether the paper is oriented the expected way.
We call such operations conditionals. Conditionals typically take either the form
if some condition holds
then
do something
or a more general form where an alternative action is specified, as in
if some condition holds
then
do something
otherwise
do something else
At times, we need to decide between even more than two possibilities. Typically, we organize those as a sequence of tests (called guards) and the corresponding things to do.
Sometimes our algorithms require us to do something again and again, a technique called repetition. Repetition can take many forms. We might,
In all of these cases, we have the advantage of being able to represent in only a few short statements what could become a rather lengthy sequence of operations to conduct.
Many algorithms require the use of some common or more basic operations and actions. We can typically make use of a collection of commands that are parameterized (i.e., take named inputs) and are referred to by a single name. For instance, given the task of creating a drawing, one might wish to utilize a "draw a circle" subroutine.
It is very useful to write algorithms for such common actions so that we can use them in other algorithms. Such helper algorithms are called subroutines. In this course, we will also often call them procedures or even functions.
This strategy of decomposing a task into manageable units is one of the most important techniques in algorithmic problem solving. It is much easier both to write and debug algorithms that solve small, specialized problems, and then use these subroutines to accomplish bigger, more complicated tasks. This helps the problem solver (and the reader!) to think about and understand the "big picture" as well as iteratively refine coarse steps of an algorithm into more detail.
a. In your own words, explain the difference between a variable and a parameter.
b. Suppose we have an algorithm for computing the average number of computer science students that visit the lab for tutoring on Mondays. Is the total number of students that visited on Mondays more likely to be a variable or a parameter? Why?
Say we add a robot to work at the information desk, and we want the robot to smile whenever someone is present in the vicinity. To what extent is a conditional, subroutine, and/or repetition necessary for this task?