\documentstyle{report}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 220/317: Programming II/Data Structures
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\setlength{\textwidth}{6.25in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\newcommand{\assignmentNumber}{3 \& 4}
\newcommand{\outdate}{18 October, 1994}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}
                              
\section*{Answer Set \assignmentNumber \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate\end{flushright}}}}
    
{\sc Ex2.1.3 a:}
\begin{tabular}{ccccc}
P&$\wedge$&Q&$\Rightarrow$&P\\
T&T&T&T&T\\
T&F&F&T&T\\
F&F&T&T&F\\
F&F&F&T&F\\
1&3&2&5&4\\
\end{tabular}
\hfill
{\sc Ex2.1.3 b:}
\begin{tabular}{ccccccc}
($\neg$ P & $\Rightarrow$ &(P & $\wedge$ & Q)) & $\equiv$ & P\\
 F &  T  & T&T&T&T&T\\
 F & T  & T & F& F &  T &T\\
 T & F & F & F & T & T & F \\
 T & F & F & F & F & T & F \\
 4 & 5 & 1 & 3 & 2 & 7 & 6 \\
\end{tabular}

~\\~\\
\noindent
{\sc Ex2.1.3 c:}
\begin{tabular}{ccccccc}
P & $\wedge$ & (P & $\Rightarrow$ & Q) & $\Rightarrow$ & Q \\
T & T & T & T & T & T & T \\
T & F & T & F & F & T & F \\
F & F & F & T & T & T & T\\
F & F & F & T & F & T & F \\
4 & 5 & 1 & 3 & 2 & 7 & 6 \\
\end{tabular}

~\\~\\
\noindent
{\sc Ex2.1.3 d:}
\begin{tabular}{ccccccccccc}
(P&$\wedge$&Q)&$\vee$&($\neg$P&$\wedge$&R)&$\Rightarrow$&Q&$\vee$&R\\
T & T & T   &T& F& F & T& T &T&T& T \\
T & F & F   &F& F& F & T& T &F&T& T \\
F & F & T   &T& T& T & T& T &T&T& T \\
F & F & F   &T& T& T & T& T &F&T& T \\
T & T & T   &T& F& F& F&  T &T&T& F \\
T & F & F   &F& F& F& F&  T &F&F& F \\
F & F & T   &F& T& F& F&  T &T&T& F \\
F & F & F   &F& T& F& F&  T &F&F& F \\
1&3&2      &7& 4&6&5   & 11 &8&10 & 9\\
\end{tabular}

~\\~\\
\noindent
{\sc Ex2.1.3 e:}
\begin{tabular}{ccccccccccc}
(P&$\vee$&Q)&$\wedge$&($\neg$P&$\vee$&R)&$\Rightarrow$&Q&$\vee$&R\\
T & T & T   &T& F& T & T& T &T&T& T \\
T & T & F   &T& F& T & T& T &F&T& T \\
F & T & T   &T& T& T & T& T &T&T& T \\
F & F & F   &F& T& T & T& T &F&T& T \\
T & T & T   &F& F& F& F&  T &T&T& F \\
T & T & F   &F& F& F& F&  T &F&F& F \\
F & T & T   &T& T& T& F&  T &T&T& F \\
F & F & F   &F& T& T& F&  T &F&F& F \\
1&3&2      &7& 4&6&5   & 11 &8&10 & 9\\
\end{tabular}

~\\~\\
\noindent
{\sc Ex2.2.3:}
Given $0\le i < j \le N$: (a) the smallest $i$ is 0; (b)
the largest $i$ is $N-1$; (c) the smallest $j$ is 1; (d)
the largest $j$ is $N$; (e) the smallest $N$ is 1.

~\\~\\
\noindent{\sc Exercise 3}
If F and G are tautologically equivalent, then
for whatever the program's state, F is true if and only
if G is true. Hence, whatever branch is taken in,
\begin{verbatim}  if F then S else T \end{verbatim}
will be taken in,
\begin{verbatim}  if G then S else T.\end{verbatim}
Neither F nor G have side effects. In each statement, the
world is affected and transformed only by S or T, whichever
is run. Hence, under any circumstance, either of these
two statements causes the same code to be run to affect
the world. Hence they affect the world exactly the same.

~\\~\\
\noindent{\sc Exercise 2.5.2}
\begin{itemize}
\item[(a)] $s = A + B .$
\item[(b)] $z = (x+y)/2.$
\item[(c)] $ k|x$.
\item[(d)] $ f|N$.
\item[(e)] $x=2^k$, some integer $k$.
\item[(f)] $(D|X) \wedge (D|Y)$.
\item[(g)] $X = qD+R$, for integers $q, r$.
\end{itemize}

~\\~\\
\noindent{\sc Exercise 2.5.3}
\begin{itemize}
\item[(a)] $z = \min(X,Y)$.
\item[(b)] $z < \min(X,Y)$.
\item[(c)] $(k\le N) \wedge (k=2^l) \wedge (N<2^{l+1})$, for some integer $l$.
\item[(d)] $(N<k) \wedge (k=2^l) \wedge (2^{l-1}\le N)$, for some integer $l$.
\item[(e)] $(a^2 \le N) \wedge (N<(a+1)^2).$
\item[(f)] $(1\le x \le 100) \wedge (y|x).$
\end{itemize}

~\\~\\
\noindent{\sc Exercise 2.5.4}
\begin{itemize}
\item[(a)] $a=\min(A,B)\wedge b=\max(A,B).$
\item[(b)] $(a\le b\le c) \wedge \bigl(\,
        ((a=X)\wedge(b=Y)\wedge(c=Z)) 
    \,\vee\,((a=X)\wedge(c=Y)\wedge(b=Z)) 
    \,\vee\,((b=X)\wedge(a=Y)\wedge(c=Z)) 
    \,\vee\,((b=X)\wedge(c=Y)\wedge(a=Z))
    \,\vee\,((c=X)\wedge(a=Y)\wedge(b=Z))
    \,\vee\,((c=X)\wedge(b=Y)\wedge(a=Z)) \,\bigr).$
\item[(c)] $(X=\min(X,Y,Z)\Rightarrow p=1) \wedge
            (Y=\min(X,Y,Z)\Rightarrow p=2) \wedge
            (Z=\min(X,Y,Z)\Rightarrow p=3).$ What if $X=Y$?
\end{itemize}
\begin{verbatim}

-----------------------ANSWER4.PAS-----------------------

[ENVIRONMENT,INHERIT('mystring2')]

module answer4(input,output) ;

(* Answer to problem set 4,
   move-to-front heuristic for the unique words program
   (c) Burton Rosenberg 1994
*)
type
(* a mylist has a dummy header. *)
   MyList = ^MyListElement ;
   MyListElement = record
                   theMs : MyString ;
                   count : integer ;
                   next : MyList ;
             end ;
   MyListCoupon = MyList ;

procedure create_MyList(var ml : MyList ) ;
(* Create dummy header for an empty list and return pointer in ml. *)
begin
   new(ml) ;
   ml^.count := 0 ;
   ml^.next := NIL ;
   ml^.theMS.length := 0 ; (* WARNING: breakdown of mystring abstraction *)
end ;

procedure print_MyList( ml : MyList ) ;
(* Print mylist ml. No side effects. *)
begin
   ml := ml^.next ; (* skip dummy header *)
   while (ml<>NIL) do begin
       write(ml^.count:3,' ') ;
       writeln_MyString( ml^.theMs ) ;
       ml := ml^.next
   end 
end ;

procedure add_MyList( var ml: Mylist; data: MyString; count: integer ) ;
(* Add to the front of MyList ml a record containing MyString data and
   count count. *) 
var p : MyList ;
begin
   new(p) ;
   p^.count := count ;
   copy_MyString( p^.theMs, data ) ;
   p^.next := ml^.next ;
   ml^.next := p
end ;

function find_MyList( ml: MyList; toFind: MyString ) : MyListCoupon ;
(* Search for MyString tofind on MyList ml. Return non-NIL coupon if
   found, else return NIL *)
var p : MyList ;
begin
   p := NIL ;
   (*L.I. toFind not found on list up till predecessor of ml^.
          ml^ to check *)
   while ( p<>ml^.next ) do
      if compareNC_MyString(ml^.next^.theMs, toFind) then p := ml^.next
      else ml := ml^.next ;
   if (ml^.next=NIL) then find_MyList := NIL
   else find_MyList := ml ;
end ;

procedure Increment_MyList( ml: Mylist; coup: MyListCoupon ) ;
begin  coup^.next^.count := coup^.next^.count+1   end ;

procedure Statistics_MyList( ml: MyList; var len: integer; var sum: integer ) ;
(* Calculate length and sum of count fields of MyList ml. *)
begin
   len := 0 ;
   sum := 0 ;
   ml := ml^.next ; (* skip dummy header *)
   (* L.I. len is number of list items up till, not including ml^,
           sum is the sum of count fields for list items up till,
           not including ml^.count. *)
   while (ml<>NIL) do begin
      len := len+1 ;
      sum := sum + ml^.count ;
      ml := ml^.next
   end
end ;

procedure MoveToFront_MyList( ml: MyList; coup: MyListCoupon ) ;
(* Move list item indicated by MyListCoupon coup to front of MyList ml. *)
var p: MyList ;
begin
   (*ASSERT: coup<>NIL and coup^.next<>NIL *)
   p := coup^.next ;
   coup^.next := p^.next ;
   p^.next := ml^.next ;
   ml^.next := p
end ;
end.

-----------------------DRIVER4.PAS------------------------

[INHERIT('MYSTRING2','ANSWER4')]
program driver1( input, output ) ;

(*  driver program to test answer4.pas
   (c) Burton Rosenberg, U. of Miami 1994
*)
var
   ml : MyList  ;
   aLine, aWord : MyString ;
   p : MyListCoupon ;
   i : integer ;
   numWords, totalCount : integer ;

begin
   create_MyList( ml ) ;
   i := readln_MyString( aLine ) ;

   (* L.I. aLine has a line of text yet to process *)
   while ( i<>MYEOF ) do begin
      parse_MyString( aLine, aWord ) ;

      (* L.I. aWord has a word to process *)
      while ( length_MyString( aWord ) > 0 ) do begin
         p := find_MyList( ml, aWord ) ;
         if (p=NIL) then
            (* word not found, add to list w/ count=1 *)
            add_MyList( ml, aWord, 1 ) 
         else begin
            (* word found, increment the count then move to front *)
            increment_MyList( ml, p ) ;
            moveToFront_MyList( ml, p ) ;
         end ;
         parse_MyString( aLine, aWord ) ;
      end {while length ...} ;
      i := readln_MyString( aLine ) ;
   end { while not MYEOF } ;

   (* Calculate and print results *)
   Statistics_MyList( ml, numWords, totalCount ) ;
   writeln(totalCount:5,' words in the file,') ;
   writeln(numWords:5,' unique words. They are:') ;
   print_MyList( ml ) ;      
end .

----------------- SAMPLE OUTPUT -------------------

$ run driver4 /input=constitution.dat
$ type /page sys$output.dat
7760 words in the file,
 1250 unique words. They are:
  2 others
205 to
 40 on
  1 MESSAGE
 35 this
  3 pass
  4 liberty
  4 our
 16 is
  3 secure
 12 more
741 the
 34 Constitution
  3 know
 17 who
    .............  et cetera
\end{verbatim}

\noindent
{\sc Note:} CPU Time for driver4.pas on this file was 50.53
seconds. For driver2.pas,  CPU Time was 2:50.38.

\end{document}

