Don Levan said:
Hello all,
A journey that has taken me from developing in Filemaker through the
self study of Ruby, Rails, and regular expressions has led me to
begin looking at algorithms and data structures. Though I don't have
a traditional computer science background, I am trying to educate
myself as best I can.
I am begin stymied by what looks like math but is greek to me. For
example, on the first page of the book I am reading (The Algorithm
Design Manual, b Steven Skinea), there is this description of the
insertion sort algorithm:
for i = 1 to n - 1 do
for j = i downto 2 do
if (A[j] < A[j-1]) then swap(A[j],A[j-1])
I can struggle through it, but I am wondering 1) what branch of math
is this? Is it algebra or something more complex? And 2) are there
any good (and accessible) books that will give me a basic
introduction to the language conventions?
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