Don L. [email protected] writes:
Design Manual, b Steven Skinea), there is this description of the
Its what is often referred to as ‘pseudo code’, a sort of generalised
programming language abstraction. There are no real rules and generally
only a
few very simple constructs to learn. In the example you give above,
possibly
the only two constructs that may need explination are the A[…] and
swap(…)
constructs.
Generally, pseudo code is something the author will define themselves
and you
will often find an explination of their particular flavor of pseudo code
in the
introduction or early chapters of the book. The primary aim of pseudo
code is
to describe algorithms in a general an concise manner without getting
bogged
down in the syntax associated with real code. There are some basic
conventions
for pseudo code, but no definite or specific rules.
Pretty much all programming languages have a basic set of things they
can do.
Most pseudo code will have some sort of construct to represent these
basic
operations. In general, you have notation to represent
- Basic variables and simple data structures such as arrays. You may
have a
‘struct’ or record type as well.
- Some construct to represent value asignment
- Some construct to represent branching/conditional operations, such as
‘if’
and ‘else’.
- looping constructs, such as ‘for’, ‘while’ and ‘until’.
- Named code blocks, sometimes done via some sort of ‘label’ or
function/procedure call.
By convention, variables with names like ‘i’, ‘j’, and ‘k’ are used to
represent counters or index variables. The variable ‘n’ is often used to
represent the count or size of something.
Generally speaking, constructs like A[] represent an array. something
like A[0]
would represent the first element of the array ‘A’, where ‘A’ is the
symbol or
name given to the storage location for the array of values. (more often
than
not, computer languages start counting from 0 rather than 1). A[j]
represents
the element of the array A at position j. A construct like A[][] usually
represents a two dimensional array, which might be used to represent
something
like a matrix.
The construct swap() represents what is often referred to as a function
or a
procedure. Essentially, it is a named block of code that will perform
some
operation. Often, functions are named blocks of code that when executed,
will
return some value while procedures are a block of code which will do
something,
but may not return any value.
The use of named blocks of code are really an abstraction that allow you
to
think at a higher level. For example, in the pseudo code you have,
swap(A[j],
A[j-1]). We know by the name that this procedure will ‘swap’ something.
We can
see that it takes two arguments (A[j] and A[j-1]), so we can be fairly
confident that what it is doing is swapping the two values at positions
j and
j-1 in the array A. We don’t have to think about how it does that
operation -
simply assume that it does and afterwards, the two values have been
swapped
over. We don’t need to think about how this swap operation will also
need to
have a temporary ‘holding’ place that the first value can be stored in
while
the second balue is moved form its position into the first position and
then
the first value is moved from its temporary position into the second
position.
Likewise, we don’t have to be concerned about whether the values being
operated
on are pointers, copies of the originals global values. We don’t have to
be
concerned with error handling, data typing etc etc. Instead, we only
have to
understand the concept of swapping two values without all the additional
overheads normally encountered in an actual program which implements
such an
operation.
The real trick with pseudo code is not to read too much into it. It is
meant to
be a high level, but still reasonably concise and unambiguous
description of an
algorithm.
When I first started learning this stuff, particularly sorting and
searching
algorithms, I found it very handy to have a deck of cards on hand. You
could
try it with the pseudo code above and imagine your trying to execute
that
pseudo code.
Shuffle the cards to ensure a random order. Then lay out 10 cards face
up on
the table. Those 10 cards represent your array ‘A’. As there are 10
cards, we
can say that your array has 10 elements, a size of 10. When you get to
the
‘swap()’ operation, just swap the two cards that correspond to the
arguments,
which will translate into array positions (i.e. card positions).
Doing this with each of the different sorting algorithms will give you a
real
appreciation of why some sorting algorithms are better than others. I
suspect
you will find this an extremely useful technique when it comes to less
obvious/intuitive sorting approaches, such as quicksort.
With respect to your question on books, I would recommend going to a
good
library and checking out some of the introductory books on discrete
maths, data
structures and algorithms. Different styles suit different people and
what I
found great you may not. For example, when I did my computing degree, I
didn’t
particularly like the style of the prescribed text books. I whent to the
library and discovered Donald Knuth and Nicholas Wirth. I found these
two
authors really good. For me, their explinations were clear, interesting
to read
and sat well with my conceptual model of the world. However, I know
others who
cannot stand their work.
Once you find an author or books you like, then try and get copies for
yourself. I highly recommend checking out Donald Knuth. In particular,
his
“Concrete Maths for Computing Science” (I think thats what it was called
- or
something similar). It is in my view and excellent book. His style is
clear and
he has included margin notes from students, which apart from adding
additional
insight/background, are often humorous and that always helps. He has
also
written an excellent series called “The Art of Computer Programming”,
but it is
quite ‘heavy’. However, as I said, I really like his style and
personally got a
lot out of it. There are also some great on-line resources from MIT
(they have
put a lot of their course resources on-line now and they are largely
free).
Therre is an excellent book called “Structure and Interpretation of
Computer
Programs”, which can be a bit heavy at times, but is an excellent
example of
the power of abstraction and using the right data structures to solve
problems.
Possibly its only drawback for many people is that it is based around
scheme.
However, you can still get a lot out of it without needing to fully
understand
scheme itself. There are also some movies on-line of the authors
presenting
courses based on the content of the book.
Finally, don’t get too concerned because this stuff looks like maths. In
reality, it is just notation used to describe a discrete set of steps
that need
to be followed. The mathematical like notation is used because it is
more
concise and less ambiguous than written english.
HTH
Tim
