Week 7 Recursion

Recursion is a programming technique useful for its brevity. It can replace long and error-prone iterative versions of the same solution. And its implementation can be shorter and easier to read using condensed logic statements. Practically, it involves a function calling itself repeatedly, until directed to a block that ends the calls given some condition. In this class, we use recursion most often to deal with nested ADTs like trees and linked lists, or, more basically, nested Python lists. If you were given the task of filtering out elements in a 1D list with some condition, an iterative method of checking every single element is very intuitive. This approach runs into problems, however, when you have an n-D nested list. It may steer you towards thinking you need n-nested for loops...but you don't know what n is. This is a classic example of recursion giving an elegant solution to the problem. You set up the function such that there is a block that processes the list as if it were a 1D list. This is called the base case, and it is here that we stop the repeated calls to itself. We know how to solve the 1D list problem. The above iterative method would work (or if you're a purist, you can generalize the recursion to single elements). Once we have a solution, we return it to the general case block, where it can be think of as the block that puts all the base cases together. In the filtering problem, if I reach the base case, I return a list of wanted elements back to the general case, and a portion of the general case block could be joining all the lists returned by the base cases to give a list of every single wanted elements in the n-D nested list. Given a nested problem in the form of [ [Problem], [Problem, [Problem] ] ], recursion solves it by reducing it to a single Problem, giving a Solution, then constructing the solution [ [Solution], [Solution, [Solution] ] ] -> [Solution, Solution, Solution] to be returned. This is the logic behind the method of recursion problem solving.

Week READING WEEK

\( ' .')/

Week 6 Name scopes

One of the interesting things that came up in lecture this month was the Python built-in name scope statements, global and nonlocal,and closely related, globals() and locals(). global should be relatively familiar to most. It allows you to define a variable inside a function that can be used outside of the function. nonlocal is a neat extention that, functionally, is almost the reverse of global, and is most prevalent when you define a function inside a function. It allows you to reference a variable on the nested function that you defined on the outside function. If you have g() inside f(), and you define x = 5 inside f(), typing "nonlocal x" inside g() allows you access to the x you defined in f to do whatever you want with it.
The closely related locals() and globals() are functions themselves, and you can call them whenever to check the current locally or globally defined names. They both return a dictionary of variable names and their values.
dir() is also related. Called without an argument, it gives you the currently defined names in a list. Called with an argument, and it will give you all the methods and attributes that the argument has.
dir() does not discriminate between attributes and methods, and I was curious as to how to find simply all the methods that a class has, and it turns out to be possible using the built-in module inspect. To find all methods in a class, you type the following: inspect.getmembers(your_object, predicate=ismethod). "ismethod" is not the only keyword argument you can type. There is also ismodule, isclass, isfunction, and many others that you can find on the official Python documentation page.

Week 5 Floating Point Precision continued

Last week we saw that Python sometimes deal with decimals strangely. Here is another example you can try in your shell.

>>> 1.1 + 2.2
3.3000000000000003

The pinch is that Python only stores around 16 significant figures. Any numbers after that is up to chance. We say that standard deviation on the a value x is 10e-16 * x. This is the error you would see in the format datum = value +/- error. These errors propagate to the rules of statistics, and is the reason why floating point precision is so important. The math is out of the scope for this course, but an example of error propagation is the following:
given x = A +/- e1, y = B +/- e2, then x + y is given by x + y = A + B +/- sqrt(e1^2 + e2^2).
Strangely enough, the error of the sum do not simply add like e1 + e2, but is given by the Pythagorean formula. Let us also define the percentage error as error_value / datum_value. An error of 5 on a value of 100 thus has a 5% error. What happens to the percentage error when you add two of the same value with errors?

(100 +/- 5) + (100 +/- 5) = (100 + 100) +/- (sqrt(5^2 + 5^2)) = 200 +/- 7

7/200 = 3.5%. The percentage error has gone down! If we had simply multiplied our value by two, we would've gotten 2*(100 +/- 5) = 200 +/- 10, giving the same 10% error. The reason for this reduction in error from the previous example is due to the fact that, despite the values being the same, we were actually adding two distinct datum values. And the rules of statistics says that the more data you have, the better. These are some of the things you might encounter doing any large scale or lengthy computations on a computer.

Week 4 - Floating point precision

Outside of the realm of graphic interfaces or databases, a major field in cs is the science of computation. This is your typical "number cruncher" that calculates pi to the 3 billionth digit. Inevitably, big numbers are involved. Or sometimes, extremely small numbers. But of course, large or small, any number can be concisely represented in scientific notation. 30000 and 0.00003 in scientific notation only differ by a sign change: 3e5 vs 3e-5. But what if you want to store 1/3 in a variable? 1/3 = 0.333333... You can't type infinite digits can you? But being an eager cs student you immediately look for a workaround. Okay, I'll just type x = 1./3. And typing 3 * x in the shell gives me 1.0. Tada, I made my program store infinite decimals.

Sadly, that is not that case. Here's an example to try. Type in the shell 1e-20 + 1 - 1. From inspection we see trivially that the answer is 1e-20, yet our program doesn't give us that answer. It gave us 0.0! How can this be? Next, try 1e-20 + (1 - 1). What do you see? Next, try lowering the number 20 until you see "proper" results.

>>> 1e-15 + 1 - 1
1.1102230246251565e-15

That certainly is strange isn't it?

Week 3 OOP

One of the main topics in the our first 3 weeks of CSC148 is the benefit of using object-oriented programming (OOP), which involve writing classes, in creating code and projects. Using classes saves the programmer from rewriting similar code and provides clear organization of both readability and usability. At face-value, they serve the same function as user-defined functions; that is, you write a collection functions to avoid rewriting written code. The design of this style, however, with object-creation, object attributes, and inheritance, can provide structure that linear programming does not provide. Each class is analogous to a factory that can spit out an object with specifications you make and an instruction manual on what it can do (dir()). The use of inheritance provides an organization of objects often similar to our own organization of things in day-to-day life: using a branching tree that starts out broadly and branch into more and more specific levels. For any large-scale programming projects you may work on, OOP is of tremendous importance.

For a review or intro-level overview of programming with OOP, MIT ocw is a good source. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/ They even have assignments and lecture slides and transcripts posted.

Python has a free-for-all mentality, and both programmers and users can define and change almost anything they want about an object, such as its attribute value. Sometimes when writing OOP code for some audience, you may want to hide away the user's ability to change an object's attribute. One way of doing this is using "property" inside your class definition. When the user types "my_object.attribute_1" or "my_object.attribute_1 = new_value", it looks like they are accessing attribute variables, when really, they are accessing a get_attribute function and a set_attribute function. This allows you to control what happens when the user accesses and set an attribute (including raising an error), without requiring the user to type pesky method calls like "my_object.set_attribute_1(new_value)".

Raymond Hettinger, one of the developers at Python, had a talk about basic Pythonic ways of creating and using a class, including topics on variable privacy and property discussed above. http://pyvideo.org/video/1779/pythons-class-development-toolkit