Memoization in C++

Many problems lend themselves well to recursive solutions; we express a big problem in terms of a similar problem that is 'smaller' in size, for which we call our same function to solve it, until we get to a problem that is small enough that we know how to solve it (we tend to call the known one the base cases).

 The classical example of a recursive function is the factorial function; we know that the factorial of 0 is 1, and we can define the factorial of an integer, say n, greater than one, as the number, n times the factorial of n-1, with the obvious c++ implementation as follows:
Another of the classical problems is generating a number in the Fibonacci sequence; this sequence is like: 0,1,1,2,3,5,8,13 ... where we start with 0 and 1, and then each number is the sum of the two previous ones; we want to write a function, let's call it fibo, that, given the place or index in the sequence would return the number, so fibo(0) would yield 0, fibo(2) would yield 1, fibo(7) 13 and so on. We could define this function as follows:
Many times, we end up solving the same sub-problem more than once, which can heavily decrease performance; for example, in the function above, we would end up solving fibo(n-2) 2 times, fibo(n-3) 4 times and so on, exponentially; one easy way we can solve this is to keep track of the values we've already calculated, and just calculate a new value if it's not in this cache; an easy way to store the values is in a map (in this case, since we're talking about unsigned ints, we could use a vector, but a map works in the general case). The code would look like:
This code is, in practice, much much faster than the other one (goes from exponential, to n*log(n) ). This general technique of storing already-calculated values for a function in a cache is called memoization.
We can generalize this pattern, and create a generic memoizer function, called memoize. Since we don't know the type of the input or output values, we need a templatized function, with two type parameters, as follows:
To use it, we would need to define our function with a lambda:
And in other place, replace the variable with its memoized variation:
Of course, this would only work for functions that take only one argument, but it would not be hard to do it for other kinds of functions, although the pattern is more important than the particular functions :).
Many would realize that there's a better iterative algorithm for Fibonacci numbers; problems where memoizing helps can be solved with dynamic programming iterative algorithms, but, in general need a better understanding of the algorithm; when faced with a new problem, we can usually start with a recursive solution, memoize if we have performance problems and we suspect or know we're solving the same subproblems repeatedly, and move to dynamic programming only if we cannot achieve good performance with memoization.

iOS first App: Temperature Conversion

Apple's first app tutorial is excellent, but many times having more examples help, so here's my simple first app tutorial, a very simple temperature conversion application; It has one input, a text field for entering a temperature in Fahrenheit degrees, and a button, that will convert it to celsius and display it. Check the short demo video below.

If you prefer videos, here's a video walkthrough; if not, follow allong.

First, we create a new project, single-view application;let's call it Temperature Conversion

Then fill out the other project options as below (make sure you select use storyboard and use reference counting, and use Temp as class prefix, to make the class names the same as in this walkthrough; select iphone for device, to simplify; put whatever you prefer for the other values).

After you choose where to save your project, you should see the full xcode workspace, similar to the screenshot below (which has extra annotations :). Notice the list (or hierarchy) of files is to the left, in the middle there's an editor, wich changes depending on the file selected, and on the right there's a secondary editor, plus the object library at the bottom.

First, select the TempViewController.h file and modify the code so it looks like the screenshot below (the actual code is below the screenshot)

Then, select the storyboard, and, from the object library (bottom right, notice this is a list, and you can scroll) drag a text field,  a label and a button onto the storyboard.

Now, ctrl-click on the text field, to get its menu, and drag from the new referencing outlet to the Temp View Controller, and select fahrenheit, the only option (a line will appear when you drag, but doesn't appear in the screenshot)

Now do the same with the label

And finally join the touch up inside event in the button with the convertToCelsius method in the controller

And now we go to the TempViewController.m file to add the actual code; for easier understanding (not terribly useful now, but useful in larger programs), we first create a method for converting from fahrenheit to celsius, which I'm calling faren2celsius
And then the actual code for handling the button press; we access our properties with dot notation and using self to refer to ourselves, so self.fahrenheit is the text field, and self.celsius is the label; they both have a text property, of type NSString, and the NSString class has an intValue method that parses a string into an int.

Now press command-R or click on the run button, and you get your first iPhone app !

Finishing touches

1. Go back to the storyboard, and add a couple of labels that say Fahrenheit and Celsius, next to each field.
2. Change the title of the button to Convert to Celsius
3. Change the text inside the label so it is blank, instead of saying 'label'.

Extending the program

1. Change the declaration of celsius in TempViewController.h to be a textfield, and, on the storyboard, delete the label, and another textfield and link it to the view controller.
2. Add another method in TempViewController.m (and declare it in TempViewController.m), called convertToFarenheit, that will convert from celsius (which is now a textfield) and put it into the fahrenheit field.
3. Add another button to the storyboard, and link it to this method.
4. Verify that you can convert back and forth between fahrenheit and celsius.

Simple animations in iOS

I'm re-learning objective-C and iOS programming, since I will be teaching a class this semester; I have created a simple animation example that might be useful to other people learning iOS.

There are basically two kinds of animation:

1. cell-based animation, in which we replace an image with another image, like old cartoons were made, or like flip books; this gives us complete control of the animation, but requires us to draw each frame.
2. property-based animation, in which we animate some properties of an object (like its location, its size etc), this is usually limited, in which we are animating the whole object, but it is a lot easier, since we do not need to draw each frame, but just need to specify the initial and final values for the properties.

We can create a very simple program to demonstrate both kinds; we will have a storyboard, with an UIImageView and two buttons, one to trigger each kind of animation. The video below shows the screen, and has a small demo.

We create a new project, single-view application, and then edit its storyboard (I do iPhone only for my simple projects :), add a UIImageView and two buttons; on its view controller, we add two properties (only one IBOutlet) and two IBAction methods, one for each button, as follows:

For the cell animation, I got a character sheet from OpenClipart, and cut it into a set of images (the images are not quite properly aligned, but they definitely exceed my artistic abilities :). You can get the images (and the whole project) from my github.

Notice we have an NSArray property for keeping the images for the cell animation, but it is not directly  hooked to the UI.

After we attach the ImageView (as a reference outlet) to the imgView property, and hook up the buttons to the corresponding methods, we go into the code.

In our viewDidLoad method we initialize the array of images:

And our method for cell animation is pretty simple; all we really need to do is set the animationImages property of the UIImageView, to an array of images, and then call startAnimating on the ImageView; we can also control the duration (in seconds), and how many times we want the animation repeated. The whole method is below:

Now, for the property animation, we need to choose a property which is animatable (from the documentation,  we can animate the frame, bounds, center, transform, alpha, backgroundColor and contentStretch properties). The frame property determines (along with some of the others :) where the UIImageView is drawn, so we create a new frame (you need to animate the whole property, can't animate pieces), and use UIView's animateWithDuration method (available since iOS 4); we need to pass it a block (using the ^ { ...} notation; anything between the braces {} is a block). There are several variations of this method, which allow you to control more of the animation). The code is as follows:

If you want to learn more about animations in iOS, Ray Wenderlich has a deeper tutorial,  Apple has all the documentation you'll ever need, and playing with the methods should be easy and fun.

Data Science Resources

I will be collecting resources here about big data, data warehousing, data mining and such. Just my personal list.

• Mining of massive datasets
• Greenplum's Data Science Summit (not great, just intro?)
• MongoDB in action
• Taxonomy of Data Science - decent blog post from dataists
• http://datasciencelondon.org/

Papers

• Mapreduce paper
• http://atbrox.com/2010/05/08/mapreduce-hadoop-algorithms-in-academic-papers-may-2010-update/
• http://en.wikipedia.org/wiki/Apache_Hadoop#Papers
• http://lemire.me/OLAP/
• www.indiana.edu/~cheminfo/I533/datacube.pdf
• 
  

Getting Started with Hadoop on Ubuntu

So, I'm trying to play with hadoop again (haven't done it in a while), and since ubuntu is my current weapon of choice, I found a great tutorial at http://www.michael-noll.com/tutorials/running-hadoop-on-ubuntu-linux-single-node-cluster/ ,but I wanted something even simpler, like a script, plus a sample program and instructions on how to compile and run it, so I created it (at the very bottom are the differences with Noll's tutorial). It is available at: https://github.com/okaram/scripts/blob/master/hadoop/install.sh .

You just need to download it and change it so it can be executable: You probably want to look at it in your favorite editor (it is not a good idea to just run a script from the internet; I trust myself, but you shouldn't trust me), and you may want to change the mirror while you're at it (I live in Atlanta, so I use Georgia Tech's). After you're happy, run it as root: And you should be done with the installation ! the script creates a user for hadoop, called hduser; you can change to it, by typing: Then, as that user, you want to setup your path and classpath (the classpath is needed for compiling): And start hadoop: Now download my sample program (it is the standard WordCount example, from the tutorial, but without the package statement, so you can compile it directly from that folder), compile it and create a jar file: Now, we need to put some data into hadoop; first we create a folder and copy a file into it (our same WordCount.java, since we just need a text file): And we copy that folder into hadoop (and list it, to verify it's there): And now we can run our program in hadoop: When you want to stop hadoop, just run the stop-all.sh command; also, if you want to copy the output to your file system, just use the -copyToLocal option of hadoop's dfs.
The install script is completely automated, so you can even use it to start an amazon ec2 instance with it; for example, use: to start a micro instance, with a ubuntu 12.04 daily build (for Dec-1-2012; change the ami id to get a different one :), and a key named mac-vm.

Using LinQ in C#

LINQ is actually a pretty cool technology; it allows you to do something like list or monad comprehensions over collections, but with a sql-like syntax; better yet, it does magic so you can use SQL tables instead of collections, and it actually generates and sends the SQL to the DBMS, instead of getting all the data into memory and iterating over it.
Since I switch languages constantly, I'm always trying to remember the right syntax; so, this is my place to have it, for now. Before you can connect to your DB, you need to run a VS tool, that will generate the LINQ for your particular schema (and you need to rerun every time you change :( . In my case, the generated code is in the SimpleBlog package, and the generated class is SimpleBlogDataContext; so my code for reading something looks like:
And to add an element to the blog table, we can do:

Notice that the context (ctx here) needs to be a global variable; having several contexts will diminish performance and probably confuse you, since variables from one context cannot be saved in another.

We always need to import the System.Linq namespace when using linq; If we're doing this directly in an aspx page we use an import directive, like: Notice that you need to add an assembly reference (at least in VS2008, you need to add it to the web.config file, even if you add it to the project references in solution explorer), so add the following line to your web.config, inside the <assemblies> tag:  <add assembly="System.Data.Linq, Version=3.5.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089" />

A simple blogroll with python and feedparser

A friend wanted to use a blog as a sort of database, allowing several people to create posts on the same blog, and then transform the posts into some sort of listing; most blogging software will let you export a list of posts as an rss feed, so this seemed like a good time to go learn how to parse and use rss.

While I'll let my friend figure out his own application, this prompted me to write a simple 'blogroll' program, that would read several rss (and atom) feeds and would produce html showing the appropriate titles and links.

Since python is my scripting language of choice for now, I googled rss parser libraries, and found feedparser.

We can call feedparser.parse, and give it a url; it will then return an object representing the feed; the object contains a field called feed, which contains information about the feed, like its title and its link (url); the object also contains entries, which is a list of objects, each representing one entry in the rss feed; for each entry, you have fields like its title and its link.

So, it is just a matter of iterating over a list of urls, parsing the feed for each, and going over its entries, producing html as we go, writing everything to a file. The final code looks like: