Posts

  • LRU cache

    Another interesting algorithm I ran into recently is for a Least Recently Used (LRU) cache. Imagine a caching system that stores key-value pairs. And you have room for only a limited number of key-value pairs. So, when the capacity is exceeded, we need to remove the least recently used (used means accessed) key-value pair. This can be simply implemented using a linked list to keep track of which key was accessed least recently. Whenever a key is read / written, we can just move the corresponding linked list node to the head of the list. And when the capacity is exceeded, simply delete the last key in the linked list and remove that key-value pair from the hash table. Hash table look up is O(1). So is removing a node and adding it to the head of the list. But, what about figuring out where the key is in the linked list itself so we can move it?

  • Word Break

    I recently ran into this interesting problem called “Word Break” - quite a popular interview question. If you want to practice solving this problem, head over to leetcode. First variant of this problem is quite simple. Given a string, check if it can be split into words to form a full sentence. You are also given a dictionary to check if the word is valid or not. For example, given a string “thisisatest” and a dictionary (list of words) - “this”, “is”, “a”, “test”, your function should return true. For the same dictionary, “thisisnotatest” should return false.

  • Optimized Integer Programming

    For one of my side projects, I had to solve an Integer Programming problem. I was initially contemplating on using some existing MATLAB/Octave package to the job. The first option that was available was the Genetic Algorithm module in MATLAB. It turned out to be too random and not methodical at all. This is not surprising as genetic algorithm is in essence a random algorithm and does not suit all kinds of problems. It could work for some problems. Next option was Simulated Annealing. Even for this, there was a package in MATLAB. It worked ok but the convergence was too slow for my needs. So, I ended up writing my own custom gradient descent algorithm to solve this problem using Python. In this article, I am going the detail the algorithm and the design choices.

  • Neural Network Implementation of an XOR gate

    I have been meaning to refresh my memory about neural networks. As any beginner would do, I started with the XOR problem. In fact, this was the first neural network problem I solved when I was in grad school.

  • Binary Search

    Binary Search is probably one of the first algorithms Computer Science students learn. It is quite simple to implement but you are likely to run into a couple of corner case scenarios. As codekata puts it, practicing it over and over helps. Not just praciticing writing the same code, but trying to achieve the same results through different implementations. A note on choice of language: I chose Python for its simplicity of accessing and slicing lists.

  • Logistic Regression Theory

    Several years ago, I took multiple Machine Learning related courses on Coursera. And I did a quite a few projects on those courses. I don’t really have the results or the code documented anywhere. So, I am starting a small Machine Learning series to help me also recollect all those projects. One of the first projects we did on the Coursera ML course is Digit Recognition. There is a well known digit dataset called MNIST. For the course though, we used a small subset of the dataset. We have a set of scanned images which contain numbers and we have to design a model to correctly classify them. Before we look into the full classification, it makes sense to start with something simpler. How about just classifying the 0s and the 1s?

  • Setting up your own site with Flask

    If you want to host your own blog with minimal setup time, you could use something like tumblr or wordpress. But, if you are like me, you would want to code everything up yourself. Flask is a very lightweight Python based framework which supports templating, database support etc., Flask provides some excellent documentation on how to set it up to write your own blog system. But, I ran into a few snags. So, I thought of sharing some of the gotchas.

  • Practical Queues

    Queue is one of the simplest data structures around. Understanding queues is very simple if you just use a primitive data type like say integer. In fact, most tutorials leave you with just that implementation. Here, I am going to start with that implementation but will eventually expand it to work with any datatype you want.

  • Learn to love the heap

    I have never used the heap datastructure in my life till recently. I didn’t think it was that useful. But, after using it to solve this order statistics problem, I am in total love with this datastructure. My first theoretical exposure to heap came when I took the Algorithms course by Robert Sedgewick. This is a great course. You can pretty much find all the videos for the course on Youtube.

  • Ecobee Experiments

    I got a free ecobee thermostat from my utility company. It was a big step forward from my older analog Honeywell thermostat. For one I could use an iPhone app to control the thermostat. Their App is great and all. But, I need to click through 5 different buttons to turn off my thermostat. I got lazy and so I got inspired. I went and looked into their developer API which turned out to be a pretty good reference. Best place to start is their examples page.

  • Little Javascript tricks for your chrome extension

    While developing my chrome plugin Shut up and cast, I learned a lot of tricks in Javascript. I shared one of them in them in the last post. In this post, I am planning to share a few small tricks.

  • The Old Switcheroo

    I recently learned (the hard way, as usual) something about the Switch statement in C. I had a part of code which I want executed for all the cases in the switch statement. So I naively put that statement just above the first case statement inside the switch structure.

  • Sending data to your site from your Chrome Extension

    How to open a new tab with a specific address from your Chrome extension is well documented in Google’s help articles. For completeness sake, let us start with discussing this. Before we create a new tab, we should add permissions for accessing “chrome.tabs” in your manifest.json.

  • Design of Antenna Arrays using Windows

    When I was in grad school, I wrote a paper on how to design Antenna Arrays using Window functions. I uploaded it to Academia.edu and forgot all about it. Once in a while I get an email from Academia.edu that someone searched for me. I got intrigued today and did a google search for “Antenna Arrays Windows” and was surprised to note that my paper is the second best match :stuck_out_tongue:. Here is my shameless blog article to get that traffic to come to my site instead. If you prefer a PDF version of the paper, you can find it here.

  • Announcing shut up and cast

    Thanks for the 4000 odd users of my previous chrome plugin Stream to XBMC, I have decided to extend the plugin’s capability to be used with the most popular casting device and the one which started it all, Chromecast. If you have a Chromecast and want to watch videos from sites for which there is no Chromecast app, you have come to the right place.

  • How scripting languages spoil you

    I love Python. But, I have to admit that it spoils you. I just spent 20 minutes trying to code up a simple program to do linear regression. This problem looks deceptively simple. In fact, it is deceptively simple, on paper.

  • HOWTO: Using Openssl C library

    For one of the Matasano crypto challenges, I had to decrypt the text which was encrypted using AES in ECB mode. Everything about AES is actually documented by the National Institute of Standards and Technology. You can get all the algorithms behind AES encryption. It is probably not a good idea to implement it from scratch. Openssl has a well tested and widely used library which works.

  • Ultimate guide to pointers

    Pointers in C are one of the most confusing concepts. I am going to document how pointers work in the order of increasing complexity.

  • Hex to base64 conversion

    I came across another set of online coding challenges called The Matasano Crypto Challenges. From a quick google search, it seems like lots of people have tried and recommended it. I got intrigued and started coding right away. To keep the blog rolling, I will share my experience with these coding challenges.

  • Sudokids

    Sudokids as the name so obviously states is Sudoku for kids. Motivation behind Sudokids is to teach kids set theory with the help of Sudoku.

  • Stream to XBMC FAQ

    As a follow up to my previous post about my plugin Stream to XBMC, here are some frequently asked questions about how to setup the plugin. Just two for now, more to follow.

  • Stream to XBMC

    This is a chrome-plugin to push videos to an XBMC setup. It can be used it with Raspberry Pi or any other XBMC setup to watch videos from CBS, Youtube and so many other sites on your TV. Big bang theory anyone?

  • Upstream linux kernel on a Raspberry Pi

    Recently, I signed up for the Eudyptula Challenge. If you have not heard of it, it is a series of programming exercises designed to train you with Linux Kernel Development process. One of the tasks is to install the latest linux kernel on your machine. You have an option of doing it in a Virtual box setting. Hey, but where is the fun in doing that? I had a Raspberry Pi handy and found a couple of good Wiki pages on how to compile your own kernel for Raspberry Pi (here and here). These two pages have the all the info needed but it is kind of scattered. Fastest way to compile the kernel is to do in in Ubuntu (You could technically do it on a MAC, but it is slightly more involved). I tried on my MAC first but ended up installing Ubuntu through Virtualbox to do the compilation. Here are the steps:

  • Welcome to my blog!

    As part of my learn something new everyday, I am migrating all my ramblings to a Jekyll-based blog. It is simple, easy to maintain and super customizable. With this change, I am hoping to write more often.

subscribe via RSS