Sunday, October 18, 2009

MSc then PhD?

Typical situation: Hamdy was a top ranked student in his university, in a developing country, and now he'd like to get a PhD from a good university in US/Canada (with financial aids). He has two options:

  1. Apply for a PhD.

  2. Apply for an MSc. And after getting the MSc degree, he applies for a PhD.

Why would Hamdy go for option 2:

Avoid frustration
MSc is less of a commitment than PhD. It's easier to work on, and takes much less time to get done. However, it gives a clear idea on how Hamdy's life is gonna be as a PhD student. Given that 50% of PhD students in some fields drop out before completing their degrees, this becomes a significant consideration. Hamdy prefers to go for the less risky degree (ie. MSc) and then decides whether he should continue for a PhD or get a good job in the industry with his MSc degree, from a good university in US/Canada. I know one person who left PhD for the industry, and many PhD students who consider doing the same.

Chances of acceptance
MSc is less of a commitment than PhD, this holds true even for the admission committee of the university he applies for. Several persons I know applied for a PhD and were offered only an MSc. So, applying for an MSc would increase Hamdy's chances of getting admitted for graudate education.

Improve credentials
What if Hamdy wants to get his PhD from the reputable university A, while his credentials qualify him only for the less-reputable university B. He can first apply for an MSc with B and get the MSc degree to improve his credentials, then apply for a PhD in A. He can then transfer his MSc credits from B to A (this is possible for many A-B universities pairs in US/Canada). Note that -if this is what Hamdy plans to do- he shouldn't apply for a PhD in the less reputable university (B), because his supervisor will be grooming and expecting him to work for him for ~5 years, and then Hamdy will let him down and -moreover- ask him for a recommendation letter to the more reputable university (Hamdy can't go to A without a recommendation letter from his supervisor at B). I'm not sure what the supervisor will write in the recommendation letter then about Hamdy's commitment.

Younos Aboulnaga was the first to introduce me to the concept of "taking a break while studying". In his undergraduate study in Egypt, Younus paused before last year, spent a year working in Brazil, and then went back to earn his BSc degree. Almost all PhD students get fed up after a few years of working for it. They wish they could "take a break" just like Younus did. However, they can't just apply for any job and spend a year or two, then come back to continue the PhD. They have to find an internship inline with their research, competing with many PhD students for a limited number of internships, probably with low pays. If Hamdy goes for option 2, he could pause for as long as he wishes, then gets back to continue his graduate education when he feels he's ready to continue.

Why would Hamdy refrain from option 2:

Option 2 usually takes more time, even though he will probably take the MSc in option 1 as well.

Commitment to research
Most of the rationales for taking option 2 assumes it's likely for the student to drop out. If Hamdy knows somehow he's comfortable with doing research and will withstand the pain it takes to get a PhD, these rationales weight nothing for him.

Over qualified
Some universities (e.g. UCSB) won't admit you for a masters program if you already have had a masters degree in the same disciple from another university.

Request: If you know something that contradicts with what I'm stating here, or complements it somehow, please do comment on the post or drop me an email at ammar DOT w AT acm DOT org, and I will be happy to update the original post reflecting your valuable point of view.

Monday, October 5, 2009

How to enhance runtime performance?

Since we do computer science research, we typically implement our explorations and research advances as computer programs. Many research fields have to deal with an immense amount of data (e.g. information retrieval, natural language processing, data mining), adding scalability as a major requirement when you develop a prototype/an exploration.

This post is all about how to enhance runtime performance of your program. It summarizes a discussion I had with some colleagues in this regard:

1. "Premature optimization is the root of all evil (or at least most of it) in programming", says Donald Knuth. Instead, use a profiler to identify which pieces of the code need your attention.

2. Optimize the algorithm first, not the code. Sometimes we think a problem is too trivial to analyze its algorithm, but it makes much sense to reconsider the 'trivial' algorithm when it runs millions of times. For example, this code

double metric1 = calculateMetric1(input);
double metric2 = calculateMetric2(input);
if(metric1 > threshold1 && metric2 > threshod2)
  return true;
  return false;

Assuming 'calculateMetric2' is an expensive procedure, refactoring the code as follows will significantly enhance performance:

double metric1 = calculateMetric1(input);
if(metric1 <= threshold1)
  return false;
double metric2 = calculateMetric2(input);
if(metric2 <= threshold2)
  return false;
  return true;

3. Concentrate on high level optimizations. Most popular compilers do a lot of optimization on your behalf. For example, Microsoft's Visual C compiler will replace the following code with "x = 27000000":

x = 0;
for(int i=0;i<300;i++)
  for(int j=0;j<300;j++)
    for(int k=0;k<300;k++)

4. Consider changing the data structure that hosts your data (e.g. a hashmap instead of an array).

5. Caching. If there’s an expensive operation with inputs that are likely to repeat, it might be worth caching. Note that a cache with low hit-ratio might degrade overall performance.

6. Distribute the load on the multiple cores of your processor, or on multiple machines.

7. Get rid of redundant calls. For example, when the code aggressively uses case-insensitive string comparisons, lowercase your strings only once.

8. Sometimes, memory allocation is very demanding. The solution in these cases is usually to create your own memory allocator or use memory pools for certain objects.

9. Sometimes, initializing/resetting arrays is very costly. It’s not always necessary to initialize/reset an array before using/reusing it. For example, to compute the Levenshtein distance between two words, there’s a dynamic programming algorithm which uses a 2D array. Even though the same array is used for different word pairs, no need to zero the array since it’s built in a bottom-up fashion.

I'd like to acknowledge my friends/colleagues (Ahmed El Deeb, Ahmed Sabry & Diaa Samy) for the constructive discussion we had around this topic.