Umair’s blog

Thoughts about programming and technology

A Reboot

I started blogging occassionally a few years ago, and my first blog was on Wordpress.com. However, for various reasons (life changes, scheduling, focus on work etc.) I pretty much stopped blogging. The oldest post on my Wordpress blog is from July 2012. Wow! Even I am surprised at how long it has been since I added anything new.

Back to 2015. I’ve been thinking about rebooting my blog for several weeks, and finally decided to take the first step. I hope to blog more frequently than I’ve done in the past few years.

For setup, I decided to generate my blog via Octopress and host it on GitHub Pages. I really like Octopress’s simplicity, look and feel, and control over various aspects of blog generation and hosting. Another advantage is that I do most of my writing in Markdown format, which is the default for Octopress. Lastly, Octopress generates my blog as static HTML.

My next steps are to figure out what to do about my old Wordpress posts. I needed to decide whether I am going to import them here, link to them instead of importing, or simply ignore.

A Quine in Objective-C

A quine is a program that takes no input and outputs its own source code. It has been a while since I last wrote a quine, so I figured I’ll write one in Objective-C. In general, quines follow a fairly simple formula. The program contains a string that includes all the code before the string and all the code after the string. Depending on the programming language, the string might also contain format string (for languages that use format-strings to print to stdout)

Finding the Start of a Loop in a Circular Linked List

A lot of people are familiar with the problem of detecting a loop in a linked list. The problem goes as follows: “Given a linked list, what is the algorithm to determine if it has any cycles (loops)?”

The algorithm is pretty straightforward:

  1. We start at the beginning of the linked list with two pointers.
  2. The first pointer is incremented through each node of the list. The second pointer moves twice as fast, and skips every other node.
  3. If the linked list contains a loop, these two pointers will eventually meet at the same node, thus indicating that the linked list contains a loop.

The algorithm is straightforward and it is relatively easy to create a mental model and get an intuitive sense of why it works.

Now, a slight twist to the same question asks: “Given a circular linked list, what is the algorithm to find the first node of the loop.”

Stern-Brocot Tree

Stern-Brocot tree is a tree data structure whose vertices correspond to the set of non-negative rational numbers. Thus, this tree provides a very elegant way for constructing the set of fractions m/n, where m and n are relatively prime. To construct the tree, the basic idea is to start with two fractions (0/1, 1/0) and then repeat the following operation:

Insert (m+m’)/(n+n’) between two adjacent fractions m/n and m’/n’

Manual Memory Management in Objective-C

Objective-C on iOS has no garbage collector, so it is up to the programmer to make sure that memory is properly freed once an object is no longer needed. On the other hand, Objective-C on the Mac does have a garbage collector (in Objective C 2.0). This blog post focuses on how to manage memory in the absence of a garbage collector.