ads An Introduction to Algorithms

Section A.1 An Introduction to Algorithms

Most of the algorithms in this book will contain a combination of three kinds of steps: the assignment step, the conditional step, and the loop.

Subsection A.1.1 Assignments

In order to assign a value to a variable, we use an assignment step, which takes the form:

\begin{equation*} \textrm{Variable = Expression to be computed} \end{equation*}

The equals sign in most languages is used for assignment but some languages may use variations such as := or a left pointing arrow. Logical equality, which produces a boolean result and would be used in conditional or looping steps, is most commonly expressed with a double-equals, ==.

An example of an assignment is k = n - 1 which tells us to subtract 1 from the value of n and assign that value to variable k. During the execution of an algorithm, a variable may take on only one value at a time. Another example of an assignment is k = k - 1. This is an instruction to subtract one from the value of k and then reassign that value to k.

Subsection A.1.2 Conditional steps

Frequently there are steps that must be performed in an algorithm if and only if a certain condition is met. The conditional or "if ... then" step is then employed. For example, suppose that in step 2 of an algorithm we want to assure that the values of variables x and y satisfy the condition x <= y. The following step would accomplish this objective.

2. If x > y:
	2.1 t = x
	2.2 x = y
	2.3 y = t

Listing A.1.1.

Steps 2.1 through 2.3 would be bypassed if the condition x > y were false before step 2.

One slight variation is the "if ... then ... else" step, which allows us to prescribe a step to be taken if the condition is false. For example, if you wanted to exercise today, you might look out the window and execute the following algorithm.

1. If it is cold or raining:
		exercise indoors
	else: 
		go outside and run
2. Rest

Listing A.1.2.

Subsection A.1.3 Loops

The conditional step tells us to do something once if a logical condition is true. A loop tells us to repeat one or more steps, called the body of the loop, while the logical condition is true. Before every execution of the body, the condition is tested. The following flow diagram serves to illustrate the steps in a While loop.

Figure A.1.3. Flow diagram for a while loop

Suppose you wanted to solve the equation \(f(x) = 0\text{.}\) The following initial assignment and loop could be employed.

1. c = your first guess
2. While f(c) != 0:
		c = another guess

Listing A.1.4.

Caution: One must always guard against the possibility that the condition of a While loop will never become false. Such "infinite loops" are the bane of beginning programmers. The loop above could very well be such a situation, particularly if the equation has no solution, or if the variable takes on real values

In cases where consecutive integer values are to be assigned to a variable, a different loop construction, a For loop, is often employed. For example, suppose we wanted to assign variable k each of the integer values from m to n and for each of these values perform some undefined steps. We could accomplish this with a While loop:

1. k := m
2. While k <= n:
	2.1 execute some steps
	2.2 k = k + l

Listing A.1.5.

Alternatively, we can perform these steps with a For loop.

For k = m to n:
	execute some  steps

Listing A.1.6.

For loops such as this one have the advantage of being shorter than the equivalent While loop. The While loop construction has the advantage of being able to handle more different situations than the For loop.

Exercises A.1.4 Exercises

1.

What are the inputs and outputs of the algorithms listed in the first sentence of this section?

2.

What is wrong with this algorithm?

Input: a and b, integers
Output: the value of c will be a - b
(1) c = 0
(2) While a > b:
		(2.1) a := a - l
		(2.2) c := c + l

Listing A.1.7.

Answer.

The algorithm only works when a > b.

3.

Describe, in words, what the following algorithm does:

Input: k, a positive integer
Output: s = ?
(1) s = 0
(2) While k > 0:
    (2.1) s = s + k
    (2.2) k = k - 1

Listing A.1.8.

4.

Write While loops to replace the For loops in the following partial algorithms:

1. S = 0
2. for k = 1 to 5: S = S + k^2
The floor of a number is the greatest integer less than or equal to that number.
1. m = a positive integer greater than 1
2. B = floor(sqrt(m))
3. for i = 2 to B: if i divides evenly into m, jump to step 5
4. print "m is a prime" and exit
5. print "m is composite" and exit

5.

Describe in words what the following algorithm does:

Input: n, a positive integer
Output: k?
(1) f= 0
(2) k=n
(3) While k is even:
	(3.1) f = f+ 1
	(3.2) k = k div 2

Listing A.1.9.

6.

Fix the algorithm in Exercise 2.

You have attempted of activities on this page.

Prev Top Next