From: Tim X Date: 2007-04-14T11:45:07+09:00 Subject: Re: Computer Science Math - For the Uninitiated Don Levan 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