CSE250                Sample Prelim II Answer Key                 Spring 2022

(1) (a) Insert the words bad bed bid bud act beg bet dog in that order into 
a basic binary search tree: The first-given word "bad" is the root and go on:

      (bad)
     /     \
 (act)     (bed)
               \
               (bid)
               /   \
           (beg)   (bud)
               \       \
              (bet)    (dog)
			  
(b) Result of deleting "bid": Using the inorder predecessor,

      (bad)
     /     \
 (act)     (bed)
               \
               (bet)
               /   \
           (beg)   (bud)
                       \
                       (dog)

Using the inorder successor instead:

      (bad)
     /     \
 (act)     (bed)
               \
               (bud)
               /   \
           (beg)   (dog)
               \        
              (bet)         

(c) Preorder transversals---any tree was fine, here are all three:

(a)  bad act bed bid beg bet bud dog
(b1) bad act bed     bet beg bud dog
(b2) bad act bed     bud beg bet dog

The extra thing to notice is that neither of the latter two is the same
as what you get from the first by deleting "bid".  Order can be tricky.
Also notice that all the trees are rather "scraggly", with relatively
high depth---this is what motivates considering red-black trees later.


(2) True/False With Justifications

[Spring 2022: I've kept the original wording from 2014, except as noted.]

(a) In a FlexArray data structure with n > c elements, in which
only inserts and no erasures have been performed, each node always
has at least c/2 - 1 elements.

True: the first node fills up to c, then element c+1 causes a split which
in fact leaves at least c/2 nodes in each node.  Further inserts also cause
splits only when capacity c is reached and similar division happens.

(b) Same question as (a), but now allowing erasures.

False: erasures can drop the population of a node below (c-1)/2 without
causing a re-allocation.

(c) In a {\tt FlexArray} that has just been built [up] with no erasures, the
next insertion is guaranteed to run in $O(\sqrt{n})$ time, even if it
causes a node to split.

Spring 2022: I tightened up the wording to make this clearly True.  In 2014,
I lectured more on the differences---which were put in action with a
different tradeoff r = 1, m = n because that favors the find(...) operation.
The original looser wording above for (c) was paired with this answer: This one 
could be argued either way.  The general intent with FlexArray is for c to be about 
sqrt{n} [as on 1(c) of your S22 Assignment 5].  If you're not dealing with erasures, you
should get this either by adjusting c in periodic refreshes, or knowing n
approximately in advance and choosing c accordingly from the get-go.  Then it's
True: the index-lookup is O(sqrt{n}) looping thru nodes, then the insert is
O(c) = O(sqrt{n}) from the C++ vector class, and finally any split also takes 
time proportional to c, and O(sqrt{n}) + O(sqrt{n}) + O(sqrt{n}) = O(sqrt{n}).
But it could be False: early on when n=c+1 like in (a), where you aren't
dynamically refreshing and you didn't know what n would be, the O(c) time is O(n)
not O(sqrt{n}).  


(d) The middle element in a vector with an odd number of elements
can always be accessed in O(1) time.

True: as vec[(vec.size()-1)/2].  The size function is O(1) since vector
maintains the size in a separate field as a class invariant.  [S22: True
for Array, and should be true for ArrayBuffer as
https://www.scala-lang.org/api/2.13.3/scala/collection/mutable/ArrayBuffer.html
promises constant time for random access (at least amortized), though I cannot find a clear
statement that size/length is O(1) time.]
 
 
(e) The middle element in a FlexArray with an odd number of elements
can usually be accessed in O(1) time.

False: even if we maintain the size in a field, we have no idea even in
which node the middle element will be, let alone its local index, without
looping thru what can be more-than-O(1)-many nodes.


(f) False.  Generally, BSTs do not provide random access, nor even access to the
begin and last elements in O(1) time.  [But see the "virtual HW7" for how to get O(log n) time.]


(g) A step in the /postorder/ transversal of a binary search tree
runs in amortized O(1) time.

True: it doesn't matter which transversal---they all take 2n-2 pointer
moves thru each edge in both directions, hence 2n-2 time total, which
amortizes as basically 2 moves per step of the postorder iteration.



(3) Answer to the shorter substitute question:

      var worditr = lookup.find(dummyEntry(word))
      while (worditr.hasNext && word.compareTo(worditr().key) == 0) {
         worditr.prev()
      } 
      worditr.next()   //because it will have moved out of the range
      while (worditr.hasNext && word.compareTo(worditr().key) == 0) {
         ...do the reciprocation check for worditr.synonyms()    [*]
         worditr.next()
      }

IMPT NOTE: We can abbreviate the first part (backing up to the start of the range) as

while (worditr.hasNext && word.compareTo(worditr.prev().key) == 0) { }

This is OK because we are only using the iterator value once, to see if the key
is still the same.  We are not doing the task yet.  But we cannot then do:

      worditr.next()   //because it will have moved out of the range
      while (worditr.hasNext && word.compareTo(worditr.next().key) == 0) {
         ...do task
      }
	  
The reason is that next() has already advanced the iterator past where we need it to be
for the task.  That's why the apply() parentheses method in the ...#Iter class is useful.
Notice that the body of the task uses it twice, once to see if the key matches, and once
to see if the list of synonyms is nonempty:

[*] Having initialized Booleans recip and hasSyns to false, the check is simply
            recip = recip || worditr().synonyms.contains(key)
            hasSyns = hasSyns || (worditr().synonyms.size > 0)


Here is the whole body of the task, including a way not to have to define "keyComp" explicitly.

   var keyitr = lookup.begin
   while (keyitr.hasNext) {
      val entry = keyitr.next()
      val key = entry.key           //TASK: For each synonym "word" of key, lookup word and see if key is
      val synSet = entry.synonyms   //one of word's own synonyms.  Because word might appear in different
      var synitr = synSet.begin     //noun,verb,adj., etc. forms, we have to try multiple keys.
      var recip = false
      var hasSyns = false
      while (synitr.hasNext) {
         val word = synitr.next()
         val wordAsItem = dummyEntry(word)
         var worditr = lookup.find(wordAsItem)
         //while (worditr.hasNext && keyComp(wordAsItem,worditr()) == 0) {  
         while (worditr.hasNext && word.compareTo(worditr().key) == 0) {
            recip = recip || worditr().synonyms.contains(key)
            hasSyns = hasSyns || (worditr().synonyms.size > 0)
            worditr.next()
         }
         if (allowPrintWhenTiming) {
            if (recip && key.startsWith("q")) {
               outp.println(s"$key and $word are reciprocal synonyms (key = " + entry.kind + ")")
            } else if ((!recip) && hasSyns && key.startsWith("q")) {
               outp.println(s"$key lists $word but $word has a list of synonyms without $key")
            } else if (key.startsWith("q")) {
               //OK todo nothing.
            }
         }
         recip = false
         hasSyns = false
      }
   }

This uses earlier code (I used an enumeration; this did not matter.  Enumerations are merely suggested,
not even recommended, for the genres in the final project.)

object SpeechParts extends Enumeration {
  //type SpeechPart = Value
  val Adjective, Noun, Verb, Misc, Unknown = Value
}

/** Assignment 4 class changed to have a part-of-speech field
    INV: category is one of "noun", "verb", "adjective", or "r"="misc" (or "unknown")
	(actually, the Fallows1898fx.txt file got rid of "r.")
 */
case class SynonymEntry(key: String, kind: SpeechParts.Value, synonyms: StringBox)

In SynonymsReader:
...
               if (line.contains("\\n.\\")) {
                  kind = SpeechParts.Noun
               } else if (line.contains("\\v.\\")) {
                  kind = SpeechParts.Verb
			   //...etc.   Eventually:
			val item = SynonymEntry(key, kind, new StringBox())
			//[then fill in the synonyms as before]


----------------The Spring 2014 answer in C++, just FYI----------------------------
Weed out words that are hd1 from one neighbor and id1 from the other,
except don't kill two consecutive words.  This means if we have iterators on 
three consecutive words w,x,y and ed1.5(w,y) holds, we can erase x and resume
with y being the new 'w'.  It is not actually needed to call the hd1 or id1
functions (but doing so was not a terrible bother).  The other main point
was to be careful not to iterate past end() or dereference end().  Code:

void reduce(F& chain) {
   F::iterator nit = chain.begin();
   while (nit != chain.end()) {
      F::iterator pit = nit++;  //INV: will be 2items before nit
	  if (nit == chain.end()) { return; } //no more erasures possible
	  //else
	  F::iterator it = nit++;   //INV: 1 item before nit and after pit
	  if (nit == chain.end()) {
	     return;
      } else if (ed15(*pit,*nit)) {
	     nit = erase(it);
	  } else {
	     ++nit;
	  }
   }
}

Optional variations that were fine:
   At start: if (chain.size() < 3) { return; } //nothing to do
   Main test: if (or else if) ((id1(*pit,*it) && hd1(*it,*nit)) 
                                || (hd1(*pit,*it) && id1(*it,*nit)))
   Declaring pit and it at the beginning, so long as you avoided invalidating them.
   
Main errors people made:
   Forgetting that chain could have < 3 words.
   Forgetting to do nit = erase(nit), so that nit stays valid.
   Forgetting the other iterators could become invalid too, like
      when a vector completely re-locates itself after an erasure.
   Incrementing nit++ twice in the loop without testing for end().