Coin change problem with change – Dijkstra’s Algorithm

The coin change problem is a well studied problem in Computer Science, and is a popular example given for teaching students Dynamic Programming. The problem is simple – given an amount and a set of coins, what is the minimum number of coins that can be used to pay that amount?

So, for example, if we have coins for 1,2,5,10,20,50,100 (like we do now in India), the easiest way to pay Rs. 11 is by using two coins – 10 and 1. If you have to pay Rs. 16, you can break it up as 10+5+1 and pay it using three coins.

The problem with the traditional formulation of the coin change problem is that it doesn’t involve “change” – the payer is not allowed to take back coins from the payee. So, for example, if you’ve to pay Rs. 99, you need to use 6 coins (50+20+20+5+2+2). On the other hand, if change is allowed, Rs. 99 can be paid using just 2 coins – pay Rs. 100 and get back Re. 1.

So how do you determine the way to pay using fewest coins when change is allowed? In other words, what happens to the coin change problems when negative coins can be used? (Paying 100 and getting back 1 is the same as paying 100 and (-1) ) .

Unfortunately, dynamic programming doesn’t work in this case, since we cannot process in a linear order. For example, the optimal way to pay 9 rupees when negatives are allowed is to break it up as (+10,-1), and calculating from 0 onwards (as we do in the DP) is not efficient.

For this reason, I’ve used an implementation of Dijkstra’s algorithm to determine the minimum number of coins to be used to pay any amount when cash back is allowed. Each amount is a node in the graph, with an edge between two amounts if the difference in amounts can be paid using a single coin. So there is an edge between 1 and 11 because the difference (10) can be paid using a single coin. Since cash back is allowed, the graph need not be directed.

So all we need to do to determine the way to pay each amount most optimally is to run Dijkstra’s algorithm starting from 0. The breadth first search has complexity $latex O(M^2 n)$ where M is the maximum amount we want to pay, while n is the number of coins.

I’ve implemented this algorithm using R, and the code can be found here. I’ve also used the algorithm to compute the number of coins to be used to pay all numbers between 1 and 10000 under different scenarios, and the results of that can be found here.

You can feel free to use this algorithm or code or results in any of your work, but make sure you provide appropriate credit!

PS: I’ve used “coin” here in a generic sense, in that it can mean “note” as well.

Explaining UPI

I just paid my cook his salary for November. Given the cash crunch, I paid him through a bank transfer, using IMPS. Earlier today, my wife had asked him for his account details (last month I’d paid him on his wife’s account).

An hour back he sent me his account details (including account number and IFSC) via WhatsApp. I had to wait till I got home and got access to my laptop (Citibank app doesn’t let you add payees on mobile banking).

I get home, log in to Citibank Online. Add payee, which includes typing his bank account number twice. Get SMS asking me to confirm payee addition. I authorise payee. And after all this I am able to finally do the transfer – and I expect him to have got his money already.

For a long time I was wondering what the big deal with UPI was, given that IMPS is already fast enough. Having finally tried UPI earlier this week (it’s finally coming to iOS, but only available on ICICI now. And the implementation so far sucks, since you need to pull out your debit card for two factor authentication – defeating the point of UPI. I’m told it’s better on Android), I realise how much easier and safer the transaction would’ve been.

Firstly, the cook needn’t have sent me his account number. All I would need was his virtual payment address. I would then open my UPI app (in my case, iMobile) and click on “send money”. And then I’d add his virtual ID there, following which his name would appear. Two or three more clicks, and entering my PIN code, the transfer would be done.

No bank account number. Not even a mobile number or an email ID. Just a random string of characters would allow me to transfer money to him! And later I could give him my UPI ID, and next month onwards he could simply send me a request via UPI for his salary. And two clicks later it would be done!

Mint has reported that there are massive delays in merchants installing point of sale devices in response to the cash ban. Banks should instead seek to acquire merchants to accept money via UPI. It’s simple, it’s quick and it protects privacy.

In fact, if the bank sales staff now have bandwidth, it can be argued that all the planets have aligned for UPI to take off for merchant payments – people have less cash, point of sale devices are not available, and both merchants and shoppers have shown openness to cashless payments, and there is a push from the government.

If only the banks can bite…

Siri Apps

So now that Apple has opened up Siri to third party developers (starting with iOS 10), I hope that app makers make use of this features clearly.

There are some apps, for example, that require inputs from time to time. My wife, for example, recently downloaded an app to track our daughter’s inputs and outputs.

The problem was that each time our daughter either input or output something, my wife had to unlock her iPhone, go to this app, and then use 3/4 more clicks to enter the necessary information. The complexity was so much that within a day she (wife) had stopped using it, and presently uninstalled the app.

This kind of app that needs frequent inputs seems ideally placed to get Siri integration. Imagine saying “Hey Siri. My baby just shat”, and the app gets immediately updated, and stuff. Given how powerful Siri already is, I don’t see any technical challenge in implementing this. The challenge, though, is on the product front, for apps to be able to use this judiciously.

PS: I just updated my laptop to MacOS Sierra, and so now have Siri on my Mac as well. only problem is that Siri on phone is so much more responsive than Siri on Mac. So when I want to call the Mac Siri, the phone Siri responds first, annoying me!

Big data at HDFC Bank?

I had a bit of a creepy moment today – I must admit that, despite being a “data guy” and recommending clients to use data to make superior decisions (including customisations), it does appear creepy when you as a customer figure that your service provider has used data to customise your experience.

I’m in Barcelona, and wanted to withdraw cash from my Citibank account in India. Withdrew once, but when I wanted to withdraw more, the transaction didn’t go through (this happened multiple times, at multiple ATMs).

Frustrated, I figured that this might be due to some limits (on how much I could transact per day), and then decided to get around the limitations by transferring some money to my HDFC Bank account (since I’m carrying that debit card as well).

An hour after I’d transferred the money by IMPS, I put my HDFC Debit Card in my wallet and walk out, when I see an email from the bank informing me that my Debit Card is valid only in India, and with a link through which I could activate international transactions on it.

I’d never received such emails from HDFC Bank before, so this was surely in the “creepy” category. It might have been sent to me by the bank at “random”, but the odds of that are extremely low. So how did the bank anticipate that I might want to use my debit card here, and send me this email?

I have one possible explanation, and if this is indeed the case, I would be very very impressed with HDFC Bank. Apart from my debit card, I also have a credit card from HDFC Bank, which I’ve been using fairly regularly during my time in Europe (that my only other credit card is an AmEx, which is hardly accepted in Europe, makes this inevitable).

My last transaction on this credit card was to pay for lunch today, and so if HDFC Bank is tracking my transactions there, it knows that I’m currently in Europe (given the large number of EUR transactions recently, if not anything else).

Maybe the bank figured out that if I’m abroad, and have transferred money by IMPS (which implies urgency) into my account, then it is for the purpose of using my debit card here? And hence they sent me the email?

The counterargument to this is that this is not the first time I’ve IMPSd to my HDFC Bank account during this trip – the Income Tax and Service Tax websites don’t accept Citibank, so I routinely transfer to HDFC to make my tax payments. So my argument is not watertight.

Yet, if the above explanation as to why HDFC Bank guessed I was going to use my debit card is true, then there are several things that HDFC Bank has got right:

  1. Linkage between my bank account and credit card. While I’ve associated both with the same customer ID, my experience with legacy systems in Indian financial institutions means actually associating them is really impressive
  2. Tracking of my transactions on my credit card to know my whereabouts. If HDFC has done a diligent job of this, they know where exactly I’ve been over the last few months (provided I’ve used my card in these destinations of course).
  3. Understanding why I use my account. While I’ve IMPSd several times in the past (as explained above), it’s all been in either the “service tax season” or “advance/self-assessment income tax season”. Mid-May is neither. So maybe HDFC Bank is guessing that this time it may not be for tax reasons?
  4. Recognising I might want to use my debit card. If I’ve put money into my account and it’s not tax season, maybe they recognised I might want to use my debit card?

Maybe I might be giving them too much credit, and it just happened that the randomly sent out email came at the time when I’d just put the money into the account.

And the link they sent to enable international transactions worked! I had to use my laptop (it didn’t work on either the app or mobile web, so that’s one point deducted for them), but with a few clicks after logging into my bank account, I was able to enable the transactions!

So maybe there is reason to be impressed!

 

The problem with Slack, and why it’s inferior to DBabble

When two of the organisations I’m associated with introduced me to the chatting app Slack, it reminded me of the chatting app DBabble (known to us in IIMB as BRacket) that was popular back when I was in college.

There were two primary reasons because of which Slack reminded me of DBabble. The first was the presence of forums/groups. There was a “General” that everyone in the organisation was part of, and then were other groups that you could choose to join and be a conversation in. The second was that you could not only converse on the fora, but also send personal messages to each other – something DBabble also enabled.

There are several reasons why Slack is superior to DBabble. Most importantly, you can tag people in your messages on forums and they get notified, so that they can respond – this is a critical feature for using it for work purposes.

Secondly, Slack integrates well with other tools that people use for work – such as email and a lot of development tools, for example (which one of the organisations I’m associated with uses heavily, but I’ve never got into that loop). Slack also has a very nice search feature that allows you to pull up discussions based on keywords, etc.

What Slack sorely lacks, which makes me miss DBabble like crazy, however, is threaded conversations. The conversation structure in each channel in Slack is linear – which means you can effectively have only one thread of conversation at a time.

When you have a large number of people on the channel, however, people might initiate several different threads of conversation. As things are, however, a Darwinian process means that all but one of them get unceremoniously cut out, and we end up having only one conversation.

It is also a function of whether Slack is used for synchronous or asynchronous messaging (former implies everyone replies immediately, latter means conversations can take their own time and there’s no urgency to participate immediately, like email, for example). My understanding is that the way it’s built, it can be used in both ways. My attempts to use it as an asynchronous messenger, however, have failed because some of the conversations I’ve tried to initiate have gotten buried above other conversations others on the channel have tried to start.

The problem with Slack is that it assumes that each forum will have only one active conversation at a time. Instead, if (like DBabble) it allows us to have different conversation threads, things can become a lot more efficient.

One of the nice features of forums on DBabble was that everytime you went to the forum, it would show you all the active threads by showing them in bold. DBabble allowed infinite levels of threading, and only messages that were unread (irrespective of which branch of which thread they were in) would be in bold, meaning you could follow all threads of conversation (this also proved problematic for some as we developed an OCD to “unbold” – read every single message on every forum we were part of).

Imagine how powerful threaded conversations can be at the corporate level especially when you can tag people in them – so you go to a forum, and can see all open discussions and see where your attention has been called, and contribute. Threading also means that you can carry out several different personal (1-to-1) conversations at a time without losing track of any.

It’s interesting that after DBabble (which also died after a later edition gave the option of “chat mode” which did away with threaded conversations) there has been no decent chat app that has come up that allows threaded conversations. Apart from possible bandwidth issues (which can happen when each message is suffixed with the full thread below it), I don’t see any reason this can’t be implemented!

I want my BRacket (DBabble) back. But then, chat has powerful network effects and there’s no use of me wanting a particular technology if sufficient number of other people don’t!

Blockchain and real estate

Based on the title of this blog post, you might assume this might be about Honduras, where there is a proposal to use the blockchain to store land records. The problem with Honduras is that there is no “trusted third party” – nobody even trusts the government, for example, so the best way to store land records is in a decentralised hard to tamper manner.

Over the last few days I’ve been reading up a bit on blockchain and bitcoin and how it works and so on. I haven’t yet got to the math – that it is described as “proof of work” irritates me no end (given that work should be evaluated on output rather than input).

So I see that what makes blockchain secure (apart from the miners having to agree on every transaction, and securing bunches of transactions using cryptographic hashes) is that every block contains within itself a hash of the previous blocks. In other words, the entire sequence of transactions is maintained.

The way “normal currency” (like cash) works is that only possession matters, not history. So the fact that there is a hundred rupee note in my pocket means that I can spend that money, and nobody has a track of how that hundred rupee note reached my pocket. This makes the system insecure since if a pickpocket picks this note, there is no proof (apart from possibly catching him in the act red-handed) that he picked it from my pocket.

With bitcoin, on the other hand, there is a record of how each bit of currency (no pun intended) ended up where it ended up. So even if someone were to magically “steal” my bitcoin, the historical records show that this legitimately belongs to me, and that makes it secure.

This reminds me of the paperwork involved when we bought our apartment in Bangalore last year. Normally you would imagine that a certificate indicating that the title currently rests with the current owner is enough to conduct a real estate transaction. but lawyers and bankers here are not satisfied with that.

The paperwork for the apartment I bought went back sixty odd years, when the land on which the building was built was first “allotted” by the City Improvement Trust Board. If I have to sell this apartment on, along with the certificate that I own this apartment I’ll have to furnish copies of this entire history going 60-70 years back. And the way property deals are done here, I don’t expect the system to change.

So this is what makes real estate such a prime candidate for using blockchain. Not only is a third party (such as the government department that stores land records) not trusted, it is a standard practice to include the entire history of every land or property going back several years. A sale transfers ownership, but in terms of paperwork, a layer gets added, not replaced.

This shows why real estate is such a prime candidate for moving to blockchain for storing transactions. It is ironical that a small and crime-ridden country such as Honduras is showing the way on this. It is time for countries like India to consider similar uses. But first, we will need to digitise existing records and make sure there is exactly one owner for each piece of property, and blockchain can’t help us with that challenge!

The problem with Twitter

Starting from the mid-2000s, the dominant method to consume content was to follow individual blogs through RSS Feed readers such as Bloglines or Google Reader. You followed specific blogs, most of which (unlike this one) had content on specific topics.

So when I wanted to learn up on economics, I started following Marginal Revolution and Econlog. When I wanted to follow the global financial crisis, I added Felix Salmon and a couple of other blogs (which I don’t remember now). All I needed to do to read on specific topics was to follow specific people.

And then Google Reader Shared Items happened. Now, you didn’t really need to follow specific blogs, for there was a social network where people would share interesting stuff that they read. Now you could outsource following blogs to friends who became curators. So there was this one friend who would share pretty much every interesting post on Mashable. Another shared every interesting post from this blog called The Frontal Cortex. I didn’t need to follow these blogs. My “curator friends” shared the best pieces with me (and I know people relied on me for Econlog etc.).

Then around the turn of the decade, Twitter replaced Google Reader Shared Items as the primary content discovery platform. A couple of years later, Google would decommission Reader. The thing with Twitter was that the movement from following specific ideas and sites to following “curators” was complete.

While twitter also functions as a “normal” social network, a major function is the sharing of ideas, and so everyone on twitter is essentially a curator, sharing with her followers what she wants them to read. There is also scope for adding comments here, and adding one’s opinion to the content. This adds a sort of richness to the content, and people can filter stuff accordingly, without consuming everything one’s friend has shared.

The downside, however, is that you are forced to consume the opinions and links shared by everyone you follow. There might be someone who I might be following for his curation of technology links, but it might happen that he might also tweet heavily on politics, which I’m hardly interested in. There is an option to turn off retweets (which I’ve used liberally) but even so, there is a lot of “unwanted content” you have to consume from people. And since it is “opinion first” (and link later), you are forced to consume people’s opinion even if you’re just browsing their timeline.

What we need in Twitter is a way to curate people’s opinions on topics. For example, I might be interested in Person A’s opinion on politics but not anything else. Person B might offer good opinions on economics but might be lousy on other things. Person C might be good for technology and sports. And so forth.

Of course, you can’t charge people with classifying their own tweets – that will add too much friction to the process. What you need is an intelligent process or app that can help classify people’s tweets and show you only what you want to know.

I can think of a couple of designs for the app – one could be where you could tell it not to show any more tweets from someone on a particular topic (or block a topic itself). Another is for you to upvote and downvote tweets, so that the app learns your preferences and shows you what you want.

Yet, I’m not confident that such an app will be built. The problem is that twitter has been notorious in terms of cutting off access to its API to apps built on it, or cutting permissions of what apps can see (Facebook is as guilty here). So it’s a massive challenge to get people to actually invest in building twitter apps.

Twitter as it exists currently doesn’t work for me, though. I repeatedly find the problem that there is way too much outrage on my timeline, and despite mercilessly cutting the number of people I follow, I find that it’s a slippery slope and otherwise interesting people continue to tweet about stuff that I don’t want to read about. And so my engagement is dipping.

I don’t need twitter itself to do anything about it. All they should do is to send out credible signals that they’ll not pull the rug under the feet of developers, so that APIs can be developed, which can make the platform a much more pleasant experience for users.