On Formal Reasoning

As I am going through Introduction to Algorithms course from MIT, just past the first lecture, we can see the importance of formally proving an algorithm correct. If an algorithm is intuitively incorrect at first, then the need for formal reasoning becomes even more important.

Coming to the 2-d peak finding algorithm, here is a semi-formal reasoning:

  • When we find a global maximum in a column and shift to either left (right), it is because this global maximum is less than the left (right) element. So, if there is a new global maximum in this column, then it is definitely more than all the elements in the previous column because it is more than the left (element) itself. So, the algorithm works.
  • Will the same argument apply if we find a 1-D peak in a column instead of a global maximum? Does not look to me like so…
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s