Posted by: atri | September 27, 2010

Lect 12: Runtime Analysis of GS Algorithm-II

In today’s lecture, we finished the implementation of the GS algorithm and proved that it can be implemented in O(n^2) time. We also briefly looked at (examples of) graphs. The slides have been uploaded.

Next lecture, we will define graphs more formally and look at some basic concepts. (The material will be from Sections 3.1 and 3.2 in the book.)



  1. Will there be a grading rubric for HW3 posted? Also, for #2, do we need to show an implementation in order to show running time of O(f(n))?

    • Hi Laurie,

      The grading rubric for HW 3 should be up by tonight.

      Regarding #2, you have to argue convincingly that the run time of your algorithm is O(f(n)). If that means you need to provide details on how certain steps of your algorithm are implemented, then you should do that. Basically if you claim some step of your algorithm runs in such and such time, there should be no reason to doubt your claim.

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


%d bloggers like this: