From: Don Levan <levandon@...>
Date: 2007-04-15T08:23:33+09:00
Subject: Re: Computer Science Math - For the Uninitiated

Thank you all for taking the time to answer my questions. Tim, thank  
you especially for the suggestions on books and the idea of using a  
deck of cards. I can certainly see how that would make things easier.

Don

On Apr 13, 2007, at 10:45 PM, Tim X wrote:

> 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
>