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)

From now on, we will use the word defined.

(18)

For variadic functions, which Python allows for, the number of arguments may be more or less than the number of formal parameters.

(19)

We will see the utility of the counting pattern for lists, for which there is no equivalent len function, in a future chapter.

(20)

The superior student will ascertain why this is so.

(21)

We can't help if other folks are sloppy in their terminology.

(22)

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!

(23)

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.

(24)

A function that can take a different number of arguments from call to call is called a variadic function.

(25)

When two variables, in this case a and list, point to the same thing, they are said to be aliases of one another.

(26)

Prepend is rather an awkward term, so we will use join as the function name, rather than prepend.

(27)

The while test is the reason for the comment that the length of listA must be greater than zero.

(28)

Note that while NodeValue and NodeNext are non-destructive operations, append is a destructive operation, since a pointer in the list is actually changed.

(29)

Sometimes, destructive functions return a value for convenience to the caller, in which case this generalization fails.

(30)

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

(31)

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.

(32)

Mathematicians, being an inclusive bunch, like to invite zero to the factorial party.

(33)

Ellipses are the three dots in a row and are stand-ins for stuff that has been omitted.

(34)

If one views more multiplications as more complex, then, clearly, computing the factorial of n-1 is simpler than computing the factorial of n.

(35)

We'll see why the variable temp is needed in the next chapter.

(36)

A pineapple, the golden ratio, a chambered nautilus, etc.

(37)

13 is 7^th Fibonacci number and seven is one more than six. A coincidence? Maybe...or maybe not!

(38)

Recall that a predicate function returns True or False.

(39)

The word is recurs, not recurses!

(40)

Yes, division is just repeated subtraction, just like multiplication is repeated division.

(41)

The loop variable is considered a outside variable changed by the loop.

(42)

A style of programming that uses no assignments is called functional programming and is very important in theorizing about the nature of computation.

(43)

Unfortunately, Python is not a good language in this regard, but the language Scheme is.

Contents