Algorithms: Sequential, Parallel and Distributed 1-1
Chapter 1
Introduction and Preliminaries
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 1-2
Lecture Notes
Overview
In Chapter 1 we introduce some fundamental algorithms that date back centuries, but which
still have an important role to play in today’s modern computing environment. These
examples are intended to give the student a glimpse of the history of the study of algorithms,
and at the same time to make the important observation that the most straightforward algorithm
for a given problem is often not the most efficient. We consider the problems of computing
powers, finding the gcd of two integers, computing square roots and, more generally, zeros of
Chapter Objectives
After completing the chapter, the student will know:
• Some of the historical basis for the study of algorithms
• The importance of analyzing the performance of a given algorithm
• The importance of not necessarily settling for the most straightforward solution to a
problem
• The efficient solutions to some fundamental computational problems, which have a long
history and have applications to modern day disciplines
• The necessity to design algorithms that exploit the emergence of new computing paradigms
such as parallel and distributed computational environments
Instructor Notes
While an instructor might decide to make all or part of Chapter 1 as a reading assignment
(depending on the student’s background), it is important to note that the examples introduced
should be part of the student’s toolkit, since they frequently occur in design of many algorithms
used in science, engineering and business applications.
The complexity (computing time) of an algorithm is formally defined in Chapter 2.
Algorithms: Sequential, Parallel and Distributed 1-3
Solutions to Selected Exercises
1.1 a) 123 = 1111011 in binary. Removing the most significant digit, and scanning from left-
1.2 a) 123 = 1111011. We initialize AccumPow = 1 and Pow = x.
Removing the most significant digit, and scanning from right to left we obtain
1.4. Suppose n has k + 1 binary digits, and let m denote the number of multiplications
1.5 a)
function LRBinaryPowers(x, B[0:m – 1])
Input: B[0:m – 1] (a binary string representing an integer n, where B[i] is the (i + 1)st most
significant bit of n)
x (a real number)
end LRBinaryPowers
Algorithms: Sequential, Parallel and Distributed 1-4
b) First convert a decimal number to a binary string using the following recursive function and
then apply the function LRBinaryPowers given in part a):
procedure DecimalToBinary(n, B[0:m – 1])
1.10 a) Let r be the remainder when a is divided by b, i.e., r = a mod b. By Formula (1.1.2)
we have that gcd(b,r) = gcd(a,b) = g. Now suppose that we have already computed integers i
and j such that
Substituting Formula (2) for r into Formula (1), we obtain:
This yields the following recursive algorithm for computing g, s, t, given a and b.
Formatted: Portuguese (Brazil)
if b = 0 then
g ← b
s ← 1
t ← 0
1.11 a) The initial value of x and value of x after each iteration of the while loop in
|2.4494944-6/2.4494944|=.0000093<0.001= error.
1.12 The following is pseudocode for finding an approximation to a zero of a continuous
function using the bisection method.
function Bisec(f(x), a, b, error)
Input: f(x) (continuous function in the interval [a,b])
endif
endwhile
return(a)
end Bisec
Algorithms: Sequential, Parallel and Distributed 1-6
The following is a recursive version.
function BisecRec(f(x), a, b, error)
1.13 a) Assuming c is a positive integer, find a zero of
cxxf −= 2
)(
, starting with interval
[1,c].
[2.4453125,2.4648438], [2.4453125,2.4550781],
[2.4489746,2.4501953], [2.4489746,2.4495850],
[2.4494324,2.4495087], [2.4494705,2.4495087],
where 2.4494992-2.4494896=0.0000096<0.00001 = error. The total number of iterations is
Algorithms: Sequential, Parallel and Distributed 1-7
For the function
axxf −= 2
)(
this becomes
xi = xi-1 – (x2
i-1 – a) / 2(xi-1)
= (xi-1 + a / xi-1) / 2,
which is precisely the recurrence relation for BabylonianSQRT.
1.18 The following procedure reads in alphanumeric characters and converts them online to
procedure InputNumber(Number,Error)
Input: This procedure continues to read in alphanumeric characters until a sentinel
1.19 Consider a polynomial P(x)=anxn + an-1xn-1 +…+ a1x + a0
For convenience, we assume that n is odd (the same argument applies when n is even). Let
Algorithms: Sequential, Parallel and Distributed 1-8