Email and Spam Filtering

Have you ever signed up for an online service and suddenly started experiencing a surge of spammy marketing emails? The kinds of emails that are sent directly to you as part of a “customer retention” program after you buy an item like airline tickets, the ones that keep sending you emails about limited-time offers and credit card deals long after your purchase is complete?  Here I’ll discuss some strategies to deal with under-the-radar spam.
Continue reading

Simulating Low Disk Space in iPhone Simulator

While testing my iPhone application, I realized there is no way to test out my worst-case scenario, when there is no disk space. How do we do that? This StackOverflow post lays it out conceptually:

I bet you could also create your own .dmg file with file system of size … say 2Mb and write to it. If this works, then it is super-easy for testing – you just mount it and switch the path for testing. If the dmg is small enough, you could probably even upload it to the source control.

Let’s do this “in practice”.

Continue reading

ASIHTTPRequest vs. NSURLRequest

Support for one of my favorite libraries, ASIHTTPRequest, has been discontinued. I have been slowly but surely making a transition from ASIHTTPRequest (back) to NSURLRequest in some of my projects. I picked ASIHTTPRequest over NSURLRequest because NSURLRequest is verbose. Extremely verbose. ASI also has queueing control, throttling control and much, much more. These are are just some of the things that made ASIHTTPRequest such a pleasure to work with. Alas, I am stuck with NSURLRequest again…

Anyway, one of the more interesting aspects of connection handling is session control. I rely on the backend server to set a session cookie when I log in, and to keep that cookie alive while I do other stuff in the program. But in particular, when I transitioned the login screen to NSURLRequest, I noticed that, despite logging in successfully, my program would think that I’m NOT logged in, in the parts where ASIHTTPRequest is still used. It looks like ASIHTTPRequest is blind to the session cookies that are set using NSURLRequest.

I should also mention that I’m using CodeIgniter on the back end for session control, but in theory it shouldn’t matter (spoiler alert: but it does).

Let’s line up the usual suspects and try to figure out why this happens.

The Usual Suspects
Continue reading

MySQL Exclusive Row Relationships

This post will explore how to find exclusive row relationships — rows that may be grouped together by some non-unique id that identifies some kind of grouping of those rows. For example, let’s say that we are managing a team of players, and that each team has to be unique. In other words, players A and B form Team 1, but players A,B,C form Team 2. Searching for existing teams with players A and B should only return Team 1, searching for teams with players A,B,C should return only Team 2, and searching for B,C returns an empty set. How to do this in SQL?

Continue reading

Stack from Queues

Ran across a question on how to implement a stack by only using queues on SO, so I decided to give it a go in Java and PHP. It’s actually pretty straight forward:

  • Initialize two queues.
  • On every push operation, if both queues are empty, add to the first queue.
  • If one of the queues is full (one will always be empty), pop off all the elements from the full queue and add them to the empty queue in the same order (as they were popped). This guarantees the full queue will always be sorted like a stack, so when a pop occurs, it is popped in the “LIFO” order, not “FIFO” order.

Code after the break. Continue reading

Camera Controller Finished Box

Arduino Camera Controller

The Arduino Camera Controller project was my first Arduino project, one that sparked my interest in electronics. The objective of this project started by building a sensor-triggered camera controller, similar to the amazing Camera Axe. I followed that project for two years, and it is truly amazing what he/she was able to accomplish with it (as far as I can see, that project can now be considered a professional product). This was my starting inspiration; I wanted to build something that could activate my Canon Rebel XTi from a sensor, and also have the option to take a series of photos for use in a time lapse video. This writeup is how I got from zero knowledge of electronics and mechanical engineering to a (nearly) finished project.

Camera Controller Finished Box

Camera Controller Finished Box


Continue reading

Doubly Linked List in C

Revisiting some of my old Arduino projects over the weekend, I remembered that C is not my strong point (that was almost a pun… close call). Rather than run away from the mountain of ampersands and hail of asterisks that ensued, I decided to improve on my Canon Rebel remote control project (loosely inspired by the awesome Camera Axe) by redoing the menu system for the Arduino-controlled LCD.

I will do the project write-up at another time as this post is largely aimed at higher-level language people like myself who struggle with pointers and memory addressing. But the good news is that there are a lot of tutorials and examples online for linked lists and various data structures in C. Continue reading

Dijsktra (in Prague)

Piggybacking onto my previous post about graphs and DFS and BFS, you may have noticed there is also a weight assigned to each edge in a graph. This is because I will talk about path-finding algorithms, starting with Dijsktra’s Algorithm. There are plenty of resources online, such as Wikipedia’s Description that do a fairly good job of describing the algorithm.

However, none of them explain the algorithm in a real world scenario, so I decided to describe it using a city whose beauty was distracting to my path orientation, causing me to constantly get lost: Prague, Czech Republic.

Graph of Prague

A section of Prague with a graph overlay

If you were planning a trip in a few blocks of that intersection, and all you had was this map, how would you get from, for example, point P to point W? Intuitively, you would look at A and all edges connected to it (without using an illustrated map, i.e. from a table), pick the lowest one and repeat.

Here is a PDF of Dijsktra’s Algorithm in Action and an animated GIF.

Dijsktra Animation

Dijsktra Animation

And finally, the updated code in PHP.

Reversing a Linked List

Exploring and refreshing data structures and algorithms, you will inevitably find the question “how do you reverse a linked list?”. For this exercise, we assume a singly-linked list, with a head, and the last item pointing to null (as shown).

Linked List

Singly Linked List

The goal is to end up with the following linked list:

Reversed Linked List

Reversed Linked List

Continue reading

Breadth-First Search and Depth-First Search in Java

I decided to implement Breadth First Search and Depth First Search in Java. The implementation uses a Directed as the underlying abstract data type, keeps track of visited graph nodes by keeping a separate data structure, and implements BFS by using a Queue.

Some implementations only implement DFS and BFS on trees, but this implementation uses a graph because a tree is really a directed graph with no cycles (i.e. a node cannot reach itself in traversal). However, in the case of a graph, when a node can reach itself, you have to pay special attention to those loops by marking nodes as “visited” so that you don’t “visit” them again and end up in a stack overflow or an infinite loop. There is more than one way to do this: by keeping a separate data structure of the visited nodes (the way I did it) or by adding an extra field to each node, mark it as visited each time it is visited, and reset it once you are done with the search. Since both methods would take linear time but resetting the nodes’ visited flags would make coding more complicated, I chose to keep a separate data structure for that.

Source

UPDATE 2012/10/16: Graph in PHP. Interestingly, PHP arrays use hash maps as the underlying structure, so using key/value pairs might actually speed up the algorithm.