Two-dimensional Arrays Top Contents

Footnotes

(1)
You might be wondering how I know Python lists are actually arrays. I came to this conclusion by looking at how long it took to access items in a very, very long list. In a list, accessing items at the back should take much longer than accessing items at the front. In an array, the amount of time should be the same. In my tests, the time to access an item was independent of the item's position. Therefore, Python lists must be arrays of some sort. You will learn more about this kind of analysis in your next Computer Science class.
(2)
Computer Scientists, when they have to write their annual reports, often refer to the things they are reporting on as darkspace. It's always good to have a lot of darkspace in your annual report!
(3)
In most other modern programming languages, a single / means integer division, so don't forget this when you learn a new language!
(4)
Languages that do not allow changes to a variable are called functional languages. Python is an "impure" functional language since it is mostly functional but allows for variable modification.
(5)
Another fundamental concept is analogy and if you understand the purpose of the envelope story after reading this section, you're well on your way to being a computer scientist!
(6)
The third great fundamental concept in computer science is generalization. In particular, computer scientists are always trying to make things more abstract and more general (but not overly so). The reason is that software/systems/models exhibiting the proper levels of abstraction and generalization are much much easier to understand and modify. This is especially useful when you are required to make a last second change to the software/system/model.
(7)
Even the envelope metaphor can be confusing since it implies that two variables having the same value must each have a copy of that value. Otherwise, how can one value be in two envelopes at the same time? For simple literals, copying is the norm. For more complex objects, the cost of copying would be prohibitive. The solution is to storing the address of the object, instead of the object itself, in the envelope. Two variables can now "hold" the same object since it is the address is copied.
(8)
In many other languages, you have to declare a variable with a special syntax before you can assign a value to it
(9)
The believed value of PI has changed throughout the centuries and not always to be more accurate (see http://en.wikipedia.org/wiki/History_of_Pi )
(10)
There are languages where it is possible to point a variable to another variable. The most famous of these languages are C and C++. Python, however, does not allow you to point a variable to a variable.
(11)
We will learn about loops in the next chapter.
(12)
In general, it is a bad idea to vary the kinds of characters that make up an indentation. One should use just spaces or just tabs, but should not use an indentation made up of spaces and tabs.
(13)
The information that is passed into a function is collectively known as arguments. The arguments are then bound to the variables that are found after the function name in the function definition.
(14)
The local function y does not really remember these values, but for an introductory course, this is a good enough explanation.
(15)
C++ and Java, as well as Python, give you another approach, objects. We will not go into objects in this course, but you will learn all about them in your next programming course.
(16)
Many times, the printing is done to a file, rather than the console.
(17)
This is not strictly true. In most operating systems, a program is expected to return an error code, if the program was not able to run to completion. Thus, raising an exception (see the chapter on error checking), will almost always cause a non-zero error code to be returned to the operating system. What should a program return if no errors are encountered? A zero. You can remember this saying to your self, "zero errors". Thus, in this text, main functions will always return zero. Note that the main's return statement will not be reached if an exception occurs.
(18)
From now on, we will use the word defined.
(19)
For variadic functions, which Python allows for, the number of arguments may be more or less than the number of formal parameters.
(20)
We will see the utility of the counting pattern for lists, for which there is no equivalent len function, in a future chapter.
(21)
The superior student will ascertain why this is so.
(22)
When you take a course in data structures and algorithm analysis, you will see that the run time of extractEvens grows in proportion to the square of the number of even elements in the list.
(23)
A function that works on and is bundled with an object is often called a method. You will learn more about objects and methods later in your academic career.
(24)
The reason is Python arrays are dynamic arrays, in that they grow larger as needed. If dynamic arrays are implemented properly, then the total cost of all appends divided by the number of appends is a small constant value. The upshot is that extractEvens now will in time proportional to the number of even values in the array, rather than the square of that number. This is quite an improvement! Suppose the input array is composed solely of a million even numbers. We would expect our new version of extractEvens to run, roughly, a million times faster than the original version.
(25)
We can't help if other folks are sloppy in their terminology.
(26)
Python has other built-in data structures as well. But even if Python had no built-in structures, one can use functions themselves as data structures!
(27)
If you are unclear about the need for reversing the arguments to ListCreate, you should instrument the loop by printing out the value of items each time the loop executes. Then all will become clear.
(28)
A function that can take a different number of arguments from call to call is called a variadic function.
(29)
When two variables, in this case a and list, point to the same thing, they are said to be aliases of one another.
(30)
Prepend is rather an awkward term, so we will use join as the function name, rather than prepend.
(31)
The test condition of the while loop is the reason for the comment that the length of listA must be greater than zero.
(32)
Note that while NodeValue and NodeNext are non-destructive operations, append is a destructive operation, since a pointer in the list is actually changed.
(33)
Sometimes, destructive functions return a value for convenience to the caller, in which case this generalization fails.
(34)
Again, when an operation does not affect its operands, it is said to be non-destructive. So, like the functions they wrap, head and tail are both non-destructive
(35)
This is one of the reasons objects would make a better base structure than arrays for nodes and lists. Ideally, nobody should call ListIndexNode except ListIndex and ListSetIndex. If objects are used, ListIndexNode can be made private, so that only other list functions can call it.
(36)
This idea of repeatedly inserting items in a list with the list remaining ordered is the basis for an important data structure, the priority queue. Priority queues are used in network connectivity algorithms and discrete-event simulations. You will learn about priority queues in a subsequent class
(37)
Actually, reversing the logic of greater than yields less than or equal, but we are ignoring situations when values match exactly. What happens in those cases is left as an exercise.
(38)
Mathematicians, being an inclusive bunch, like to invite zero to the factorial party.
(39)
Ellipses are the three dots in a row and are stand-ins for stuff that has been omitted.
(40)
If one views more multiplications as more complex, then, clearly, computing the factorial of n-1 is simpler than computing the factorial of n.
(41)
We'll see why the variable temp is needed in the next chapter.
(42)
A pineapple, the golden ratio, a chambered nautilus, etc.
(43)
13 is 7th Fibonacci number and seven is one more than six. A coincidence? Maybe...or maybe not!
(44)
Recall that a predicate function returns True or False.
(45)
The word is recurs, not recurses!
(46)
Yes, division is just repeated subtraction, just like multiplication is repeated division.
(47)
The loop variable is considered a outside variable changed by the loop.
(48)
A style of programming that uses no assignments is called functional programming and is very important in theorizing about the nature of computation.
(49)
Unfortunately, Python is not a good language in this regard, but the language Scheme is. When the value of a recursive call is immediately returned (i.e., not combined with some other value), a function is said to be tail recursive. The Scheme programming language optimizes tail recursive functions so that they are just as efficient as loops both in time and in space utilization.
(50)
A three-dimensional array would be an array whose elements are arrays whose elements are arrays. Arrays of two dimensions and higher are known as multi-dimensional arrays.
(51)
This choice of the backbone representing the rows is purely arbitrary, but when this choice is made, the matrix is said to be row-ordered. If the opposite choice is made, that the backbone represents the columns, then the matrix is said to be column-ordered. Most programming languages provide row-ordered matrices and higher dimensional arrays.

lusth@cs.ua.edu


Two-dimensional Arrays Top Contents