Don Levan <levandon@gmail.com> writes:
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
--
tcross (at) rapttech dot com dot au
