Novel Implementations of Queue and Deque

25 Oct 2013

Baseless Number System

03 Jul 2013

Memory Leak Detection using ltrace

17 Mar 2013

Type Safety of Arrays in Java and Scala

16 Mar 2013

Recursive Descent (RD) Parsing

15 Mar 2013

Cracking Simple Substitution Ciphers

27 Feb 2013

Shoemaker's Problem

24 Feb 2013

Encapsulation in Scala

08 Feb 2013

25 Oct 2013

This post introduces implementations of queue and deque data structures using dynamic arrays. Deque implementation is suitable as a default container to replace standard dynamic arrays as it has the advantage of having constant time complexity for front push/pop operations with little or no speed/locality overhead. This may especially be a game changer for dynamic languages such as python or ruby where people care less about the complexity and use lists/arrays for anything required.

Baseless Number System

03 Jul 2013

I had this idea of non-overflowing digits when I first saw pascal's triangle in primary school and last day it came to my mind again for no apparent reason. I tried to search this a little bit but couldn't find anything related partly because of the fact that 'baseless numbers' is usually used with the meaning 'fake numbers' or 'misleading numbers' and partly because it is probably a quite useless thing to have but anyhow here it goes.

Memory Leak Detection using ltrace

17 Mar 2013

I had known strace tool for a while which traces system calls during the execution of a user space program. Recently I have discovered its cousin ltrace which is the same thing for dynamic library routine calls. Among other things it also reports libc function calls which gave me the idea of doing memory leak detection.

Type Safety of Arrays in Java and Scala

16 Mar 2013

Maybe you heard people saying Java arrays are not type safe but what do they mean by that? I will give you an example and also talk about how Scala handles this situation.

Recursive Descent (RD) Parsing

15 Mar 2013

So you decided to implement your own parser instead of using tools like bison or ANTLR and someone told you to go after recursive descent parsers and yet you are here. I will try to share my own experience with recursive descent parsing and give two implementations of the same grammar that parses a subset of arithmetic expressions with no intention for a flame war. Personally I think Scala version is more concise and easy to write but somehow hides the underlying logic behind which may or may not be relevant whereas C family language implementation is probably be clear to those who do not even know about parsing but requires some extra typing to construct.

Cracking Simple Substitution Ciphers

27 Feb 2013

Ever since I realized google app engine supports python numpy library, I have been meaning to give it a try by implementing some of the interesting things we do in my university as an app. I could finally get my hands on it and implemented a Markov Chain Monte Carlo (MCMC) algorithm which emerged recently to solve simple substitution ciphers. In fact this was a homework for my Monte Carlo class offered by professor Taylan Cemgil but since I'm not actually registered to the class, I decided to implement it as an app instead. If you dig in the course page you may find a matlab version of the algorithm as well as a javascript demo.

Shoemaker's Problem

24 Feb 2013

Shoemaker has $N$ jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day. For each $i^{th}$ job, it is known the integer $T_i$ $(1 \leq T_i \leq 1000)$, the time in days it takes the shoemaker to finish the job. For each day of delay before starting to work for the $i^{th}$ job, shoemaker must pay a fine of $S_i$ $(1 \leq S_i \leq 10000)$ cents. Your task is to help the shoemaker, writing a program to find the sequence of jobs with minimal total fine.

Encapsulation in Scala

08 Feb 2013

One thing that has been bothering many for quite a while is the need to write getters and setters for each variable. The idea behind encapsulation and information hiding is that if you ever need to change the way a class works, you won't necessarily be breaking any code that is using that class. While it may be useful for large code bases, it is usually an overkill for small applications as changes are quite rare and easy to handle.