Posts

Jul 5, 2020 Two's complement arithmetic is magic
Recently I revisited two’s complement arithmetic. It’s one of the coolest tricks I’ve seen.
...
Mar 21, 2020 I am very fortunate
The COVID-19 situation is the first such in my life. It has affected me and my family in various ways, but boy am I lucky.
...
Feb 8, 2020 Starting Tabla
When I moved to Zürich last year, I was drawn to percussion in general. I played around with a drum-kit, and I loved it. The coordination required to keep time and play the right notes takes my mind somewhere else. I get to focus only on the current moment, because if I don’t, I’m going to miss the next beat.
...
Jan 4, 2020 My first Chaos Communication Congress, 36c3
The 36th Chaos Communication Congress took place in Leipzig from 26-30 December, 2019. I’d always wanted to be part of the congress, but it is quite difficult to score a ticket if you’re not part of a hackerspace. Last year though, I was determined, and managed to get a ticket to 36c3 during the second presale.
...
Jan 12, 2019 Embrace the borrow checker
The borrow checker is arguably one of the biggest sources of frustration when learning Rust. Once the Rust compiler is satisfied with the syntax, it gets down to the real stuff: proving that your program is free from data races caused by aliasing of memory.
...
Jan 12, 2019 Tagging functions with attributes in Perl
Suppose we have a Perl module that allows us to query a set of business objects (for example, purchases made on our website). The API of the module looks something like:
...
Dec 16, 2018 Extended File Attributes on Linux
Files already have a lot of user accessible metadata associated with them – the last time of modification, access control bits, etc.
...
Sep 2, 2018 Why I believe P ≠ NP
The HAMCYCLE problem
...
Jun 24, 2018 Creating lock-files in Unix
Lockfiles are commonly used for process level mutal exclusion. For example, a cronjob processing hourly logs can hold a lock so in the event it ends up taking more time than an hour, the next hourly job does not clobber the working directory. Databases like Postgres also use lockfiles in their data directories to ensure at most one serving process is handling the data.
...
Jan 28, 2018 Summary of "ImageNet Classification with Deep Convolutional Neural Networks"
I decided to read interesting deep learning papers often and try to summarize them to aid my own understanding of the topics.
...
Jan 16, 2018 Spawn, log, reap children with IPC::Run
In testing my implementation of a distributed failure detector, I needed to be able to:
...
Oct 19, 2017 The bakery algorithm for mutual exclusion
The bakery algorithm was proposed by Leslie Lamport as a solution to Dijkstra’s concurrent programming problem. In the problem, Dijkstra had first identified the need for mutual exclusion among a group of concurrently executing processes.
...
Sep 16, 2017 Optimal failure detector performance
This is a note to self on computing the lower bound on number of messages each process in a distributed failure detector must send to guarantee adherence to pre-specified values for:
...
Sep 10, 2017 Analysis of gossip based dissemination
Gossip based protocols are widely used in distributed systems for robust dissemination of information. The problem: spreading a message among a set of processes. For example, in the Bitcoin P2P network, whenever a new transaction happens, it needs to be broadcast to all peers in order for it to end up on the blockchain. Typically, such information originates at one of the nodes in the network, and needs to be communicated to the rest of the peers.
...
Sep 8, 2017 A simple backup setup using rsync
Suppose we have a bunch of files we’d like to have backed up on a remote host periodically. In this post, I’ll describe my setup that uses rsync with cron.
...
Aug 12, 2017 Cryptographic hash functions
Hashing is commonly used when we want to reduce a message of an arbitrary size to a fixed length “digest”, for purposes ranging from integrity checking of files downloaded from the internet to building blocks for cryptocurrencies. There are many functions one can use to map the input message to its hash. The only requirement is that the output be of a known, fixed size. For example, consider the function
...
Jul 30, 2017 Doing numbers without the numbers
Numbers are abstractions invented by humans to aid with various activities, mainly counting, and sometimes recreation. While the “three” might be the number of coins in my pocket right now, the number “three” is in itself an abstract entity, worthy of study in its own right. It is defined as the successor to the integer “two”. It is, in general, really hard to define what data is. According to one definition, we define data in terms of operations possible on it, and certain constraints on these operations, like an axiomatic system. Note that under this scheme, the actual representation of the data object in question is irrelevant: only the external operations on it and a set of properties obeyed by those operations is enough.
...
Jul 8, 2017 SICP exercises 1.37-39
In these exercises, we deal with continued fractions. These are remarkable ways of writing rational and irrational numbers as a sum of an integer and another number, which is itself recursively written as a continued fraction. For instance, $\sqrt{19}$ can be represented as
...
Jul 1, 2017 Killing a process group with a timeout in bash
On Linux, most programs that daemonize write their process number to a file, which can be used to send signals to the daemon. To automate deployment (in case you already do not have upstart or systemd integration with the program in question), here’s one approach to stop a daemon with potentially many child processes:
...
Nov 6, 2016 Writing video captured using OpenCV to a file
This approach requires ffmpeg (forked to avconv on Debian), and is not really limited to OpenCV. If you can write raw video frames to stdout, you can use this method. OpenCV video frames are represented as numpy arrays in Python, and the .tostring() method will give the raw frame data that can be piped to ffmpeg. Here is a small program that captures the first video stream and pipes it to ffmpeg to make a video output file called ouput.avi.
...
Sep 5, 2016 Baby steps with Elixir -- Wordcount
Implementing (useful subsets of) basic Unix utilities is a great way to learn a programming language. On my quest to read a file one line at a time in Elixir, I decided to try implementing wc. The interface:
```
$ elixir wc.exs <filename>
 <line-count> <word-count> <char-count> <filename>
```
...
May 22, 2015 Deriving the laws of reflection and refraction of light from Fermat's principle
Fermat’s principle of least time can be roughly stated as, “The path taken between two points by a ray of light is the path that can be traversed in the least time” (From Wikipedia). Fermat used this observation to derive the laws of reflection and refraction of light.
...
May 19, 2015 SICP Exercise 1.20 - GCD
Euclid’s algorithm for computing the GCD (Greatest Common Divisor) of two numbers is based on a very neat idea: The GCD of two numbers $a$ and $b$, with $a \gt b$ is the same as the GCD of $a-b$ and $b$. A little thought would convince us that this means the GCD of $a$ and $b$ is then equal to the GCD of $remainder \left( a, b \right)$ and $b$, which in turn is equal to the GCD of $b$ and $remainder \left( b, remainder \left( a, b \right) \right)$ and so on. In Scheme code,
...
Apr 25, 2015 SICP excercises 1.17 and 1.18 - Multiplication using addition, doubling and halving
These two exercises ask us to implement a multiplication routine assuming we can only add, double, and halve even numbers. The first implementation is a straightforward translation of the facts that the product of two numbers $a$ and $b$ is given by $ab = 2 \left( a \times \frac {b} { 2} \right) $ for even values of $b$ and $ab = a(b-1) + a$ for odd values of $b$. Here is the code:
```
(define (fast* a b)
  (cond ((= b 1) a)
        ((even? b) (double (fast* a (halve b))))
        (else (+ a (fast* a (- b 1))))))
```
...
Apr 25, 2015 SICP excercises 1.19 - Logarithmic time Fibonacci number generation
This exercise describes a transformation $T_{pq}$, that, when applied to a pair $\left( a, b \right)$, transforms it according to $a \gets aq + bq + ap$ and $b \gets bp + aq$. The transformation used to generate Fibonacci numbers, starting from the pair $\left( 0, 1 \right)$, can be written as $a \gets a + b$ and $b \gets a$.
...
Apr 22, 2015 SICP Exercise 1.15
Exercise 1.15 in SICP requires us to find the order of growth in time and space of a procedure that approximates the value of $ \sin x $ by noting that $\sin \left(x\right) \approx x$ when $x$ is sufficiently small. For larger values of $x$, $ \sin x $ can be recursively calculated using the trigonometric identity
...
Apr 22, 2015 SICP Exercise 1.16
This exercise requires the design of a procedure that evolves an iterative exponentiation process using successive squaring. It should use constant space and a logarithmic number of steps. The hint is to note that $\left( b^{ \frac{n}{2} } \right)^2 = \left( b^2 \right)^{ \frac {n}{2} }$ and to transform states such that $ab^n$ is invariant, and equal to $b^n$ where a is another state variable along with the base b and exponent n. Here is the implementation:
...
Apr 12, 2015 SICP Exercise 1.14
Given a set of coin denominations $\mathbb{C}$ of size $n$, in how many ways can an amount $A$ be changed using the coin denominations in $\mathbb{C}$?
...
Apr 5, 2015 SICP Exercise 1.13
The Fibonacci sequence is given by,
...
Nov 2, 2014 Setting up OpenCV for Android without an IDE
Getting OpenCV running on Android without an IDE like Android Studion or Eclipse is actually very simple. It is just underdocumented. So here it is.
...
Dec 1, 2013 Why IF has to be a special form in Lisp
In both Scheme and Common Lisp, the IF conditional is a special form with a simple evaluation rule:
...
May 11, 2013 Exposing C++ OpenCV code to Python using Boost
Both C++ and Python are excellent languages that complement each other in many ways. I have been working on Computer Vision and Document Analysis problem and I have had the need of offloading some performance critical code to C++ and expose it neatly to the other pieces, which in turn are in Python.
...
Apr 21, 2013 Reversing a list in functional style
Suppose we have a list implementation in which every element (or node) in the list contains a head, which is the item at this node and a tail, which is rest of the list. I’ve used Scala here, but most of the code looks almost like pseudocode.
...
Mar 27, 2013 Variables in Common Lisp
Common Lisp is a dynamically, but strongly typed language. The variables carry the type information that can be fetched at runtime, and hence, the type errors are detected dynamically. In this way, it is most similar to Python, which, too, is a dynamically but strongly typed language.
...
Jan 20, 2013 Common Lisp Collections
Even though Lisp lists are remarkably powerful and flexible, they are not the only data-structure available in Common Lisp. Among the most useful other data structures are arrays and hash tables.
...
Dec 8, 2012 A Python stack for scientific computing
This post shows how to install the important packages for scientific computing in Python in a virtual environment.
...
Nov 25, 2012 The Tanimoto coefficient
There exist a number of metrics to measure similarity between two items, like the Euclidean distance metric, the Pearson correlation coefficient and the Tanimoto score, and its special case, the Jaccard coefficient/index.
...
Oct 27, 2012 Calculating C(n,r) efficiently
The number of ways of choosing $r$ items from a collection of $n$ identical items is referred to as $C(n,r)$, ${}^{n}C_{r}$ or $ n \choose r $ and is a fundamental counting operation. $ n \choose r $ is given by
...
Oct 2, 2012 Decorators with optional arguments in Python
Python decorators are one of the best features of the language, and I think that this SO answer describes them the best. I’ll take an example similar to the example from that question itself. We want to write a decorator that, when used to decorate a function that returns a string, will wrap that string with the HTML bold tags.
...
May 11, 2012 Configuring an HTTPS site with Django on Nginx + Gunicorn
I have deployed quite a few Django powered sites on PaaS like OpenShift, Google AppEngine. But I was required to deploy my final semester project on our college server, which turned out to be really difficult After a lot of work, I finally was able to deploy Django on Nginx and Gunicorn over HTTPS (my site uses HTTPS throughout).
...

Posts

The HAMCYCLE problem