Skip to main content

Algorithm Analysis - 1

Currently, I'm learning to perform algorithm analysis using Big-O notation. In one resource I found the following problem:
You just dropped a box of glass toys and n toys in the box broke in half. You'd like to match the halves of the toys so that you could glue them together, but the only way to tell whether two halves belonged to one toy is to physically pick up the two pieces and try to fit them together. Express how long this matching process will take in terms of n.

The answer given is n^2 (n squared) with the following explanation: 

You have to compare every piece with every other piece. If you have 1 toy and it breaks in half, you have 1 comparison to make. If you have 2 toys and they both break in half there are 4 pieces and you have to do 6 comparisons. If you have 3 toys, there are 6 pieces and you have to do 15 comparisons. If you have N/2 toys, you have N pieces and you have to doN-1 + N-2 + N-3 + ... + 1 =(N)(N-1)/2 comparisons. This is O(N^2).

The order of magnitude is correct, but the reasoning seems wrong. Imagine you have 2 toys and thus 4 pieces. 

  • Starting with a random piece, there are 3 other pieces to compare it with. 
  • In the worst case, the first two comparisons don't produce a match. This means however, that the third piece is necessarily a match. 
  • Once you have performed those two (incorrect) matches, and reassembled the first toy, the remaining two pieces don't need to be tested as they necessarily fit.
  • If you add the steps to reassemble the toys (1 each), that gives a total of 4 matches for 2 toys.
Let's check this reasoning with three toys.

  • 3 toys: A, B,C
  • Broken in half into 6 pieces: A1, A2, B1, B2, C1, C2
  • Take one piece to test: A1.
  • In the worst case, all your first matches are wrong:
    • A1-B1 , A1-B2, A1-C1, A1-C2
    • Thus, it takes at most, 4 matches to match A1-A2 plus the step to reassemble A which gives 5 matches.
  • Now, there are only two toys left (B & C) to match. From our previous reasoning we know that only 4 matches are necessary.
  • This means it will take, at most, 9 matches to reassemble 3 toys.
If we perform this analysis for 4 toys, we'll find that it takes 7 matches to reassemble the first toy for a total of 16 matches.

In general, the pattern is  n^2 (exactly) or  O(n^2). This is what the answer stated, but the finer details of the answer seem off. 

Labels:

Comments

Post a Comment

Popular posts from this blog

Einstein's Logic Puzzle (SPOILER ALERT!)

On Monday I began working through a Discrete Math textbook in preparation for some courses I'll be taking in January. There was a beautiful logic problem in Chapter 1, apparently created by Einstein. This is one version of it: Five men with  different nationalities and with different jobs live in  con secutive houses on a street. These houses are painted  dif ferent colors. The men have different pets and have   dif ferent favorite drinks.  Determine who owns a zebra and  whose favorite drink is mineral water (which is one of the  favorite drinks) given these clues:  The Englishman lives  in the red house.  The Spaniard owns a dog.  The Japanese  man is a painter.  The Italian drinks tea.  The Norwegian  lives in the first house on the left.  The green house is  immediately to the right of the white one. The photogra pher  breeds snails.  The diplomat lives in the yellow house. Milk is drunk in the middle house. The owner of the green  house drinks coffee. The Nor
Post a Comment
Read more

CodeSchool vs Codecademy(or 'How socket inherits event listening methods and implements asynchronicity')

In this review I'm going to focus on the pedagogy that I see evident in some CodeSchool courses and compare them to  Codecademy. By pedagogy, I mean: 'How does CodeSchool teach?' and ' Does it do a good job of teaching?'. I'm going to argue that despite high quality videos, colourful web pages, and often ssspppeeeeeakkkiiiing...rrrreeally...slowly..., CodeSchool's pedagogy is inferior to that of Codecademy. There are many fantastic resources for learning to code on the web, and CodeSchool is one of them. So far I have completed courses in Ruby, Rails, Javascript, HTML/CSS, Jquery and Git on CodeSchool. The courses have all included high quality videos and colourful, interactive exercises- as well as  massive  pdf files of the slides ( the files take more than a minute to load on my machine .) The question is: does the higher production value mean better educational quality? The 'Try' courses on CodeSchool(such as Try Ruby and Try jQuery) are f
Post a Comment
Read more

Ruby on Rails -First App

Yesterday I built my first (technically second) Rails app working through Michael Hartl's book . The 3rd edition is free to read online and has been recommended by several self-taught developers; it is also on The Odin Project curriculum. The first tutorial covers the basic installations, including Git, Heroku and Bitbucket (instead of GitHub). The steps are clear, but the language sometimes is not.  Most of the steps worked -except that my app doesn't seem to work when accessed from Heroku.    When running bundle install, I ran into problems with the SQL gems. Apparently this was because Ubuntu14.04 didn't come with the C compiler needed.  I needed to run:                                sudo apt-get install libsqlite3 -dev                                sudo apt-get install libpq -dev             After this the bundle install  went ahead fine.    I also finished CodeSchool's Rails for Zombies which introduced basic Rails. As a review, I'm now worki
Post a Comment
Read more