Posts

  • Two's complement arithmetic is magic

    Recently I revisited two’s complement arithmetic. It’s one of the coolest tricks I’ve seen.

    ...
  • 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.

    ...
  • 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.

    ...
  • 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.

    ...
  • 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.

    ...
  • 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:

    ...
  • 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.

    ...
  • Why I believe P ≠ NP

    The HAMCYCLE problem

    ...
  • 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.

    ...
  • 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.

    ...
  • Spawn, log, reap children with IPC::Run

    In testing my implementation of a distributed failure detector, I needed to be able to:

    ...
  • 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.

    ...
  • 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:

    ...
  • 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.

    ...
  • 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.

    ...
  • 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

    ...
  • 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.

    ...
  • 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

    ...
  • 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:

    ...
  • 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.

    ...
  • 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>
    
    ...
  • 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.

    ...
  • 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,

    ...
  • 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))))))
    
    ...
  • 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$.

    ...
  • 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

    ...
  • 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:

    ...
  • 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}$?

    ...
  • SICP Exercise 1.13

    The Fibonacci sequence is given by,

    ...
  • 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.

    ...
  • 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:

    ...
  • 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.

    ...
  • 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.

    ...
  • 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.

    ...
  • 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.

    ...
  • A Python stack for scientific computing

    This post shows how to install the important packages for scientific computing in Python in a virtual environment.

    ...
  • 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.

    ...
  • 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

    ...
  • 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.

    ...
  • 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).

    ...

subscribe via RSS