Last year, I posted this algorithm question, and said I would give the solution shortly after. I was looking over stuff I had posted on my blog today, and realized I never posted a solution, so here it is:

Note: To avoid and confusion, “story” and “floor” mean the same thing in this example.

The Problem:

A firm wants to determine the highest floor on its n-story building from which a device can fall with no impact on the device’s functionality. The firm has two identical gadgets that you can experiment with (each costs $1,000,000). You are allowed to break both gadgets,  but no extra gadgets will be provided. Design a brute force algorithm in the best efficiency class to solve this problem.

The most simple solution seems pretty obvious. You start at the first floor and drop the gadget. If it breaks, you know it cannot be dropped from anything higher than 1 story. If it doesn’t you go to the next story and drop it. You keep doing this until the item breaks. When it breaks, you know that the last possible story that you can drop it from without breaking is the previous story.

There must be a much faster way, right?  What if you had a building with 2000 floors, and the gadget would not break until floor 1900? You would waste a lot of time using this simple brute force method. The asymptotic time complexity of this algorithm is linear, or . So assuming it takes on average 10 minutes to drop the gadget, take the elevator all the way down to the first floor, inspect the gadget to see if it is broken, and take it all the way back up to the next floor, it would take you 1900*10 minutes to find the answer to your problem. That is A LOT of time.

Another possible solution, which is much more elegant: (note: this is still considered a brute force algorithm)

Remember, we have two gadgets to use during this testing project.

First, you drop the gadget at where n is the number of stories. If the gadget breaks at this story, you know the lowest possible story it will not break is between story 1, and story . If it doesn’t break at then drop the gadget at .

If it breaks, then you know the lowest possible story it will not break is between and . If it doesn’t break at , then you just increase the multiple by 1. You keep doing this until you find a story where it breaks.

For instance, lets assume it would break at . You start at floor (remember, we already dropped it at so we don’t need to check it again). If it breaks, you know the lowest story is .

If it doesn’t you just keep incrementing until you get to . If it does not break at this floor, you know the lowest possible floor is that floor, since we know it broke at (we already tested it an it broke at that floor).

This solution has am asymptotic time complexity of or

jonnale Computer Science

So it is no surprise that this blog hasn’t been updated in quite awhile, and the frequency of updates has seriously decreased. This isn’t necessarily a result of laziness, in fact, it is the opposite. So much has been going on that I haven’t had time to update:

Here is what is going on in my life:

• Last semester was incredibly tough. I took a couple of really hard classes, was working on a few research papers (which got accepted to conferences in Russia!), and started working on a few Android apps. It was REALLY freaking busy.
• This semester isn’t as busy, but is still very busy. I am taking all morning classes (which turned out to be awesome), and I am in the middle of developing some awesome Academic Android apps for professors and students. I am really freaking excited about this. I love working with the Android SDK.
• I am TA’ing this semester for Systems Programming. I have a total of 3 jobs on campus.
• I have been applying for jobs, which takes a lot more time than most people think. In most cases, it isn’t a simple “write cover letter + submit resume” process. There are usually other steps involved, and in some cases, these steps are VERY time consuming.

Along with application development, Andrew Cullison and I have opened up Android for Academics to promote the use of Android based smartphones in academic environments (this site is still under construction). We also plan to use this to promote some of the applications I am working on for Android.

On top of all of this, some of my really close friends are moving away, and I have been doing my best to spend as much time as possible with them before they are gone. Furthermore, it looks like I am going to be moving (pending I get a job) and I have my heart set on Boston. I have been trying to balance my time between family and friends seeing as I might be moving, which has been both interesting and difficult.

Needless to say, 2010 has been a very busy and interesting year so far, and it is only going to get more interesting in the upcoming months.

jonnale Computer Science

So for reasons outside of my control, I was unable to post any blogs this summer. I don’t want to get into specifics, but trust me, my reason is a good reason.

My last year of my undergraduate studies has begun, and so far it is going okay. This again goes back to the reason I wasn’t able to post anything this summer, but I don’t want to get into that.

In terms of Philosophy, I am taking Philosophical Inquiry, and Philosophy of Mind. Both are awesome.

In terms of Computer Science, I am taking Theory of Computation. I knew going in it was going to be a hard class, but I am actually really interested in the material. Granted, its still hard, but at least it isn’t boring and hard. I have my first exam for this course this week.

I also found out last week, that three papers I worked on were accepted for publication! I worked very hard on these projects, and it feels very rewarding.

Anyway, I hope that I will find the time and motivation to post more. There is a lot of cool tech news floating around, so I am sure there will be more to come.

jonnale Computer Science

I really like puzzles. Although I do enjoy board game puzzles, my favorite type of puzzles are ones that require extensive thinking and a clever and elegant solution. This is what really drew me to Computer Science. Applying data structures, algorithms, architecture, etc., and coming up with a high performing, elegant solution to a problem is challenging and exciting to me. Puzzles are also a reason I really like Philosophy.

On my algorithms midterm exam before Spring break, there was a question that I think represents why I truly enjoy studying Computer Science. Never in my life have I read a question on an exam and said to myself, “This question is awesome.” I am going to post a modified version of the question, and strongly encourage anyone to post their solution as a comment. I will post one possible solution on Friday.

A firm wants to determine the highest floor on its n-story building from which a device can fall with no impact on the device’s functionality. The firm has two identical gadgets that you can experiment with (each costs $1,000,000). You are allowed to break both gadgets,  but no extra gadgets will be provided. Design a brute force algorithm in the best efficiency class to solve this problem.

This is a very technical question, so in order to simplify it, do not worry about what “brute force” or “efficiency class” means if you have never taken an algorithms course. These are important concepts for solving this problem in a real life situation, but I do not want these topics to discourage discussion amongst non-CS readers. If you wish to leave a comment, simply write what you would do to solve this problem.

Example solution:

1. Drop gadget on first floor
2. If it breaks, gadget cannot be dropped from hight=current floor
3. If it does not break, go to next floor and Repeat.

Example in pseudocode:

DidItBreak(n)
//where n is the number of floors
for currentFloor<-1 to n do
  if result of device drop = broken
    return currentFloor-1
  else
    currentFloor <- currentFloor + 1
  return -1

jonnale Computer Science algorithms

Everyone that has a gmail account knows how awesome gmail is. The layout is great, there are a TON of features and options, and it comes with some awesome applications (Google Apps). Not to mention, you get 7gb of storage for FREE.

Recently, I found out that Google offers Google Apps (gmail, calander, google docs, etc) for FREE to educational institutions. Not only that, but Google maintains the server, and everything is stored on the Google cloud. This means that IT and server administrators do not have to worry about an e-mail server!

In terms of money:

1. Schools would not have to purchase a server for e-mail (or at least storage for e-mail).
2. Schools would not have to purchase a license to software (such as Microsoft Outlook Webmail)
3. Server administrators could work on more important tasks.

Of course money is important, but faculty and students should also be a big concern. Let’s compare Google Apps with the software my college uses, Microsoft Outlook Webmail:

Google Apps:

Gmail:

• 7GB of storage space
• Very user friendly
• Saves e-mail while you are typing in case of a crash
• Separate Section for “starred” e-mail (useful for bookmarking important e-mail)
• Allows you to search the content of your mail

Google Calendar

• Excellent user interface. (Seriously, anyone with a brain can figure it out in less than 10 seconds)
• Allows you to share calendars
  • You can make subcalendars, and only share the subcalendars while making your general calendar private (this would be great for faculty and students).
• Allows you to send invites for events. This could be very useful for department meetings and faculty, student groups, etc.

Google Docs:

(Note: I must admit, I do not use Google docs that frequently due to syncing notes with DropBox)

• Allows you to create text documents, presentations, spreadsheets, forms, etc.
• Allows you to share documents with your peers.
• Could be a great tool for taking notes in class.

Microsoft Outlook Webmail:

• “Premium” mode only works with internet explorer (sorry mac and linux users).
  • “Premium” mode really means drag and drop. (It’s 2009, is drag and drop really a “premium” feature?)
• E-mail
  • 50mb of space (I am currently using 46mb and receive a warning every day)
  • Does not save draft of e-mail while you are typing.
  • Times out after 10-15 minutes. If you write a 15 minute e-mail and hit “send” it will take you to the login screen and you will have lost the e-mail (this is so frustrating).
  • Allows you to “Flag” e-mail for bookmarking
  • DOES NOT LET YOU SEARCH YOUR INBOX (if it does, it isn’t mind numbingly obvious where the search option is)
• Calendar
  • Does not have a nice, simple graphical view.
  • Sending events to other people is no where near as simple (it is not that challenging, but compared to google calendar, it could be much simpler).
  • I am not even sure how to add a personal event? Here is the screen when you hit add event:

(click to expand)

(Note: I am assuming the first field is the “To:” field (why are none of the fields labeled?)? Why is it required? What if you want a personal event?)

• Notes – No where near as many features as google docs. To use an analogy: Google docs is to Open Office, as Microsoft Webmail “note” is to a simple .txt file.

The reason I did not include each feature in Microsoft Outlook Webmail as its own nice header like I did for Google Apps is because MO Webmail is just a mess of features, while each Google App is its own separate application (you can use Google docs without using gmail, etc).

So in conclusion:

1. Google Apps is Free!
2. Google Apps provides plenty of storage space (7gb).
3. Google Apps would save time and money (no need to buy server, Google maintains the cloud).
4. Google Apps offers more features, and each feature is well implemented. These features could be used by faculty, students, student groups, etc.

(I would just like to note, I use thunderbird as an e-mail client due to my strong dislike for Microsoft Outlook Webmail. I prefer using an e-mail client, but many students simply use the webmail client.)

jonnale Computer Science