Comparing Algorithms

-

I recently mentioned that MIT OpenCourseware project started hosting Video/Audio lectures as well for some select courses. Thats an excellent opportunity to go to MIT and take a class without ever leaving your home.

I never studied formally about Computer Algorithms. So I started taking the course : 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005. After spending so many years in Software Development, I must admit, I have not much to take away from the first 1 hour 20min class, but here are some thoughts and notes on the size of input.

[Source:Wiki] In theoretical analysis of algorithms it is common to estimate their complexity in asymptotic sense, i.e., to estimate the complexity function for reasonably large length of input. Big O notation, omega notation and theta notation are used to this end. For instance, binary search is said to run an amount of steps proportional to a logarithm, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called hidden constant.

The key aspect of Asymptotic analysis is about estimating the rate of growth of required resources to achieve a function, particularly, to estimate the complexity function for reasonably large length of input. If the size of input doesn't qualify for this reasonably large length of input then the analysis just doesn't apply. Then the big question is about knowing this size of input, to be able to apply the concept for each such algorithm. This is the missing piece of the puzzle, often ignored. Often, it was always argued that one algorithm is much better than the other, as that is what being taught in class room or mentioned in academics.

For general problems like sorting, we might get an extensive analysis available in books and papers. But when it comes to problems that are specific to a domain, there is not much analysis available. We must do on our own to find out what is a resonably large size of input means for our problem. If we can learn how to do this, then we can apply our understanding of Asymptotic analysis in real life problems.

This is the reason we might have multiple algorithms in a solution rather than having just the 'BEST' (as per some CS grads) algorithm.

The example being discussed in the class was about sorting. Two algorithms have been compared: Insertion Sort and Merge Sort. Watch lecture 1 here. Link to Thought Garage » MIT Video/Audio OpenCourseWare

Comments

Bhasker V Kode said…
Nice find....

Keep Clicking,
Bhasker
December 26, 2006 at 6:16 PM
Post a Comment

Popular posts from this blog

Newsworthy News in Red October : Dow Jones & Tax Dodgers

-
Dow Jones Index crosses the symbolic 10000 figure. U.S. stocks rallied, sending the Dow Jones Industrial Average above 10,000 for the first time in a year, on better-than-estimated earnings at JPMorgan Chase & Co. and Intel Corp. Bank of America Corp., American Express Co. and JPMorgan more than doubled since the Dow slid to a 12-year low on March 9 as global financial firms began recovering from $1.6 trillion in writedowns and credit losses. International Business Machines Corp. and Hewlett-Packard Co. jumped at least 54 percent since March 9 on signs the nation was recovering from the worst recession in seven decades. Source: Bloomberg And, about 7500 International Tax dodgers file for IRS Amnesty to avoid jail Some 7,500 international tax dodgers have applied for an amnesty program that promises no jail time and reduced penalties for tax cheats who come forward, the Internal Revenue Service announced Wednesday. … The program is part of a larger eff...
Read more

USCIS Selects Final H1B Petitions by Random Selection - Almost a 50% chance for each Application

-
U.S. Citizenship and Immigration Services (USCIS) announced today that on April 12 it conducted the computer-generated random selection process to determine which H-1B petitions, subject to the congressionally mandated H-1B cap for fiscal year 2008 (FY 2008), would continue to final processing. USCIS completed this determination ahead of the preliminary schedule noted on April 3, when it announced it had received enough petitions to meet the cap for FY 2008. The 123,480 cap-subject petitions received on April 2 and 3 were labeled with unique numerical identifiers and selected randomly by computer. The chosen numerical identifiers were then transmitted to the appropriate service center for further processing. Source: USCIS Announcement Number 123,480 looks a lot better keeping in view initial estimates. A good 50% chance for each application to be selected.  Update: 3rd May 2007 Hello friends, I understand your anxiety. But don’t loose your hope and/or temper yet. Please wai...
Read more

H1B 2008:USCIS released Preliminary Numbers

-
USCIS today released the final count of number of unique pieces of mail received for H1B petitions. It received 133,000 unique pieces of mail containing H-1B petitions. I guess, each piece of mail will ' mostly ' contain more than one petition, as no company would send each petition in a seperate package and its most unlikely that a firm applies for just one petition. Probably by the end of next week, we might know the actual number of H1B petitions filed and how lucky one must be to get through the initial filter. Source: USCIS Releases Preliminary Number of FY 2008 H-1B Cap Filings  (26KB PDF) 04/05/2007 During Monday and Tuesday, USCIS received 133,000 unique pieces of mail containing H-1B petitions. This is lower that the original USCIS estimate of 150,000. USCIS based the initial estimate on amounts from manifests received along with the mail. USCIS reached the updated number following a physical count of the mail. Each piece of mail may contain more than one H-1B pe...
Read more