algorithm – Pertinent Observations

Computer science and psychology

This morning, when I got back from the gym, my wife and daughter were playing 20 questions, with my wife having just taught my daughter the game.

Given that this was the first time they were playing, they started with guessing “2 digit numbers”. And when I came in, they were asking questions such as “is this number divisible by 6” etc.

To me this was obviously inefficient. “Binary search is $O(log n)$ “, I realised in my head, and decided this is a good time to teach my daughter binary search.

So for the next game, I volunteered to guess, and started with “is the number $\ge 55$ “? And went on to “is the number $\ge 77$ “, and got to the number in my wife’s mind (74) in exactly 7 guesses (and you might guess that $\lceil log_2 90 \rceil$ (90 is the number of 2 digit numbers) is 7).

And so we moved on. Next, I “kept” 41, and my wife went through a rather random series of guesses (including “is it divisible by 4” fairly early on) to get in 8 tries. By this time I had been feeling massively proud, of putting to good use my computer science knowledge in real life.

“See, you keep saying that I’m not a good engineer. See how I’m using skills that I learnt in my engineering to do well in this game”, I exclaimed. My wife didn’t react.

It was finally my daughter’s turn to keep a number in mind, and my turn to guess.

“Is the number $\ge 55$ ?”
“Yes”

“Is the number $\ge 77$ ?”
“Yes”

“Is the number $\ge 88$ ?”
“Yes”

My wife started grinning. I ignored it and continued with my “process”, and I got to the right answer (99) in 6 tries. “You are stupid and know nothing”, said my wife. “As soon as she said it’s greater than 88, I knew it is 99. You might be good at computer science but I’m good at psychology”.

She had a point. And then I started thinking – basically the binary search method works under the assumption that the numbers are all uniformly distributed. Clearly, my wife had some superior information to me, which made 99 far more probable than any number between 89 and 98. And s0 when the answer to “Is the number $\ge 88$ ?”turned out to by “yes”, she made an educated guess that it’s 99.

And since I’m used to writing algorithms, and teaching dumb computers to solve problems, I used a process that didn’t make use of any educated guesses! And thus took far many more steps to get to the answer.

When the numbers don’t follow a uniform distribution, binary search works differently. You don’t start with the middle number – instead, you start with the weighted median of all the numbers! And then go on to the weighted median of whichever half you end up in. And so on and so forth until you find the number in the counterparty’s mind. That is the most optimal algo.

Then again, how do you figure out what the prior distribution of numbers is? For that, I guess knowing some psychology helps.

I wish I’d seen this 12 years back

Have I told you that my wife regularly puts out a lot of great content on relationships? She has a relationship blog. A newsletter on relationship markets (brownie points for guessing the funda of the name). A personal youtube channel. A “professional” youtube channel.

There’s a lot of amazing content she puts out through all these channels, but I must say that I got especially blown away by this one video that she has put up recently. It is a conversation with Urvashi Goverdhan, an actor and model, about “how to get the first date”.

So you might be single and wondering how you can chat up someone of the opposite sex (or in the interest of diversity, should I say “gender that you want to partner with”?). And if you are like what I was until 2009, you have no clue how to do it.

Most of the time you play over conservative and miss out on opportunities. Sometimes you might decide to go aggressive, but do it all wrong (as I kept doing through most of the 2000s), and count yourself lucky that your “target” decides that physically harming you or shaming you is not worth their time.

If you are like that (and I was like that till at least August 2009 – if you’re not convinced go read my blog archives. Everything about my life from 2004 onwards is well documented here), then I strongly urge you to listen to this conversation, as these two wonderful ladies talk about what women look out for in men, and what men need to do to get women’s attention in a nice manner.

Watching this now, I so strongly wish that I had seen this 11-15 years back. I would have been able to make very good use of it back then. Then again, if I had seen this video and been able to make good use of it back in the day, then there is a strong likelihood that I may not have met the person who is now my wife at all (some of you might know – we met through this blog, and then Orkut, and then chatted for long enough that when we met, it was a “qualified lead” that I was able to convert).

It is a long video, but completely worth your time. So go ahead and watch it in full. Oh, and you should subscribe to the Marriage Broker Auntie Youtube channel as well, if you haven’t already.

Still not convinced that you should watch the video pasted above? Here are some pointers I gathered, all from the first 10 minutes of the video:

If a boy is in a group that already has girls, then there is a higher chance of other girls wanting to talk to him
Pick up lines don’t work. At all.
When you repeatedly make eye contact with someone, smile. Don’t stare.

Okay, now go off and watch the video!

Chasing Dhoni

Former India captain Mahendra Singh Dhoni has a mixed record when it comes to chasing in limited overs games (ODIs and T20s). He initially built up his reputation as an expert chaser, who knew exactly how to pace an innings and accelerate at the right moment to deliver victory.

Of late, though, his chasing has been going wrong, the latest example being Chennai Super Kings’ loss at Kings XI Punjab over the weekend. Dhoni no doubt played excellently – 79 off 44 is a brilliant innings in most contexts. Where he possibly fell short was in the way he paced the innings.

And the algorithm I’ve built to represent (and potentially evaluate) a cricket match seems to have done a remarkable job in identifying this problem in the KXIP-CSK game. Now, apart from displaying how the game “flowed” from start to finish, the algorithm is also designed to pick out key moments or periods in the game.

One kind of “key period” that the algorithm tries to pick is a batsman’s innings – periods of play where a batsman made a significant contribution (either positive or negative) to his team’s chances of winning. And notice how nicely it has identified two distinct periods in Dhoni’s batting:

The first period is one where Dhoni settled down, and batted rather slowly – he hit only 21 runs in 22 balls in that period, which is incredibly slow for a 10 runs per over game. Notice how this period of Dhoni’s batting coincides with a period when the game decisively swung KXIP’s way.

And then Dhoni went for it, hitting 36 runs in 11 balls (which is great going even for a 10-runs-per-over game), including 19 off the penultimate over bowled by Andrew Tye. While this brought CSK back into the game (to right where the game stood prior to Dhoni’s slow period of batting), it was a little too late as KXIP managed to hold on.

Now I understand I’m making an argument using one data point here, but this problem with Dhoni, where he first slows down and then goes for it with only a few overs to go, has been discussed widely. What’s interesting is how neatly my algorithm has picked out these periods!

Why Twitter is like Times Now

One reason I stopped watching news television about a decade back is because of its evolution into a “one issue channel”. On each day, a channel basically picks a “topic of the day”, and most discussion on that day is regarding that particular topic.

In that sense, these “news channels” hardly provide news (unless you bother to follow the tickers at the bottom) – they only provide more and more discussion about the topic du jour (ok I’m feeling all pseud about using French on my blog!). If you’re interested in that topic, and willing to consume endless content about it, great for you. If not, you better look for your news elsewhere (like the <whatever> o’clock news on the government-owned channel which at least makes a pretence of covering all relevant stuff).

One thing that made Twitter attractive soon after I joined it in 2008 was the diversity of discussions. Maybe it was the nature of the early users, but the people I followed provoked thought and provided content on a wide array of topics, at least some of which I would find interesting. And that made spending time on twitter worthwhile.

It’s still true on a lot of days nowadays, but I find that Twitter is increasingly becoming like a modern news channel such as Times Now. When there are certain events, especially of a political nature, it effectively becomes a one-topic channel, with most of the timeline getting filled with news and opinion about the event. And if it is either an event you don’t care about, or if you’ve moved on from the event, Twitter effectively becomes unusable on such days.

In fact, a few of my twitter breaks in the last 2-3 years have followed such periods when Twitter has turned into a “one issue channel”. And on each of these occasions, when I’ve joined back, I’ve responded by unfollowing many of these “one-issue tweeters” (like this guy who I don’t follow any more because he has a compulsive need to livetweet any game that Arsenal is playing).

That Twitter becomes a one-topic channel occasionally is not surprising. Basically it goes like this – there are people who are deeply passionate or involved in the topic, and they show their passion by putting out lots of tweets on the topic. And when the topic is a current event, it means that several people on your timeline might feel passionately about it.

People not interested in the topic will continue to tweet at their “usual rate”, but that gets effectively drowned out in the din of the passionate tweeters. And when you look at your linear timeline, you only see the passion, and not the diverse content that you use Twitter for.

Some people might suggest a curated algorithmic feed (rather than a linear feed) as a solution for this – where a smart algorithm learns that you’re not interested in the topic people are so passionate about and shows you less of that stuff. I have a simpler solution.

Basically the reason I’m loathe to unfollow these passionate tweeters is that outside of their temporary passions, they are terrific people and tweet about interesting stuff (else I wouldn’t follow them in the first place). The cost of this, however, is that I have to endure their passions, which I frequently have no interest in.

The simple solution is that you should be able to “temporarily unfollow” people (Twitter itself doesn’t need to allow this option – a third party client that you use can offer this at a higher layer). This is like WhatsApp where you can mute groups for just a day, or a week. So you can unfollow these passionate people for a day, by which time their passion will subside, and you can see their interesting selves tomorrow!

Of course it’s possible to manually implement this, but I know that if I unfollow them today I might forget to follow them back tomorrow. And there are countless examples of people in that category – who I unfollowed when they were passionate and have thus missed out on their awesomeness.

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.

On apps tracking you and turning you into “lab rats”

Tech2, a division of FirstPost, reports that “Facebook could be tracking all rainbow profile pictures“. In what I think is a nonsensical first paragraph, the report says:

Facebook’s News Feed experiment received a huge blow from its social media networkers. With the new rainbow coloured profile picture that celebrates equality of marriage turned us into ‘lab rats’ again? Facebook is probably tracking all those who are using its new tool to change the profile picture, believes The Atlantic.

I’m surprised things like this still makes news. It is a feature (not a bug) of any good organisation that it learns from its user interactions and user behaviour, and hence tracking how users respond to certain kinds of news or updates is a fundamental part of how Facebook should behave.

And Facebook is a company that constantly improves and updates the algorithm it uses in order to decide what updates to show whom. And to do that, it needs to maintain data on who liked what, commented on what, and turned off what kind of updates. Collecting and maintaining and analysing such data is a fundamental, and critical, part of Facebook’s operations, and expecting them not to do so is downright silly (and it would be a downright silly act on part of the management if they stop experimenting or collecting data).

Whenever you sign on to an app or a service, you need to take it as a given that the app is collecting data and information from you. And that if you are not comfortable with this kind of data capture, you are better off not using the app. Of course, network effects mean that it is not that easy to live like you did in “the world until yesterday”.

This seems like yet another case of Radically Networked Outrage by outragers not having enough things to outrage about.

Jobs and courtship

Jobs, unlike romantic relationships, don’t come with a courtship period. You basically go for a bunch of interviews and at the end of it both parties (you and the employer) have to decide whether it is going to be a good fit. Neither party has complete information – you don’t know what a typical day at the job is like, and your employer doesn’t know much about your working style. And so both of you are taking a risk. And there is a significant probability that you are actually a misfit and the “relationship” can go bad.

For the company it doesn’t matter so much if the odd job goes bad. They’ll usually have their recruitment algorithm such that the probability of a misfit employee is so low it won’t affect their attrition numbers. From the point of view of the employees, though, it can get tough. Every misfit you go through has to be explained at the next interview. You have a lot of misfits, and you’re deemed to be an unfaithful guy (like being called a “much-married man”). And makes it so tough for you to get another job that you are more likely to stumble into one where you’re a misfit once again!

Unfortunately, it is not practical for companies to hire interns. I mean, it is a successful recruitment strategy at the college-students level but not too many people are willing to get into the uncertainty of a non-going-concern job in the middle of their careers. This risk-aversion means that a lot of people have no option but to soldier on despite being gross misfits.

And then there are those that keep “divorcing” in an attempt to fit in, until they are deemed unemployable.

PS: In this regard, recruitments are like arranged marriage. You make a decision based on a handful of interviews in simulated conditions without actually getting to know each other. And speaking of arranged marriage, I reprise this post of mine from six years ago.

Bol Bol Why did you ditch me …

of late i’m having frequent bouts of extreme depression…

After careful analysis you see that the only chance for you to win is if the Queen of Hearts is with West.

I’m trying to figure out whether i have a crush on her or not.

…I’ve started enjoying it – talking to her frequently, guessing what goes behind each thread of conversation, trying to understand her while she tries to understand me…

You think of a wonderful scenario. You start day-dreaming about it. You day-dream about it so much that you start believing it’s true.

Of course, this screw-up has been hitting me for the last 12 hours. And that reminds me of the fact that she hasn’t responded to my mails or messages for a long time. Pushes me further down. Feel like totally giving up in life.

Suddenly “inspired” by an arbit conversation with a friend, I happened to rummage my almost defunct yahoo mailbox and look through some old mails. a series of exchanges with her, circa early 2004.

I input a girl into my algorithm and ask it if there is a possibility of a relationship with her. If it says no, I can completely believe it and get on with life. A ‘yes’, however, means trouble. It means there is a possibility of a relationship, but there is no guarantee.

That little bit of indiscretion. The little bit of getting carried away. And then, that little bit of my foot in my mouth – I could’ve probably wriggled out of the situation, but i chose not to. Yet another relationship in limbo.

Think I have hit a local optimum. And jumping the gun being my habit, I tell my mom about it before I confirm it with the woman in question.

I’m still trying to figure out the nature of this relationship. It’s much stronger than simple good platonic friendship, but doesn’t seem to be anywhere near a romantic relationship

I made the measurement today. don’t ask me how. we are good friends.

Ranga sends this: Any kind of symbiotic relationship ends up being remunerative.

“i believe people enter your life exactly at a point when u need them to grow together and exit/fade away from your life at the right time, enabling you to move ahead. its sad but true”

at several points of time in life, you end up in the unpleasant situation where your relationship with someone has hit the pits. there is a cold war on, and you haven’t spoken to him/her for a while. and you want to try and re-build the relationships.

She took my hand in hers and started gently stroking my fingers. One by one.

For most of the first half of last year, I used to turn to her whenever I was depressed.

When we met for the first time, my order of a mousse was met with a “oh, I didn’t know you are such a high calorie person. I?m very calorie conscious you know. I’ll have tea -without milk or sugar”. I had quickly changed my order to a cup of cold coffee.

And that relationship. Something had snapped right at the end. She had suddenly wanted to puke and wanted to hang up.

Having been in a budding long distance relationship (which ultimately didn’t wrok out; in fact, it failed before it became “official”), I couldn’t agree more with this article.

She is still an out-of-money option – quite ordinary for most of the time, offering nothing, or mildly negative returns; but once in a very long time you get great value, making the long periods of mediocrity worth their while.

Tauba Tera Jalwa, Tauba tera pyar,
Tera Emosanal Attyachaar!