My (Jagota) response to a P4 issue that came up in class today (6/11): apparent inconsistency between P4 specs and the test data and output I posted on this page yesterday. 1. makeDSC does indeed create an empty collection. However after it has done so, one may call makeSet repeatedly to add sets containing a single vertex each. So this will make the output come out as desired for test Data A, namely the graph with zero edges. 2. Second, the P4 spec sample output is only for a particular DSJ which may arise in SOME application, which may have nothing to do with connected components of a graph. In that application, there may be no singleton sets. So the fact that the example in the P4 specs does not have singleton sets is not inconsistent with the fact that the DSC storing the connected components of a particular graph may have singleton sets. In summary, there is no inconsistency between the P4 specs (and my mention that makeDSC should create an empty collection) and the test data and output posted on the web page. (During class today I thought there might possibly be an inconsistency because someone mentioned that the P4 specs were inconsistent. But when we read the P4 specs it turned out that there is no inconsistency.)
In the two week2 lectures we will cover sections 0.3-0.4 (induction), section 0.5 (asymptotic notation), 0.6 (recurrence relations), and 0.9-0.10 (program correctness) of this handout. You are expected to already know the material in sections 0.1, 0.2, and 0.7 (we won't cover it in class). If you don't, then read and understand these sections. Also read sections 0.11 and 0.12 which discuss running time issues. We will not cover sections 0.8, 0.13--0.14 in this course as these involve probabilistic analysis and randomized data structures/algorithms. However you may find them interesting.