CPS130, Lecture 1: Introduction to Algorithms



9/8/2002

CPS130, Lecture 3/4: Programming, Examples, and Recurrence Relations

1. Programming and the Computing Environment

Although the text, pp, 21-23 and largeL1, p, 5 assume a random access machine environment, the background computing environment is still somewhat ambiguous.

We will view this ambiguity as flexibility and will instead try to focus precisely on exactly what we are counting when we try to determine the required computational resources of a specific algorithm. Algorithms and their programming implementation usually proceed by breaking down the computation into sub-computations. In the simplest case, these “elemental” subcomputations may be done with a control structure (e.g., for loop) or a recursive call. Often algorithms are expressed in a pseudo-programming language, but for complicated algorithms, this can be ghastly. It can be far preferable to first explain the essence of the algorithm in a clear mathematical notation and/or English and then proceed to pseudo-code if further clarification is needed. Our pseudo-code will often be pseudo-MATLAB. In MATLAB every variable is a matrix, an n x m array of numbers. MATLAB is a “call by value” language rather than a “call by reference (name)” language, and this can cause inefficiencies if care is not taken. I suggest you take some time to learn MATLAB since it can be viewed as a rapid prototyping language - sort of a super-calculator that can also do nonnumeric computation.

Another notion related to algorithms and programming is “proof of correctness.” Essentially this is just induction and I feel this should be addressed at the algorithm design level and not the pseudo-code level, but we will be flexible. Further comments regarding programming will occur throughout this lecture.

2. Examples

Example 1: max element of an integer array A = [a1, a2, …, an] and its index

input = A

Output = (M, ind)

Math description:

if we think of M and ind as functions of A we can write

[pic]

English description:

We first let M = a1, ind = 1. Then for each [pic], we compare M to ai. If ai > M, then

M [pic] ai and ind [pic] i.

There are many ways to code this algorithm. It can move along the array forwards or backward or use a recursive call. Here are two

Pseudocode descriptions:

function [M,ind]=maxint(A)

%

% these are comments

% initialize

%

M=0; ind=0; [m,n]=size(A);

for i=1:n

if A(i)>M

M=A(i); ind=i;

end

end

In fact this is real MATLAB (matlab from now on).

» A=[1,35,2,6];

» [M,ind]=maxint(A);

» m=[M,ind]

m = 35 2

A (memory inefficient) recursive implementation is:

function [M,ind]=rmaxint1(A)

%

% initialize

%

[m,n]=size(A);

%

M=A(1);ind=1;

if n==1

return

else

%

% this statement is inefficient since

% it puts A(1:n-1) on the call stack recursively

%

[M,ind]=rmaxint1(A(1:n-1));

end

if A(n)>M

M=A(n);

ind=n;

end

Again this is real matlab.

» a

a =

13 2 2 35 56 6 8 1 5

» [x,y]=rmaxint1(a)

x =

56

y =

5

A more efficient implementation makes A global (see Appendix):

function [M,ind]=rmaxint2(n)

%

% n is dimension of global row vector A

%

global A

if n == 1

M=A(1);ind=1;

else

[M,ind]=rmaxint2(n-1);

end

if A(n)>M

M=A(n);

ind=n;

end

A =

13 2 2 35 56 6 8 1 5

» [x,y]=rmaxint2(9)

x =

56

y =

5

It is clear in this simple example that (call it) maxint requires n-1 comparisons. First, if n=1, correctness is immediate. Also if the output is correct for an array with n = k (induction hypothesis), the comparison insures it is correct for a larger array with n = k+1. Hence correctness for all n is true by induction.

Which description is best? That depends: do you prefer apply pie or key lime pie. I personally like the math description and the recursive code best since I think they capture the essential recursion best and the correctness by induction seems clearer. Otherwise you must introduce the pseudo-induction of “loop invariance.” Many computer language people would intensely dislike the use of the recursive call in rmaxint since they would claim that this is “tail recursion” and is not as efficient as a loop structure. Perhaps, but maybe that’s the compiler’s problem, although, horrible inefficiencies can sneak in that might be hard to catch by even the best optimizing compiler. This is true in matlab which, as indicated above, does not “call by reference (name)” so all actual variables, not just pointers, are put on the call stack. It is often possible to avoid the recursive allocation problem in matlab by using “global” and “persistent” (documentation included in the appendix). This is done in rmaxint2 and in the next example.

Even though it is clear in this simple example that T(n) = n-1 comparisons are required to compute M, the essential feature about T is that

(R1) T(n+1) = T(n) + 1, T(1) = 0.

(R1) is called a recurrence (recursion) relation or difference equation. We will learn how to solve these equations for a variety of functions k(n) which will replace k = 1 here. They will give us a way to count the complexity of as algorithm given a specific measure (like comparison) of complexity.

Example 2: merging sorted subarrays

In this example we merge two distinct sorted subarrays A(p:q) and A(r:s) of an integer matrix A. Again we use recursion rather than the while loop on text, p 29. We also dump the results into C and use the persistent B in an analogous fashion to the temporary arrays L and R in the text. (I think the persistent feature here may solve the function stack variable problem mentioned above.). C can be put back into A, if desired, in the calling environment.

Note that in the special case p=q, A(p) is inserted into the already inserted sorted A(r:s); this is what is needed in insertion-sort (large, L1, p 3; text, p 17). It can also be used in merge-sort (large, L2,L3; text, pp 28-36).

Here is (efficient) matlab.

function C=merge(p,q,r,s,bstart)

%

% A(p:q), A(r:s) with necessary p>q and

% r>s must be sorted subarrays of global A;

% need not be contiguous; input A,p,q,r,s

% not checked (should be!?)

% A is global; must be declared in

%anything calling function including workspace if so;

% output C can be put back into A (outside of function)

% using p,q,r,s

%

persistent B;

global A;

%

%initialize

%

if bstart==1

B(1:(q-p+s-r+2))=0;

end;

%

% finish up, tidy up and get out

%

if p>q | r>s

if p>q,

pr=r; qs=s;

else

pr=p; qs=q;

end;

B(bstart:bstart+qs-pr) = A(pr:qs);

C=B;

B=[];

return;

end;

%

% update B and bstart

%

if A(p) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download