Smallest multiple with constraints

Problem statement:

Given a number 'n', design an algorithm that will output the smallest integer number 'X' which contains only the digits {0, 1} such that X mod n = 0 and X > 0 (1 ≤ n ≤ 100000)

Problem credits: Ayush on the Stony Brook Puzzle Society Facebook Group

Insight: Suppose n = 6. Consider some numerator (target answer X) to be 1101. Can this be correct? We can verify by dividing and checking the remainder. 1101 mod 6 = 3, so we've overshot the answer by 3 or more (since we might not have the smallest X).

Another way to get the same remainder '3' is to say:

• 1000 mod 6 = 4
• 100 mod 6 = 4
• 00 mod 6 = 0
• 1 mod 6 = 1

Add up all the remainders and take that mod 6. Hence, (4 + 4 + 0 + 1) mod 6 = 9 mod 6 = 3.

Which basically means that we want to find that subset of powers of 10, added together (mod n) leave a remainder of 0. We can solve this using dynamic programming using a technique similar to the one used to solve the subset sum problem. The solution to our problem (and to the subset sum problem) is pseudo-polynomial. Specifically, our problem is solved in time O(n log X).

Here is the ideone link, and below is the code (in python) to solve it.

Follow up problem:

Find a number 'X' given an 'n' (similar to the problem above) except that you are allowed to only use digits {0, 3, 5, 8}. Can you always find a solution for any 'n'?

How to make an intense cup of hot chocolate

tl;dr Find a way to melt chocolate; then add milk and sugar. Drink up (credits to Yazhini for this succinct description).

Experiment: One of the most intense hot chocolates you've ever had

Ingredients -- You will need (for 1 cup hot chocolate [240ml]):

1. 250 ml whole milk
2. 4-6 squares of dark chocolate (I use Ghirardelli)
3. A ceramic cup
4. 2 tablespoons of water
5. (optional) 1/2 teaspoon sugar

Procedure:

1. Pour the whole milk into a saucepan and heat till it begins to simmer
2. Now take the chocolate squares and place them in the ceramic cup. Heat in a microwave for ~20 second at medium power
3. Pour 2 tablespoons of water on the chocolate and heat in the microwave for 30 second at medium power
4. Stir the chocolate and water well to make it a thick homogeneous mixture
5. Pour the simmering milk into the ceramic cup, add sugar if needed, and stir well
6. Optionally strain the hot chocolate to rid it of any thin layer of cream that may have formed while simmering the milk
7. Drink and enjoy!

Observation:

One happy person (i.e. you)

Inference:

Hot chocolate makes you happy :)

Macho-ism in Computer Science

It's common for me to see blog posts by companies talking about the high traffic volume in terms of QPS/RPS they handle and the amount of data they process, and that's super cool. But then there's another class of facts I see floating around a lot, and they tend to talk about the size of their hadoop or serving cluster, and things like "dozens or hundreds" of machines in your fleet seem to be something to be proud of. I don't understand this way of thinking or at least don't see the point of it. As I see things, it's nicer if you can get more done with fewer machines, and not more machines in your fleet.

Static To Dynamic Transforms or: How I learnt to stop worrying and love static data structures

Gaurav in his blog post describes in great detail what a static to dynamic transform is, when it is applicable, how to dynamize a static data structure, and the costs of inserting and looking up values in a dynamized data structure (relative to the costs in the corresponding static structure). I'll skip all of that since it's been presented so well in the link above, but will give a short description of the essentials.

• What is a static data structure? A static data structure is one where it isn't computationally efficient to insert a new element, and typically involves re-building the whole structure to be able to add just one element. e.g. A sorted array. If you want to keep an array of elements sorted, then inserting a single element could involve shifting all the elements one place to the right.
• What is a dynamic data structure? A dynamic data structure is one where adding a single element is computationally efficient, and doesn't involve touching every element in the data structure. e.g. A height-balanced binary search tree. Inserting a single element in a height-balanced binary search tree involves O(log n) node rotations. See this page to read more about the differences between static and dynamic data structures.
• What is the amortized insertion time to insert an element in a dynamized sorted array? Inserting a single element into a dynamized sorted array costs O(log n) per insertion.
• How much extra space do you need to dynamize a sorted array? You need O(n) extra space to dynamize a sorted array, since you need intermediate storage space when merging parts (levels) of the dynamized data structure.
• What is the query time in a dynamized sorted array? Searching for an element in a sorted array costs O(log n), whereas searching in a dynamized sorted array costs O(log² n).

We can see that the overhead of dynamizing a sorted array is something we can live with. In fact, it's almost unbelievable that we can dynamize a sorted array by paying only as much as an O(log n) overhead per insertion, and an O(log n) overhead per query.

Static to Dynamic transforms in practice: Consider that you're working with an inherently static data structure such as the SSTable (Sorted String Table), and that your system must maintain all its data as part of some SSTable. In such a case, inserting even a single row means that you need to rebuild the new SSTable which contains all the rows from the previous SSTable plus the newly inserted inserted row. This obviously means that the cost of inserting a single row can be linear in N, N being the number of elements in the newly created SSTable. This is extremely undesirable since it means that inserting N elements into the system will cost O(N²).

This is exactly where the Static To Dynamic Transform comes in super handy. You just apply the transform, and almost magically, you've gone from an overall running time of O(n²) down to O(n log n) for inserting n elements into the data structure.

Deamortizing disk writes during log rotation

According to this page on deamortization, "deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound."

Log Rotation refers to the automated process used in system administration in which dated log files are archived. logrotate is one such UNIX command that lets you perform log rotation.

Many services (daemons in the UNIX world) write out log files that need to be periodically rotated and compressed. This is achieved using the logrotate command (mentioned above). Certain tools such as multilog also assist in augmenting the log with extra information such as the timestamp, etc...

When log files are rotated and compressed, it ends up reading the complete log file from disk (if not present in the kernel caches), and using a lot of CPU for the duration of compressing the log file. Depending upon the size of the log file, this could take anywhere from a fraction of a second to 10s of seconds. If the log file is large (which is usually the case), it ends up starving other processes that need to use the disk or CPU. If the supervising process (performing the job of log rotation and compression) is synchronously reading from the daemon service's stdout/stderr, and is taking too long to rotate/compress the logs, then it will block writes to the daemon's stdout/stderr file descriptors since the pipes between the supervisor and the daemon will be full.

This can be mitigated by deamortizing the costs of log rotation/compression by writing out the compressed file incrementally instead of compressing the uncompressed log file when it is rotated and a new log file is started. This not only deamortizes the I/O and CPU costs, but also ensures that we log a lot lesser in terms of bytes (on disk). This is because we were earlier writing out the uncompressed file and subsequently compressing it and writing the compressed log file, whereas we will now only write out the compressed file (eliminating writes of the uncompressed file, which is a large fraction of total log file writes). If we write out just the compressed log file incrementally, we're saving greatly on the IO cost associated with writing out the uncompressed log file. This simple change can go a long way in helping you scale your services to be able to handle a larger number of overall requests.

Gyro balls and yoga

The Powerball is a relatively new gyro-based exercise device intended for strength building in the wrists and fore-arms. I'm using it to help me in my yoga practice.

Aasanas that require wrist and forearm strength are greatly benefited by using the wrist exercising gyro for 3-5 minutes a day.

For example, using the gyro helped me get going with hamsasana (where your fingers are pointing towards your face)

which is a lot harder than mayurasana (where your fingers are pointing away from your face, and towards your feet).

You can immediately spot the difference between the final pose for each posture.

1. In hamsasana, your body is bent at the buttocks, whereas in mayurasana, the body is mostly straight.
2. In hamsasana, your face is closer to the ground than it is in mayurasana.
3. In hamsasana, you are bent further forward (angle that the forearms make with the floor) than you are in mayurasana.
4. In hamsasana, your back is slightly more bent compared to mayurasana, where you back is mostly straight.
5. In hamsasana, your elbow is further down your abdomen compared to mayurasana, where it is tucked into your stomach.
6. Hamsasana needs more wrist strength compared to mayurasana.

To Muir Woods and back

S, V, and D went decide to bike to Muir Woods from SF Caltrain. I have a sore index finger, so this will be brief. This is the path we took in the going direction, and this is the elevation profile. On the way back we took a slightly longer route.

6:30am: Wake up.

7:55am: Leave for Caltrain Station

9:36am: Reach San Francisco Caltrain Station

9:40am: Purchase fruits and food items for the trip from Safeway


Here are our bikes:


10:00am: Start biking on The Embarcadero towards the Golden Gate Bridge



The Bay Bridge is on the way:


Some other exhibit. Looks like an arrow facing the ground:


10:05am: Arrive at The Bike Hut since V forgot their helmet at home The guy at the bike hut too a while to inflate his shop, but once he was done, offered V a helmet gratis. Very kind man.

Don't remember when, but reached the Golden Gate Bridge (south side) and then biked across to the north side of the bridge. This was fun. Didn't take any photos since there was quite a bit of uphill and we didn't think of taking photos at that time.

We reach the north side of the bride and rest for a while. Then take the road on to Sausalito. This road is marginally uphill but mostly downhill. I don't enjoy the downhill as much in fear of having to bike back up :-p

Reach Sausalito and can't believe the breathtaking views from the place.




Someone is flying a Quadcopter here as well. The battery life on these seems to be ~20 minutes. The owner prefers to use it just for 15. That's 25% energy wasted. Greenpeace, are you listening??




We keep biking along the coast (Bridgeway) and eventually cross 101 at some point in time. Then on to Mill Valley-Sausalito Path, and then left on to Sycamore Ave. Nothing particularly interesting between Sausalito and now.

We have to constantly consult our maps because the road is no longer just a straight road. We're afraid of taking a wrong turn and biking in the wrong direction. The constant checks make biking frustrating and makes us uneasy. V suggests investing in a phone holder for bikes. I provide a node of approval.

Our first reality check is at Molino Park where we wonder how far we want to go since the uphill slopes have been tiring. V's determination and unwillingness to give up inspires me. We turn on to Edgewood Avenue with renewed energy and determination.

1:30pm: We reach the tip top of Sequoia Valley Road, and the views are just breathtaking. S reaches shortly after. I've dismounted and crossed the road and am already taking photos.




The road ahead is ~700ft of pure downhill pleasure (which means uphill on our way back). S asks if we want to continue on and whether we'll be able to make it back in time. I make some quick approximate calculations and boldly suggest that we should be back by 5:30pm. Sounds like an estimate for delivery on a software project. Read on to find out what happens next.

V arrives and we unanimously decide to continue (against my better judgment, but hey, I did want to visit Muir Woods too :-p). The next ~7 minutes is just pure downhill orgasmic thrill.

Muir Woods Visitor Center is here. We decide to stay till 2:30pm. We have a Bartlett Pear each. V needs caffine in their blood, so we stop for a coffee break.

There's a tiny bridge over a stream and a lot of visitors!






And some #firstworldproblems:
2:45pm: And we're back on the road. This is an ~700ft ascent, and we do it fairly slowly.

3:15pm: The view at this time of the day on the tip top of Muir Woods Road is breathtaking.





V's bike:


3:30pm: There is a slight hiccup when we don't know which road we are on. We think that gmaps is showing us the right road, but the road sign seems to be wrong. We ask a tired runner, and he guides us. We later realize that the road name changes, and gmaps doesn't show where this transition happens. This can get confusing.

4:05pm: We stop at a place where we see a sea-plane and contemplate taking it :-p We also see a helicopter landing there. We all unanimously decide to take the ferry back from Sausalito to Pier39. S is the only one with power in their cell phone. The next ferry is at 5:35pm, and it will take us ~30 minutes to get there according to gmaps. We amble our way to the ferry terminal.

4:45pm: We;re almost at the ferry terminal when S spots R and family. We're pleasantly surprised by the meeting and exchange pleasantries and indulge in small talk.

5:00pm: We head to the ferry terminal and stand in line with the rest of the bikers. S determines the status of tickets and gets a Clipper Card. S tells V that tickets cost $4.25, but the clipper card needs $10.25 balance. I am unsure if I have that sort of cash, but I assume that I can refill my card. I ask S some more questions since I am confused about what is going on. S is searching for their Caltrain ticket. S and I need to communicate more. I have a hard time understanding things and S thinks I am smarter than I am.

5:20pm: The line moves forward, but the ferry is filling up fast. I see a ticket window and wonder why we aren't buying tickets. Everything seems bizarre to me. S then explains that we can clip on on the ferry and that $10.25 is the cost of the ferry and $4.25 is the minimum balance required. I really need to find a good way to communicate with S. We casually joke that we shouldn't be the first ones in line for the next ferry.

We are the first ones in line for the next ferry. Never has a STOP sign hurt so much.


5:45pm: We wait for the ferry to leave (since it isn't over till it's over), and start biking back. I am somewhat pleased that we aren't waiting for the next ferry, which is at 6:45pm.

Sausalito uphill seems easier than the one on Muir Woods Road. We are all pretty tired.

6:00pm: We've reached a point in the road where we need to decide whether we should turn right or go straight. I remember turning left after emerging from a tunnel on our way here, so I suggest turning right. I check the map for good measure, and it looks okay. The is my first blunder. We turn right into a tunnel that's longer than any other tunnel we've taken so far and find ourselves on Bunker Road. Phone doesn't have data, but the GPS is able to tell us where we are. We can't route back so we decide to retreat back into the tunnel we came from.

6:05pm: We;re back at the mouth of the tunnel, and we decide to route back to SF Caltrain. gmaps will suggest a path that doesn't exist. We don't know this, so we take the path. On the way down (which is a steep downhill), S suggests that they don't remember gaining so much altitude on the way up. We're halfway down. I completely agree with S, but don't have a better idea, so I don't stop. This is my second blunder. We find ourselves at the bottom of the Golden Gate Bridge. The view is majestic.




We crawl back up to the Golden Gate Bridge and realize that we have to cross since the west side of the pedestrian/bike path is now closed and we need to go over to the east side. My 5:30pm estimate has been blown to bits.

7:05pm: We take a short break to determine when we'll reach Cafe Chaat (dinner!!). I speculate another 20-25 minutes to reach Cafe Chaat.

7:55pm: We reach Cafe Chaat. Dinner is on the menu :-p

9:15pm: Take the last Caltrain back (it's Sunday).

Making soft chapatis that balloon

I've been making chapatis for a while now, and conventional wisdom says that getting the dough well knead is the key to soft chapatis since it forms the gluten strands in the dough and makes it tough. I very recently chanced upon the real method to make soft pliable dough that also results in chapatis that balloon even under sub-optimal rolling.

The key is to knead the dough in salty water. Take some salt (to taste) and mix it in some water (at room temperature). When the salt has completely dissolved in the water, use that water to knead your dough. You will find it much easier to knead your dough, and it will result in a soft pliable dough that is somewhat forgiving of mistakes (or chapati got stuck to the rolling pin and folded over itself) while rolling.

I additionally add some turmeric and red chilli powder to my dough for enhanced taste and colour! :)

Merging AVL Trees

Problem Statement: Given two AVL trees T1 and T2, where the largest key in T1 is less than the smallest key in T2, Join(T1, T2) returns an AVL tree containing the union of the elements in T1 and T2. Give an algorithm (in pseudocode) for Join() that runs in time O(log n), where n is the size of the resulting AVL tree. Justify the correctness and efficiency of your algorithm.

Problem statement and solution stolen from these assignment solutions.

Solution: Begin by computing the heights h1 of T1 and h2 of T2. This takes time O(h1 + h2). You simply traverse a path from the root, going to left child if the balance factor is -1, to the right child if it is positive, and to any of the children if the balance factor is 0, until you reach a leaf. Assume that h1 > h2; the other case is symmetric.

Next, DELETE the smallest element x from T2, leaving T'2 of height h. This takes O(h2) time.

Find a node v on the rightmost path from the root of T1, whose height is either h or h + 1, as follows:

v = root(T1)
h' = h1
while h' > h + 1 do
  if balance factor(v) = -1
  then h' = h' - 2
  else h' = h' - 1
  v = right-child(v)

This takes O(h1) time.

The reason we choose a node with height h or h + 1 is because if we are at a node of height h, and we move to its parent node, then the height of the new (parent) node might increase by 2 (to h + 1), since the sibling of node from which we moved up might have a height greater (by 1) than its sibling.

Let u denote the parent of v.

Form a new tree whose root contains the key x, whose left sub-tree is the sub-tree rooted at v and whose right sub-tree is T'2.

Note that this is a valid binary search tree, since all the keys in the sub-tree rooted at v are in T1 and, hence, smaller than x, and, by construction, x is smaller than or equal to all elements in T'2. The balance factor of the root of this new tree is h - h' which is either -1 or 0, so this new tree is a valid AVL tree. The height of this new tree is h' + 1, which is 1 bigger than v's height. Let the root of this new tree be the right child of u, in place of v. Again, since all keys in this new tree are at least as big as u, this results in a valid binary search tree. This part of the construction takes constant time.

Now, as in the INSERT algorithm, we go up the tree, starting at u, fixing balance factors and perhaps doing a rotation. This takes O(h1) time. Note that the correctness follows from the condition at u before this process is begun is a condition that can arise during the INSERT algorithm.

Since h1, h2 ∈ O(log n), the total time taken by this algorithm is in O(log n).

Better algorithms v/s micro-optimization

As a kid, I participated in a game that involved bouncing a tennis ball on the ground using your hands. The winner was the one who was able to bounce the ball the most number of times in 60 second.

All the little ones (including me) went first (since the game was primarily meant to keep us busy). I was top scoring with a little over 70 bounces in 60 second. What I did to get there was try and go as fast as I possibly could without losing control of the ball, and focusing heavily on where the ball was at all times.

Then the grown-ups started and for a while no one was able to beat that score. Then one smart dude knelt down when the signal to start was given. Everyone else had already started bouncing there balls and were in to their second bounce, and this guy was taking his own time getting settled in his squatting position. When he was ready, he started bouncing the ball, and boy did he go fast! He had just out-smarted everyone else with a better algorithm for getting more bounces in the same time duration.

Better algorithms are like bicycles for the mind.

Before we had sorting algorithms that ran efficiently [O(n log n)], we had micro-optimizations applied to every known O(n²) sorting algorithm in an attempt to make it perform fewer comparisons, or exit early, and hence run faster. Fixing the algorithm, however, was the real game changer.

Javascript as a language is really darn good

If you look at computer languages as tools to help you convert thought to code (ignoring other real-world practical considerations such as efficiency, developer availability, platform pervasiveness, library availability, etc...) then my opinion is that Javascript (in the form of node.js as we know it today) really stands out. Let me explain why I feel so.

1. Javascript is a small and minimal language with few (redundant) constructs and can be taught and remembered easily. This is useful for someone who is trying to use javascript to write code as well as someone who is trying to read javascript code. When you are expressing your ideas, you want to know what tools you have and want to be able to fit them in your head. At the same time, when you (or someone else) (re)visit(s) your code, you want the reverse transfer of information (i.e. code to idea) to be quick and unambiguous and the reader shouldn't get confused trying to figure out the language syntax and semantics. To explain,
   
   
   • The fact that functions are first-class objects and that the lambda syntax isn't different (or otherwise special) compared to the standard function definition syntax helps.
   • As does the fact that objects/maps (hashes), arrays, etc... all have the same get/set syntax.
   
   
2. There's very little fluff in the language. Most keywords don't feel like they're useless. The only ones I find excessive are 'new', 'prototype', and 'function'. Coffeescript solves this to some extent.

What this means is that it's very easy to get started with your first program once you have an idea of what it is that you want to express in code. Javascript lends itself well to elegant code.

Since there is no main() function in a node.js script, you don't need to encode all your executable code in a main() function. You won't believe how incredibly useful I find this even though I have programmed in C and am used to that style of programming. This also means that each file can have its own test() function that is run by just invoking:
$ node file_name.js.

Declaring arrays and objects (maps) in javascript is really easy, and anything that can be reasonable done in 1 line is done in one line. For example, declaring an array a that has 4 elements, 44, 31, 21, and 23 is:
var a = [ 44, 31, 21, 23 ];

Declaring an object o that maps key 'name' to 'blogger', key 'url' to 'http://blogger.com/', and key 'age' to 5 is as simple as:

var o = {
  'name': 'blogger',
  'url': 'http://blogger.com/',
  'age': 5
};

Notice how values in maps can be of different types. This is also true of elements in an array.

Converting a string (or any other type) to a string isn't rocket science either.
var sint = String(89);

To test my belief, I've started writing a toy regular expression parser and evaluation engine in javascript that will have some intentional holes (un-impelemented features) that you can fill up later so that you can get a feel for both how regular expressions work, as well as how javascript as a language handles.

Inside the guts of Kadane's algorithm OR Understanding the Maximum Sum Subarray Problem

Kadane's algorithm is used to solve the 1 dimensional Maximum Sum Sub-array Problem in computer science.

Let's try to understand how it really works. If we are given the problem of finding the maximum sum sub-array of a given array, the first native approach we can try is the O(n²) algorithm of starting at every array index and computing the sum from that index to every index after it. This works, and gives us the correct answer, but we should ask ourselves if we can exploit certain properties that the problem might have to try and speed up the solution.

Let's try and dig deeper into an example.

Consider the following array & its corresponding cumulative sum subarray:

Element	10	-5	-2	7	1	-5	-3	2	4	-3	6	-21	5	-2	1
Cumulative Sum	10	5	3	10	11	6	3	5	9	6	12	-9	-4	-6	-5

Some observations:

1. A maximum sum sub-array can never have a negative number as one of the elements at the end-points, except of course if every element in the array is a negative number. If a maximum sum sub-array had a negative number on one of its end-points, we could remove that element and increase the value of the sum, thus getting a sub-array with a larger sum. Conversely, a maximum sum sub-array always starts and ends with a non-negative number, unless of course all the numbers in the array are negative.


2. We can always clump all negative and non-negative numbers together since once we encounter a negative number, the sum always drops and once we encounter a non-negative number, the sum never drops.


3. If the running sum of a sub-array array ever falls below zero, no solution will ever include the negative number that caused this sum to fall below zero since it over-powers the positive sum accumulated before it. Note: We only speak of 1 negative number because of the clumping point above.


4. An extension of the point above implies that the new running sum that begins once a cumulative sum falls below zero always starts from the immediately following non-negative number.

Applying the rules above, we get the following recurrence:

MaxSum[i] is the Maximum Sum ending at index i.

MaxSum[i] = Array[i]                if i = 0
MaxSum[i] = MaxSum[i-1] + Array[i]  if MaxSum[i-1] + Array[i] >= 0
MaxSum[i] = 0                       if MaxSum[i-1] + Array[i] < 0

The re-written array (which now consists strictly of alternating negative and non-negative numbers) and the new cumulative sum sub-array are (the row "Cumulative Sum" below represents the MaxSum variable above):

Index	1	2	3	4	5	6	7	8	9	10	11
Element	10	-7	8	-8	6	-3	6	-21	5	-2	1
Cumulative Sum	10	3	11	3	9	6	12	0	5	3	4

How to give a talk/presentation - Wisdom from Dr. Bender

(The content of this post is mostly stolen inspired by this post by my friend Deepak.)

This Spring, I took a course called CSE638 (Advanced Algorithms) under Professor Michael Bender. This was a mostly research oriented course, with a focus on doctoral students. An important part of doing Academic Research is talking/presenting your material in conferences and seminars. Professor Bender spent a couple of classes discussing this, and I thought I'll list down the stuff he mentioned - more of a note to myself.

1. Make the talk prefix-competitive
   If somebody dozes off, the person should have got the best part of your presentation/content before he/she dozed off. Bring the best part of your talk to the front. Make it prefix-competitive.
   
2. Stand in front of the screen, Smile :)
   Do not stand away from the screen, in some corner behind the podium. Stand in front of the screen. Let the Projector's display glow on your face. Stand confidently in front of the screen - okay now, don't block the screen, but stand to the edge of the screen, and Smile while you speak. Convey enthusiasm. "People like seeing faces". Facebook has become popular for a reason ;)
   
3. Diagrams and Figures!
   Have plenty of diagrams and figures on each slide.
   
4. Refer to every slide & everything on each slide
   Refer to each and every item on your slide. If there is a diagram, explain everything. If you're not going to explain something, refer to it and say that you're not going to explain it. Either way, please do refer to everything on your slides!
   
5. Touch the screen, point to it
   Don't be afraid of the screen. Touch it. While explaining the diagrams and figures, stand over the screen and explain stuff by physically touching the screen with your fingers/hands. That very act conveys confidence.
   
6. Results Up Front
   If your talk is about the results, let the results be as far upfront as possible. Build the context as soon as possible, and announce what you did.
   
7. Explain the Title
   Spend time explaining the title. And the background. This might seem to conflict with point-4, but it's not. That's the trick.
   
8. Give credit wherever possible, and do this in the beginning
   When giving credit to others, please try to do this when you start rather than when you end. People like hearing about other people. Did I mention something about facebook earlier?
   
9. Explain why the problem is important
   This I feel is one of the biggest take-aways from the talk. Even if the audience doesn't understand the solution, they should understand why we need a solution in the first place.
   
10. Make use of plots effectively
    Explain the axes, and know what to plot. Refer to this post by Gaurav to know more about what this means.
    
11. Know your audience
    For example, presenting the workings of a toaster to a homemaker is different from presenting it to an electrical engineer. You'll need to motivate the problem differently in both cases. Same goes with presenting it to someone who has had a toast before v/s someone who hasn't. I find that Dr. Dan Gusfield does a brilliant job of motivating problems before presenting the solutions (related to point-7).
    
12. There are a couple more about Jokes, Color Schemes, etc. which I can't recall.

There now, nobody can stop you from giving an awesome talk!

PS - If you're from Stony Brook, and find that I've missed something, feel free to write in the comments. Thanks!

Update: Found this article online.

PMA: The Packed Memory Array

Thanks to Deepak & Gaurav for proof-reading this post and providing useful feedback!

The Packed Memory Array (pdf) is an interesting structure to say the least, since it keeps its elements almost contiguously (and in sorted order) in memory with no additional indirection via pointers like a usual array and still allows one to perform fast - O(log²N) - updates to the array.

We know that inserting elements in sorted order into an array without keeping gaps between consecutive elements costs O(n) per insert, whereas searching for an element can be done using binary search with a cost of O(log n). These are tight upper bounds, but the story is a little different for randomly arranged data. If one is inserting random data into a sorted array with gaps being maintained between consecutive elements, the expected time to insert a single element magically falls to O(log n)! Now, what just happened here? To find out, read more in Bender, Colton, and Mosteiro's paper titled Insertion Sort is O(n log n) (pdf). On the other hand, if we don't permit gaps between elements, even for random data being inserted, the amortized cost for inserting n elements into an array in sorted order is O(n²) - why? (hint: Refer to the expected case analysis of quick-sort).

The simple idea is to not pack all elements together, but to maintain some gap between consecutive elements. We shall see that if we follow this simple idea, then the cost for insertion falls to O(log²n) amortized worst-case. This is the packed-memory-array (PMA). We however need to formalize the idea a bit and set some rules of the game before we get ahead of ourselves.

We'll start off by assuming that we already have a PMA that holds n valid elements. One of the invariants we have for the PMA is that it should be more than 0.25x full (this is called the fullness threshold). i.e. If the PMA has space for 4n elements, then there should be at least n actual elements in the PMA. Any less and we should re-size the PMA to have space for 2n (not n) elements (this is also part of the fullness threshold). The reason we maintain extra space in the PMA is so that we can re-balance and that re-balances involving a lot of elements won't happen too frequently.

Let's just focus on insertions for now. The PMA is organized as a contiguous array of slots which might be used or free. Conceptually, we break this array of size N into N/log N blocks, with each block holding log N elements. We'll see why this is helpful. If we look at a PMA as being made up of such blocks of size log N each, then we can view the PMA as binary tree (conceptually) with each level having different fullness thresholds.

The algorithm for inserting elements relies heavily on the upper density threshold whereas the algorithm for deleting elements relies heavily on the lower density thresholds. For the sake of brevity, I shall only discuss insertion (not deletion).

Algorithm: When we insert elements into the PMA, we follow these steps:

1. Locate the position to insert the element into. We either know this before-hand or we perform a binary search which costs O(log²N).
2. If the cell we want to insert into is free, we just add the element, and mark the cell as used. We are done!
3. If however, the cell is used, we compute the upper density threshold for the smallest block (of size log N) that the desired cell falls within, and check if the upper density threshold would be violated. If we notice that there is no violation, we just re-balance all elements including the new one into that block. We are done. If we violate the upper density threshold, we consider a block twice as large (which includes the cell we will be inserting into) and check if the density threshold is violated. We repeatedly move up till we find a chunk for which the upper density threshold is not violated.
4. If we fail to find such a chunk, we just allocate an array twice as large and neatly copy all the existing elements into the new array with constant sized gaps between elements!

Analysis: We analyze the cost to insert an element into the PMA.

Pre-requisite: Weight balance for fun and profit

1. The upper (and lower) density thresholds are arranged so that they grow arithmetically from the top (root) level to the bottom (leaf) level.
2. The difference in density thresholds is 0.5, and we have log N levels, so if we want to maintain a constant arithmetic difference between levels, there must be a difference of 0.5/log N between each level. This is a difference of Δ = O(1/log N) between each level.
3. Q. What is number of elements that should be inserted at a certain level to bring it out of balance?
   A. Clearly, if a level has room for N elements, and it is out of balance then that could have happened only if it went from being in balance to now out of balance, which means that O(ΔN) elements were inserted into this level.
4. Q. What is the number of element moves we need to bring a level back into balance?
   A. If a level is out of balance, we typically go up till a level within density thresholds is located and re-balance it. Ideally, going up one level should do the trick, so to re-balance a level containing N elements, Θ(N) operations are sufficient.
5. Therefore, the amortized cost to re-balance a level is O(N / ΔN) = O(log N).
6. However, we must not forget that an element insertion affects the thresholds of O(log N) levels, which means that the actual cost for insertion is O(log²N).

You can also read about the analysis in section-4 of another paper.

Q1. What if we use space proportional to Θ(N^c) (assume c=2) to store N elements? What happens to the running time for insert?

A1. Well, it just goes over the roof since you're now going to be moving elements across a lot of unused cells while you re-balance the array. Additionally, you'll also need to to adjust your level density thresholds to not be arithmetically increasing, but geometrically increasing. Instead, if you use tagging and maintain elements as tags and pointers to actual values, you can get better running times if the tag space is polynomial (N^c) in the number of elements in the structure.

Q2. Is the PMA a cache-oblivious data structure?

A2. The PMA is Cache Oblivious, and is used as a building block in other more complex external memory data structures such as the Cache-Oblivious B-Tree.

Implementation: You can find a sample implementation of the PMA here.

Weight Balance for fun and profit

According to Dr. Bender, Weight Balance (different from the wikipedia article on weight-balanced tree) is one of the most important topics in Computer Science, and we were lucky enough to learn it from him! Others might not be so lucky, so let me try and do a job that's hopefully a constant factor (or fraction) as good - since it won't matter because all we care about are the asymptotics.

Pre-requisite: This note on Amortized Analysis.

We'll use weight balance to implement a dictionary structure and examine how the guts of one such structure, the weight-balanced tree work.

A dictionary data structure is one that supports the following dictionary data structure operations:

1. Insert
2. Delete
3. Find
4. Predecessor
5. Successor

Points 4 & 5 are what distinguish a dictionary data structure from a keyed data structure such as a Hash Table.

Now, you might have heard of the following data structures that (efficiently) support the operations mentioned above:

1. Treaps
2. Skip-Lists

It would surprise (or maybe not) you to know that both these structures work on the principle (guess) of weight-balance!!



So what exactly do we mean when we talk about the weight of a sub-tree in a BST? Well, as it turns out, the weight of the sub-tree in a BST is just the count of the number of nodes in the sub-tree rooted at that node (including the node itself).

For example, the following tree (image courtesy wikipedia) has a weight of 9
and the sub-tree rooted at node 10 has a weight of 3.

A weight-balanced tree rooted at node u is one in which (either):

1. The weights of the left and right children of a sub-tree are within constant factors of each other:
   weight(Left-Child(u)) + 1 = Θ(weight(Right-Child(u) + 1)
   Note that the +1 is important for pedantic reasons as far as the order-notation is concerned.
   OR
2. The weights of the left and right children of a sub-tree are within constant factors of the weight of the complete sub-tree
   weight(Left-Child(u)) + 1 = Θ(weight(u) + 1) AND
   weight(Right-Child(u)) + 1 = Θ(weight(u) + 1)

It turns out that both these definitions are equivalent.

More realistically, if we stick to the second definition, we have:
weight(Child(u)) + 1 ≥ 0.25 * (weight(u) + 1) AND
weight(Child(u)) + 1 ≤ 0.75 * (weight(u) + 1)
where, Child(u) denotes both the left & right child of u.

For example, if we consider the following example tree, which is clearly out of weight-balance (don't ask me how we got there because this example is made-up), we re-balance it to be perfectly in balance (if we have an odd number of nodes or almost perfectly balanced otherwise).


We should be careful about how we re-balance these N nodes, because if the cost is any worse than Θ(N), then we won't get the update costs that we desire. The easiest way to perform the re-balance with a cost of Θ(N) is to perform an in-order traversal of the subtree rooted at node u, and write out the sorted nodes to an array. We can then re-create a perfectly balanced BST from that array either using recursion or the Day–Stout–Warren algorithm.

This is where the fun starts!!

Q 1. How many nodes need to be inserted under a sub-tree rooted at node v to bring the sub-tree out of balance (assuming it is perfectly balanced to start off with)? Let's assume that the sub-tree originally contains N nodes.
A. You need to insert some constant fraction of the weight of that sub-tree! which is Ω(N).

Q 2. What is the cost to rebalance the sub-tree rooted at node v if we know that that sub-tree has a weight of N?
A. Well, we already answered this above. The answer is Θ(N).

Q 3. How many sub-trees potentially go out of balance when you insert a node?
A. We know that a node is inserted at the leaf level, so potentially all the sub-trees that are rooted at the nodes on the leaf-to-root path with the newly inserted node as the leaf node can potentially go out of balance. This happens to be Θ(log N) nodes.

∴ the amortized cost to insert a new node into the balanced tree is:
Ω(N)/Θ(N) * Θ(log N) = Θ(log N).

Now, that's a fairly straight-forward algorithm to get the same (amortized) costs as the worst-case costs for updates with a more complicated beast such as an RB-Tree or an AVL-Tree. Though, I feel that Treaps are much simpler to implement.

Amortized Analysis or: How I learned to stop worrying and love averages

Amortized Analysis is usually seen as a pretty scary term, and I've seen a lot of people confuse it with Average Case Analysis, but let's try and de-mistyfy it, one step at a time.

We've performed amortized analysis at some point or another in our lives without actually knowing it. A few lame examples follow:

• For the stock broker: Purchasing shares at a lower price to average out the cost price of all the holdings of a given stock
• For the fitness enthusiast: Working out thrice as much at the gym today because [s]he missed 2 days before today
• For the reader: Reading a few more pages of a book so that you can take a break tomorrow and still complete it on time

There are situations where amortized analysis doesn't work too. For example, suppose you're in charge of cooking for your family, you can't say that you'll cook thrice as much on the 3rd day from today and not cook at all between now and then. Sorry, but sometimes it just doesn't work!! These are cases where you must use worst-case bounds.

Let's try some exercise and learn by example!

1. Ex-1: You're jogging 16 miles every day for 8 days, and your friend jogs 8 miles and 24 miles on every odd and even numbered day respectively (starting from day #1). Who jogs more over a period of 8 days? Here is a graphical representation of how much you and your friend ran over a period of 8 days:


2. Ex-2:You're jogging 16 miles every day for 7 days, and your friend jogs in the following manner:

   Day	Miles Jogged
   1	2
   2	2
   3	4
   4	8
   5	16
   6	32
   7	64

   
   Who jogs more over a period of 7 days?


3. Ex-3: You're playing a game where you have a graph and you start at the node with the symbol S and finish at the node with the symbol F. The constraints on your moves are that you must take EXACTLY ONE blue coloured edge in every move, but you can take as many (or zero) red coloured edges in a move. A move contains a combination of red and blue edges.
   An example graph is shown here: One trace of a successful completion of a game that visited 11 blue edges and 4 red edges is shown here: Can you identify the maximum number of edges of any colour that will ever be visited if I tell you that exactly 107 blue edges were taken in a particular successful completion of the game?

If you got this far, and were able to solve all the exercises - congratulations! - you've understood what amortized analysis is all about! And as an added benefit, Ex-2 is how one would go about analyzing the insertion cost for Dynamic Arrays, and Ex-3 is actually how one would analyze the running time for the KMP string matching algorithm!

PV=nRT or: How I learned to stop worrying and love cooking under pressure

I'll try to be as brief as possible here. Just going to talk about the physics behind Pressure Coking and why it's so cool (and hipster). Hey, it saves fuel and hence damages the environment to a much lesser much lesser extent than does normal cooking.

From How Does A Pressure Cooker Work?: "Simply put, water boils at 212°F (100°C). At this point, no matter how long you continue to boil, it always stays the same temperature. As the water evaporates and becomes steam it is also the same temperature, 212°F.

The only way to make the steam hotter (and/or to boil the water at a higher temperature) is to put the system under pressure. This is what a pressure cooker does. If we fit an absolutely tight cover to the pan so no steam can escape while we continue to add heat, both the pressure and temperature inside the vessel will rise. The steam and water will both increase in temperature and pressure, and each fluid will be at the same temperature and pressure as the other. "

To explain the last paragraph above, let's turn to physics and the Ideal Gas Law, which states that PV=nRT where,

P	=	Pressure
T	=	Temperature

and we don't really care about what the other symbols mean.

This means that Pressure and Temperature vary directly with each other, and if you raise the pressure of a fluid, then the temperature at which it changes state will also increase!!

Parvorder Platyrrhini or: How I learned to stop worrying and love monkeys

As usual, this is going to be short.

I was coming back by train from Charni Road to Churchgate after a swim at Mafatlal Bath when an eunuch with a baby monkey (maybe less than 2 years old) walked in and started asking for money.

At first, I just ignored them since I had something going on in my head, but eventually they got my attention when the monkey started acting acrobatic in the train and started swinging from pole to pole and climbing the inner walls of the railway carriage (bogie in India).

I walked towards them and quietly handed the owner a ₹5 coin (that's about $0.1). What followed was pure ecstasy! The monkey climbed on me starting from the feet upwards and used my shorts and tee-shirt as support. I found it lodged in my arms like I would hold a human baby. It then walked all over my shoulders and lodged itself on my head (I had just cut my hair super tiny, so I guess that helped). It sat there patiently; probably observing the people around. I'm sure that the others felt as if I was the owner of the monkey! Never ever have I had something like this happen to me, so I was absolutely overjoyed with the proceedings. I wasn't even worried about getting all dirty right after my swim because this was just as fantastic a feeling as I could (not) think of!

Eventually, it was time to step off the train and the owner of the monkey started tugging at its leash, but the monkey would not budge! ha! After a few sharp tugs though, the baby relented and it was time to part ways.

Reminds me of:

A great day for freedom

Today, I took Abbas, my dear dear dear friend (and a Muslim) to a pool where for the longest time, only Hindus were permitted to congregate and bathe. Only for the last 2 years has this ban on other religions been lifted (which I felt was unhealthy to start off with). Sense has been knocked into certain quarters!

It feels quite liberating to be able to have the option of not worrying about religion, etc... before associating with people. It's a person for crying out loud!! I remember my days in school where we didn't know anything about the concept of religion and never ever let that feature in the equation of friendship or acquaintanceship.

Why did we let religion govern our lives and let it stop us from doing harmless things we otherwise would have?

हिन्दू, मुसलिम, सिख, इसाई हम सब भाई भाई हैं ।

Better Index Compression

It's late, so I'll keep it short and to the point.

An index is something that lets you get at data quickly. I consider a B-Tree as well as a sorted array an index. The time to lookup an element in an array is O(log₂ N) whereas that in a B-Tree is O(log_B N), where N & B mean their usual things.

1. If we just consider static structures (sorted array for example), and we wish to compress the data but maintain the retrieval speed, one can think of compressing blocks of size B and then performing a binary search over blocks. There are O(N/B) such blocks, so the cost of performing a binary search is O(log₂ N/B), which involves decompressing O(log₂ (N/B)) blocks of size B each.
   
   Instead of B, if we chose O(log₂ N) elements to fit in a block (intuitively, assume that O(log₂ N) = kB, for some constant k > 0), we land up with O(N/log₂ N) blocks, each of size O(log₂ N), and the asymptotic cost to query remains the same, but we decompress O(log₂ (N/log₂ N)) blocks this time, which is asymptotically better than before.
2. If OTOH, we sample out every O(log₂ N)^th element from the sorted array, and create an uncompressed array from these elements, and make each element point to a compressed block containing all the elements between this element and the next element, then each element points to a compressed block containing O(log₂ N) elements.
   
   Queries can be answered by performing a normal binary search on the array of sampled elements, and then at most 1 decompression operation is sufficient to locate the element in the compressed block. This is better than the O(log₂ (N/log₂ N)) blocks we had to decompress in the earlier scheme. The asymptotic cost of a query remains the same but we gain a lot by performing exponentially fewer decompression operations!!
   
   Credits to Anirban for this explanation: Another way to look at it is to imagine a B-Tree built from these sampled elements, and each node in this B-Tree points to a compressed block containing O(log₂ N) elements. Alternatively, this can also be seen as a B-Tree built in such a way that internal nodes are stored uncompressed, but the leaf nodes are stored compressed.