CSE250, Fall 2009      Remarks on Assignment 3     As of 10/12 (still grading)

I gave preliminary stats in class, and we haven't finished grading by any
means.  The most common omission with makefiles wasn't the dreaded TABs
but rather having the target as "PhraseClient.cpp" without one's initials.
UNIX and g++ are not able to divine them!  Fixing this, and things like
lowercase "phrase.h", took several hours (and cost 3 pts.).  By the way,
not having your initials on Phrase.{h,cpp} was a minor convenience, 
allowing us to test the latter separately in the root course-submit
directory without having to rename it, or rename our Phrase class with
your initials---all this being done with a specially-written Perl script.

Besides the software engineering issue of (a) economizing on public
functionality by a library, as I raised in class, two other issues emerged:
(b) Is it worth compromising "Declarativeness" to make code more efficient?
(c) When should data be treated "by-value", vs. "by-pointer" (== by-Java!)?
[Plus there was (d) the option of extending or "wrapping" StringStack, but
I think sensibly no one took it up, and it was really "planted" only to 
discuss (inheritance-versus-) "delegation" later in Chs. 4--5, and because
if I didn't I thought people might wonder at the similarity and ask.]

My "gentle persuasion" on (a) worked reasonably well: only 7 new public
methods + one Phrase(string) constructor were added across everyone's code,
and only 1 of those 7 could not be implemented fully.  That 1 was a
getter for an extra private field "finished" whose value was set by a
very long "push" method that seemed to be doing the client's job.
The field was "modal" in the sense that it seemed to depend on the
next word given as argument to "push", rather than on the other fields
of the actual object alone---or at least I couldn't tell quickly from
reading the code.  Such a dependence is hard to treat in code that
should serve all clients equally.  We presupposed that any additions
would be accessors and hence marked "const" (as generally required!),
so we word-searched all Phrase.h files for "const".  Adding a non-const
method to an object specification signifies intent to mutate it in new
ways, and we would have no way to simulate such changes in state by
adding methods---const or not---wthout going overly into code details.   

Test runs were automated (1) with your submitted files, (2) with your
client and our "maxed-out" Phrase class, and (3) with your Phrase
class and our client---which only required the minimum-specified
functionality and hence could drive any Phrase class however augmented.
Run (3) did, however, require that methods adhere to their specified
meanings---which brings up issue (b).  Bad results---even non-compiling---on
(2) and (3) did *not* rule out possibly getting full credit for your own
code that did (1) perfectly.  Instead, good results on (2) or (3)
could yield full-credit for the one component even if the tandem failed
on run (1).  Such "modularity" *may* also bring more-lenient marking of
errors, on the principle that being friendly to such componentwise "black
box" testing (p149 etc.) is a debugging help.  Besides Hamlet.txt with
100 words and then all words, we ran on plaintext files of the Gettysburg
Address, US Declaration of Independence, and original US Constitution,
which have testing features explained on the private answer-download page.

Issue (b) could generate a prelim-exam question that goes like this:

I.   Let n stand for the # of words in a Phrase.  How long does it 
     take to run (the answer-key version of) isAscending()?

     Answer: "O(n)"---or more precisely, Theta(n).

II.  The client checks isAscending() as each word is added.  What is
     the asymptotic running time for this whole process thru n words?

     Answer: O(1) + O(2) + O(3) + ... + O(n) = "O(n^2)"---but prefer
     saying Theta(n^2) since you know the time well: it's quadratic.

III. Now it was observed that if a Phrase was previously known to be
     ascending, then to check whether a newWord leaves it ascending,
     we only need to check its length against the previously-added word.
     Now what is the whole-process running time?

     Answer: Assuming the time for newWord.size() and the comparison
     is constant (i.e., ignoring the character length of strings or
     supposing no word is longer than say 15 letters), i.e. "O(1)",
     we get O(1) + O(1) + O(1) + ... + O(1) for n words added one-by-one,
     = "O(n)"---or better said, Theta(n).  Which is much less than II.!
     ---because n = o(n^2), using "Little-Oh" to express that.

Your exam won't ask something like *this* insofar as it's not supported by
homework---I chose not to put a "Report" or essay component on Assgt. 3
where it could have come in---but this type of reasoning is upcoming in
lectures when I finally address the "O(1)"s and "O(n)"s sprinkled throughout
Chapter 4.  For now instead---and this is in-bounds for your exam---consider
two ways you could implement the quicker check of III:

(A) By coding "isAscending()" to do just that one comparison.
    Reasoning inductively, this works fine with a client (including my
    answer key) that keeps pushing words until isAscending() fails, 
    and then pops off the offending word.

(B) By having the client do the comparison---and keep track of the
    cumulative results inside a loop.  Then in fact you don't need
    the isAscending() method at all.  

Well, (B) can be taken to the logical conclusion that you don't need
classes at all!  I did my sophomore-year programming in a language called
PL/I which was single-file-only.  Since the project emphasized the "modular"
benefit of splitting tasks between client and methods in classes, I think
most people thus-tempted did (A).  But now Rep. Joe Wilson comes into play:
*Unless* the Phrase class has a big fat /** REQ: stating that only
ascending-or-descending phrases can be stored there, or *unless* it
enforces a straitlaced // CLASS INV that words breaking progressions are
booted out, another client would expect to use it with phrases such as
"a flash in the pan".  On that the isAscending() "Hack" returns "true",
but looking at its name, "You lie!"  Declarativeness means never having
to say you're fibbing.

The tiebreaking consideration between II. and III. here could be the
project spec's saying to assume no Phrase would be longer than 20 words.
Then there's no asymptotic "n".  Yes if we stored all of "Hamlet" as a
single Phrase the quadratic time would be "molasses", but for "O(20^2)"
with the "O" standing-in for a small principal constant, you hardly notice.
This is subsumed by the general software engineering advice "Never
optimize!" (Google that!), or more reasonably, Logic First, Then Tweaks.
(Nevertheless, there was no points penalty for the "smart" hackery.)


Issue (c) has no easy answer, not even in-soapbox-mode as in (b).
From "Java2C++" we know we /can/ program entirely with pointers for all
non-primitive types.  Do we want to?  Value syntax is easier, but
prevents use of "virtual" method behavior (except thru references which
we're soft-pedaling) and imposes an assignment requirement (operator=).
The nub is, do we really want to make a clone by assigning?
In my "PhraseClientValues.cpp" version this is done (only!) to save the
values of the longestAscendingPhrase and longestDescendingPhrase found
thus far.  But I could have used a pointer to it instead---either changing
a pointer p to the "&" of a new champion OR (if the phrase phr was created
by-value within a loop, so that a pointer to it would "dangle" on loop
exit) using the Phrase copy constructor via p = new Phrase(phr); instead.
Note from today's lecture that the default copy-constructor is *not*
upset by the presence of a member-const field.  Some of you may have
felt tricked by keeping the "const int maxSize" field from StringStack,
then getting the compile error about operator= (mysteriously).  The point
at the very end of my lecture today (end of the "Big Three" slide),
however, is that the <iostream> library is already playing that trick on us
all.  Not being able to assign streams forced the ungainly preamble and its
use of pointers with streams supplied to you.  This results from an act of
deliberate "self-mortification": operator= is declared but put in the
"private:" section!  Well the purpose is to save programmers from demonic
problems that would follow from liberally cloning streams.  The Phrase
class needs nothing so drastic, but especially /when/ maxSize could be
high and allow those n=10,000-word phrases talked about in (b) [for a
different task and a different client!], there's nothing wrong with its
denying use of operator=.


This is about as close as I have time to furnish a sample exam, supplying:
(a) some concluding discussion of the theme I brought in class,
(b) an O-notation question where you see its purpose being used, and
(c) help with my two most recent lectures which are in-bounds for the exam.