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.

So the wife and I both decided to sign up on the dating app TrulyMadly, she to conduct research for her matchmaking service, and me as part of my research for the book that I’m currently revising. Based on our collective usage of our respective apps for about an hour, here are some pertinent observations.

• Sexism: The wife can see salaries of men she is getting matched with, while I don’t get to see salaries of women being recommended to me. Moreover, women are allowed to “lurk” (and not have a public profile) on the platform, but no such thing for men. I’m surprised no one has called out TrulyMadly on their sexism
• Job board: To list on the app you need to indicate your profession and job, and how much you are making. So if you are a woman on this site, apart from getting to check out men, you get to check out what jobs pay how much, and it’s not inconceivable that you use the app to find yourself a job.
• Judgments: This should possibly go down under sexism again. Anyway, the wife has mentioned her qualifications as “MBA”, and she is only being shown men who are graduates of top B-schools in India. No such thing for me – women shown to me had all kinds of qualifications. It’s like TrulyMadly has decided that women should only date men who are at least as well qualified as them. Moreover, the app also decides that men can only date women who are shorter than them, though there’s a setting somewhere to change this.
• Age bar: Based on my age (which I entered as 34), the app decided that I should only be allowed to check out women between the ages of 26 and 34. These can be moved around, in case I have fetishes outside this age range, but I’m shocked that they are not aware of the N/2+7 rule – based on which the lower limit should’ve been set at 24 (34/2+7) and not 26.
• Gender imbalance: The app gave up on me after I rejected some half a dozen women, after which I deactivated my account and deleted the app. The wife’s app, however, continues to go strong, as she might have rejected some two or three dozen men by now (apart from having done research on what jobs pay how much). Just goes to show the gender imbalance on the app. I can imagine this leading to a lot of frustrated people, of both genders.

Ok that’s it for now. Any more insights you can read in my book (I hope to get it out in the next month or two)!

Moral of the story: Product management pays better than category leader.

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…

The Birthday Party Problem

Next Tuesday is my happy birthday. As of now, I’m not planning to have a party. And based on some deep graph theoretic analysis that the wife and I just did over the last hour, it’s unlikely I will – for forming a coherent set of people to invite is an NP-hard problem, it seems like.

So five birthdays back we had a party, organised by the wife and meant as a surprise to me. On all counts it seemed like a great party. Except that the guests decided to divide themselves into one large clique and one smaller clique (of 2 people), leaving me as the cut vertex trying to bridge these cliques. That meant the onus was on me to make sure the tiny clique felt included in the party, and it wasn’t a lot of fun.

The problem is this – how do you invite a subset of friends for a party so that intervention by the host to keep guests entertained is minimised?

Let’s try and model this. Assume your friends network can be represented by an unweighted undirected graph, with a pair of friends being connected by an edge if they know (and get along with) each other already. Also assume you have full information about this graph (not always necessary).

The problem lies in selecting a subgraph of this graph such that you can be confident that it won’t break into smaller pieces (since that will mean you bonding with each such sub-group), and no guest feels left out (since the onus of making them comfortable will fall on you).

Firstly, the subgraph needs to be connected. Then, we can safely eliminate all guests who have degree of either zero or one (former is obvious, latter since they’ll be too needy on their only friend). In fact, we can impose a condition that each guest should have a minimum degree of two even in the subgraph.

Then we need to impose conditions on a group in the party breaking away. We can assume that for a group of people to break away, they need to be a clique (it is not a robust requirement, since you and someone you find at a party can suddenly decide to find a room, but reasonable enough).

We can also assume that for a group to break away, the strength of their mutual connections should outweigh the strength of their connections to the rest of the group. Since we’re using unweighted graphs here, we can simply assume that a group can break away if the number of edges between this group and the rest of the network is less than the size of the group.

So if there is a group of three who, put together, have two connections to the rest of the group, the group can break away. Similarly, a clique of four will break away from the main group if they have three or less edges going over. And let’s assume that the host is not a part of this subgroup of guests.

Given these constraints, and constraints on party size (minimum and maximum number of guests to invite), how can we identify an appropriate subset of friends to invite for the party? And I’m assuming this problem is NP-Hard (without thinking too much about it) – so can we think of a good heuristic to solve this problem

Do let me know the answer before next Tuesday, else I may not be able to have a party this time as well!

Pizza from dominos – good and bad

Last night we decided we wanted pizza from dominos for dinner. Having been used to Swiggy, I instinctively googled for dominos and tried to place the order online.

There is one major fuckup with the dominos website – it asks you to pick the retail outlet closest to you, rather than taking your location and picking it yourself. And so it happened that we picked an outlet not closest to us.

I quickly got a call from the guy at the outlet where my order had gone, expressing his inability to deliver it, and saying he’ll cancel my order. I gave him a mouthful – it’s 2016, and why couldn’t he have simply transferred the order to the outlet that is supposed to service me?

I was considering cancelling the order and not ordering again (a self-injurious move, since we wanted Dominos pizza, not just pizza), when the guy from the outlet in whose coverage area I fell called. He explained the situation once again, saying my original order was to be cancelled, and he would have to take a new order.

Again – it wasn’t just a fuckup in the payment in the Dominos system, in which case they could’ve simply transferred my order to this new guy. So I had to repeat my entire order once again to this guy (not so much of a problem since I was only getting one pizza) and my address as well (it’s a long address which I prefer filling online).

Then there was the small matter of payment – one reason I’d ordered online was that I could pay electronically (I used PayTM). When I asked him if I could pay online for the new order he said I had to repeat the entire process of online ordering – there was no order ID against which I could simply logon and pay.

I played my trump card at this time – asked him to make sure the delivery guy had change for Rs. 2000 (I’d lined up at a bank 2 weeks back and withdrawn a month’s worth of cash, only that it was all in Rs. 2000 notes). He instantly agreed. Half an hour later, the pizza, along with change for Rs. 2000 was at my door.

The good thing about the experience was that the delivery process was smooth, and more importantly, the outlet where my order reached had taken initiative in communicating it to the outlet under whose coverage my house fell – the salespersons weren’t willing to take a chance to miss a sale that had fallen at their door.

The bad thing is that Jubilant Foodworks’ technology sucks, big time. Thanks to the heavily funded and highly unprofitable startups we usually order from, we’re used to a high level of technology from the food delivery kind of businesses. Given that Jubilant is a highly profitable company it shouldn’t be too hard for them to license the software of one of these new so-called “foodtech” companies to further enhance the experience.

No clue why they haven’t done it yet!

PS: I realise I’ve written this blogpost in the style I used to write in over a decade ago. Some habits die hard.

Using my cook as an ATM

This happened ten days before high value notes were withdrawn, and suggests nothing about my cook’s political opinions or views.

On 30th October 2016, I paid my cook his salary for October. As it was the usual practice, I paid him in cash. He asked me if I could do an online transfer instead.

It was the first day of Diwali, and he needed to send money to his wife in Bihar. And it being Diwali, all banks were closed, and there was no way he could send money to her. So he asked me if I could do that. And if I were anyway transferring money to his wife’s account, could I send her a bit more, he asked – he would compensate me for the extra amount in cash.

And so like that I used my cook as an ATM. He gave me his wife’s account details (it was such an obscure branch that I’d to google it to find the IFSC code – wasn’t in citibank’s lookup list). I added her as a “payee” and immediately IMPSd the amount to her. And my cook gave me the extra funds I’d transferred in cash.

Later on, I told him to install his bank’s app on his newly acquired fancy phone (with a Reliance Jio sim). I’m not sure he’s done that but considering how resourceful he is, it wouldn’t be long before he does that. And more of the Bihari cooks network in Bangalore do likewise.

Nandan Nilekani, in his championing of the UPI, likes to talk about how “anybody can be an ATM” with the new technology. This was an exemplary example of that.

The only fly in the ointment was that I didn’t need cash that day – after all I’d been to the ATM earlier that morning just so that I could get cash to pay my cook – so I ended up with a lot of cash that I didn’t need. Thankfully I was able to spend it productively before the ceased to be legal tender.

Following the withdrawal of high currency notes, I told my cook I would pay his subsequent salaries by bank transfer. He gladly agreed.

Damming the Nile and diapers

One of the greatest engineering problems in the last century was to determine the patterns in the flow of the Nile. It had been clear for at least a couple of millennia that the flow of the river was not regular, and the annual flow did not follow something like a normal distribution.

The matter gained importance in the late 1800s when the British colonial government decided to dam the Nile. Understanding accurately the pattern of flows of the river was important to determine the capacity of the reservoir being built, so that both floods and droughts could be contained.

The problem was solved by Harold Edwin Hurst, a British hydrologist who was posted in Egypt for over 60 years in the 20th Century. Hurst defined his model as one of “long-range dependence”, and managed to accurately predict the variation in the flow of the river. In recognition of his services, Egyptians gave him the moniker “Abu Nil” (father of the Nile). Later on, Benoit Mandelbrot named a quantity that determines the long-range dependence of a time series after Hurst.

I’ve written about Hurst once before, in the context of financial markets, but I invoke him here with respect to a problem closer to me – the pattern of my daughter’s poop.

It is rather well known that poop, even among babies, is not a continuous process. If someone were to poop 100ml of poop a day (easier to use volume rather than weight in the context of babies), it doesn’t mean they poop 4ml every hour. Poop happens in discrete bursts, and the number of such bursts per day depends upon age, decreasing over time into adulthood.

One might think that a reasonable way to model poop is to assume that the amount of poop in each burst follows a normal distribution, and each burst is independent of the ones around it. However, based on a little over two months’ experience of changing my daughter’s diapers, I declare this kind of a model to be wholly inaccurate.

For, what I’ve determined is that far from being normal, pooping patterns follow long-range dependence. There are long time periods (spanning a few diaper changes) when there is no, or very little, poop. Then there are times when it flows at such a high rate that we need to change diapers at a far higher frequency than normal. And such periods are usually followed by other high-poop periods. And so on.

In other words, the amount of poop has positive serial correlation. And to use the index that Mandelbrot lovingly constructed and named in honour of Hurst, the Hurst exponent of my daughter’s (and other babies’) poop is much higher than 0.5.

This makes me wonder if diaper manufacturers have taken this long-range dependence into account while determining diaper capacity. Or I wonder if, instead, they simply assume that parents will take care of this by adjusting the inter-diaper-change time period.

As Mandelbrot describes towards the end of his excellent Misbehaviour of markets , you can  use so-called “multifractal models” which combine normal price increments with irregular time increments to get an accurate (fractal) representation of the movement of stock prices.

PS: Apologies to those who got disgusted by the post. Until a massive burst a few minutes ago I’d never imagined I’d be comparing the flows of poop and the Nile!