Apps Contact Seminars

Archive for February, 2011

February 24th, 2011

Online Algorithms

The past two Wednesdays, I covered two guest lectures at GWU for an advanced algorithms class.

I absolutely loved it (as many of my students who know me well would easily guess!) Also, I found that many doctoral students enjoy online algorithms, but may have limited exposure to it.

Presentations can be found here.

Had many detailed discussions with very enthusiastic student, and some of them had suggestions which may have significant impact for online algorithms in machine learning.

Tags: ,

February 17th, 2011

Finding the smallest and the largest number from an unsorted array

#cs6212gwu – Spring 2011 – HW1 – Q4

This is a common puzzle.  Given an array of n sorted numbers, how to find BOTH the minimum and the maximum using as few comparisons as possible.  If only the minimum (or the maximum) is to be found, then that can be done by using n-1 comparisons.  So, the first algorithm could be to find the minimum, and then to find the maximum from the remaining, in a total of (n-1) + (n-2) comparisons.

A better algorithm is that we first compare pairs of numbers (in n/2) comparisons, and collect n/2 “winners” and n/2 “losers”.  Then, find the maximum from the winners, in n/2 – 1 comparisons, and the minimum from the losers in n/2 – 1. That is a total of 3n/2 – 2 comparisons.

So much is straightforward. Much more interesting question arises, if we ask:

Is the algorithm presented above optimal?  In other words, can we say that any algorithm that is based on comparisons will need at least 3n/2 – 2 comparisons, regardless of in which sequence it does the comparisons.

We want to prove that for any given algorithm (let us call it algorithm A), there is a sequence of numbers for which A takes at least 3n/-2 comparisons to find both the maximum and minimum numbers.  Such a proof can be constructed based on adversary (or game theoretic approach); essentially saying that an adversary will actively work against the algorithm to maximize the number of comparisons needed, but with the condition that the adversary cannot contradict itself.  For example, adversary cannot say a > b, b > c and then also say c > a.

Adversary thinks in terms of numbers in 4 buckets:

• Bucket Q – contains numbers that have never been compared to anything yet.
• Bucket W – Contains numbers that have only won games that they have played.  So, they are candidates for being the maximum.
• Bucket L – Contains numbers that have only lost games that they have played.  So, they are candidates for being the minimum.
• Bucket X – Contains numbers that have both won and lost games they have played.  So, they are not candidates for being the minimum or the maximum.

These buckets start with the following state when the algorithm A starts:

Bucket Q: n numbers, Buckets W, L, X: 0 numbers each.

Finally, when algorithm A finishes, this must be the state:

Bucket Q: 0 numbers; Bucket W: 1 number; Bucket L: 1 number; Bucket X: n-2 numbers

Adversary goes by the following rules for creating outcomes of comparisons:

• C1: When comparing two numbers in bucket Q – one number will go into W bucket, and one number will go into L bucket.  (Net change: -2, +1, +1, 0)
• C2: When comparing a number from W bucket to a number from Q bucket, the number  from W will win and will remain in W.  Number from Q bucket will go into L.  (Net change -1,0,+1,0)
• C3: When comparing a number from L bucket to a number from Q bucket, the number  from L will lose and will remain in L.  Number from Q bucket will go into W.  (Net change -1,+1,0,0)
• C4: When comparing a number from W bucket to a number from X bucket, the number  from W will win and will remain in W.  Number from X bucket will remain in X.  (Net change 0,0,0,0)
• C5: When comparing a number from L bucket to a number from X bucket, the number  from L will lose and will remain in L.  Number from X bucket will remain in X.  (Net change 0,0,0,0)
• C6: When comparing a number from W bucket to a number from L bucket, the number  from L will lose and will remain in L.  Number from W bucket will remain in W.  (Net change 0,0,0,0)
• C7: When comparing two numbers from W bucket, one will remain in W, and one will go into X.  (Net change, 0, -1, 0, +1)
• C8: When comparing two numbers from L bucket, one will remain in L, and one will go into X.  (Net change, 0, 0, -1, +1)

These rules ensure the following points:

• Maximum of 2 numbers can be removed from Q bucket during each comparison, and during this comparison, no number goes into the X bucket.   [This happens in comparison C1.]
• During each comparison, maximum of 1 number can enter the X bucket.  [This happens in comparisons C7, C8, and in those comparisons, there is no change in the size of the Q bucket.]

So, we observe that we need n-2 comparisons (of type C7/C8) simply to fill up the X bucket (we need n-2 numbers there by the end).  Further, since those comparisons do not involve Q bucket, we need at least additional n/2 comparisons just to empty out the Q bucket (it starts with n numbers and needs to have 0 numbers).  So, in total, we need to make at least 3n/2 – 2 comparisons just to make sure Q and X buckets have the desired state before algorithm A can draw its conclusions.

QED.

February 12th, 2011

Saturday Morning Puzzle – Cars and HoV

Here is a simply and mildly practical problem.

Say, I-66 is jam packed. (Oh wait, supposition not needed.  It is jam-packed – any day, any time.)

Suppose, HoV lane is moving freely.  (Supposition needed along with prayer.)

So, your idea is that you could let a small number of lucky vehicles into the HoV lane, and still not overcrowd HoV, while at the same time alleviating some congestion from the main lanes.  How do you do it?  Keep in mind, you can’t say every “3rd” car, since every car is a 3rd car depending upon who is doing the counting.  So, your method must be deterministic based on the car.  Secondly, you should be able to change your method next time this lucky scenario happens.  Thirdly, it would be nice if there was a way to easily confirm the criteria from a distance.

Tags: , ,

February 7th, 2011

IBM, Oracle and other analytics spammers

I have high respect for the stock prices of IBM and Oracle.  But in operational sense, they are no different from much smaller establishments.  In some sense they are much worse, because they claim to be the “analytics”, “decision” and “real-time” powerhouses, while having as much difficulty processing an unsubscribe request as your local florist.

I recently attended an analytics conference, and in a moment of keynote induced dizziness, swiped my conference card at Oracle and IBM booths.  Since then, I have been flooded with their real time analytics “innovations”.  Following the unsubscribe links doesn’t really help.  Even though you do get a confirmation message, you continue to get the emails even weeks later.  (Perhaps they use a different scale for “real-time”.)  Oracle has problems with creating a working user-interface for unsubscribe requests as well.  They do have an “Opt-Out completely” link, and this is where it brings you to:

There are only 3 triggers on the page: “login”, “create account” or “update profile”.  “Update profile” link brings you to the login page, and after you login, there is no Opt Out option.  So, while Oracle respects your right to unsubscribe, it has conveniently forgotten a mechanism that allows you to exercise that right.

Some convenience, and some UI designers.

Tags: , ,

Switch to our mobile site