#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\usepackage{calc}
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc1[20]
\end_layout

\end_inset

If we had only 
\family typewriter
LTAG
\family default
,
 
\family typewriter
INFO
\family default
 and 
\family typewriter
RTAG
\family default
 fields (not 
\family typewriter
LLINK
\family default
) in a level order sequential representation like (8),
 would it be possible to reconstruct the 
\family typewriter
LLINK
\family default
s?
 (In other words,
 are the 
\family typewriter
LLINK
\family default
s redundant in (8),
 as the 
\family typewriter
RLINK
\family default
s are in (3)?)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Yes,
 although the traversal might be less efficient.
 First,
 we would have to collect the roots of the trees to form the first level.
 These roots are precisely the first family,
 that is,
 the first sequence of nodes up to an including one with 
\begin_inset Formula $\mathtt{RTAG}=1$
\end_inset

.
 We count the number of such nodes that have children,
 which are the ones with 
\begin_inset Formula $\mathtt{LTAG}=0$
\end_inset

.
 For the second level,
 we take as many families as nodes with children in the first level.
 Each of those families corresponds to the children of one of those nodes,
 in order.
 For the third level,
 we take as many families as nodes with children in the second level,
 and so on.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc3[24]
\end_layout

\end_inset

Modify Algorithm 2.3.2D so that it follows the ideas of Algorithm F,
 placing the derivatives it computes as intermediate results on a stack,
 instead of recording their locations in an anomalous fashion as is done in step D3.
 (See exercise 2.3.2–21.) The stack may be maintained by using the 
\family typewriter
RLINK
\family default
 field in the root of each derivative.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
[Initalize.] Set 
\begin_inset Formula $\mathtt{P}\gets\mathtt{Y}\$$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e23324b"

\end_inset

[Differentiate.] Set 
\begin_inset Formula $d\gets\mathtt{DEGREE(P)}$
\end_inset

.
 If 
\begin_inset Formula $d=0$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{ARGS}\gets0$
\end_inset

,
 otherwise set 
\begin_inset Formula $t\gets\mathtt{RLINK}^{d-1}\mathtt{(LLINK(DY))}$
\end_inset

,
 
\begin_inset Formula $\mathtt{DY}\gets\mathtt{RLINK(}t\mathtt{)}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{RLINK(}t\mathtt{)}\gets\Lambda$
\end_inset

.
 Then perform the routine 
\begin_inset Formula $\mathtt{DIFF[TYPE(P)]}$
\end_inset

.
 (This routine uses 
\family typewriter
P
\family default
 and 
\family typewriter
ARGS
\family default
 as its arguments and it is in change of freeing the nodes of 
\family typewriter
ARGS
\family default
 that will not be part of the result,
 which it should store in 
\family typewriter
Q
\family default
.)
\end_layout

\begin_layout Enumerate
[Save link.] Set 
\begin_inset Formula $\mathtt{RLINK(Q)}\gets\mathtt{LLINK(DY)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LLINK(DY)}\gets\mathtt{Q}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{P}\gets\mathtt{P}\$$
\end_inset

.
\end_layout

\begin_layout Enumerate
[Done?] If 
\begin_inset Formula $\mathtt{P}=\mathtt{Y}$
\end_inset

,
 terminate.
 Otherwise go back to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e23324b"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc6[24]
\end_layout

\end_inset

Suppose that the nodes of an 
\emph on
oriented
\emph default
 forest have three link fields,
 
\family typewriter
PARENT
\family default
,
 
\family typewriter
LCHILD
\family default
,
 and 
\family typewriter
RLINK
\family default
,
 but only the 
\family typewriter
PARENT
\family default
 link has been set up to indicate the tree structure.
 The 
\family typewriter
LCHILD
\family default
 field of each node is 
\begin_inset Formula $\Lambda$
\end_inset

 and the 
\family typewriter
RLINK
\family default
 fields are set as a linear list that simply links the nodes together in some order.
 The link variable 
\family typewriter
FIRST
\family default
 points to the first node,
 and the last node has 
\begin_inset Formula $\mathtt{RLINK}=\Lambda$
\end_inset

.
 Design an algorithm that goes through these nodes and fills in the 
\family typewriter
LCHILD
\family default
 and 
\family typewriter
RLINK
\family default
 fields compatible with the 
\family typewriter
PARENT
\family default
 links,
 so that a triply linked tree representation like that in Fig.
 26 is obtained.
 Also,
 reset 
\family typewriter
FIRST
\family default
 so that it now points to the root of the first tree in the representation.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
[Initialize.] Set 
\begin_inset Formula $\mathtt{C}\gets\mathtt{FIRST}$
\end_inset

 and 
\begin_inset Formula $\mathtt{FIRST}\gets\Lambda$
\end_inset

 (we haven't found any root yet).
\end_layout

\begin_layout Enumerate
[Done?] If 
\begin_inset Formula $\mathtt{C}=\Lambda$
\end_inset

,
 terminate.
\end_layout

\begin_layout Enumerate
[Add child.] Set 
\begin_inset Formula $p\gets\mathtt{PARENT(C)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{N}\gets\mathtt{RLINK(C)}$
\end_inset

.
 If 
\begin_inset Formula $p=\Lambda$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{RLINK(C)}\gets\mathtt{FIRST}$
\end_inset

 and 
\begin_inset Formula $\mathtt{FIRST}\gets\mathtt{C}$
\end_inset

,
 otherwise set 
\begin_inset Formula $\mathtt{RLINK(C)}\gets\mathtt{FCHILD(}p\mathtt{)}$
\end_inset

 and 
\begin_inset Formula $\mathtt{FCHILD(}p\mathtt{)}\gets\mathtt{C}$
\end_inset

.
 (In assembly we might just set 
\begin_inset Formula $p$
\end_inset

 to some function of 
\family typewriter
LOC(FIRST)
\family default
 whenever 
\begin_inset Formula $p=\Lambda$
\end_inset

.)
\end_layout

\begin_layout Enumerate
[Advance.] Set 
\begin_inset Formula $\mathtt{C}\gets\mathtt{N}$
\end_inset

 and go to the previous step.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc11[24]
\end_layout

\end_inset

(
\emph on
Equivalence declarations.
\emph default
) Several compiler languages,
 notably FORTRAN,
 provide a facility for overlapping the memory locations assigned to sequentially stored tables.
 The programmer gives the compiler a set of relations of the form 
\begin_inset Formula $\mathtt{X[}j\mathtt{]}\equiv\mathtt{Y[}k\mathtt{]}$
\end_inset

,
 which means that variable 
\begin_inset Formula $\mathtt{X[}j+s\mathtt{]}$
\end_inset

 is to be assigned to the same location as variable 
\begin_inset Formula $\mathtt{Y[}k+s\mathtt{]}$
\end_inset

 for all 
\begin_inset Formula $s$
\end_inset

.
 Each variable is also given a range of allowable subscripts:
 
\begin_inset Quotes eld
\end_inset


\family typewriter
ARRAY X[
\begin_inset Formula $l:u$
\end_inset

]
\family default

\begin_inset Quotes erd
\end_inset

 means that space is to be set aside in memory for the table entries 
\family typewriter
X[
\begin_inset Formula $l$
\end_inset

]
\family default
,
 
\family typewriter
X[
\begin_inset Formula $l+1$
\end_inset

]
\family default
,
 ...,
 
\family typewriter
X[
\begin_inset Formula $u$
\end_inset

]
\family default
.
 For each equivalence class of variables,
 the compiler reserves as small a block of consecutive memory locations as possible,
 to contain all the table entries for the allowable subscript values of these variables.
\end_layout

\begin_layout Standard
For example,
 suppose we have 
\family typewriter
ARRAY X[
\begin_inset Formula $0:10$
\end_inset

]
\family default
,
 
\family typewriter
ARRAY Y[
\begin_inset Formula $3:10$
\end_inset

]
\family default
,
 
\family typewriter
ARRAY A[
\begin_inset Formula $1:1$
\end_inset

]
\family default
,
 and 
\family typewriter
ARRAY Z[
\begin_inset Formula $-2:0$
\end_inset

]
\family default
,
 plus the equivalences 
\begin_inset Formula $\mathtt{X[}7\mathtt{]}\equiv\mathtt{Y[}3\mathtt{]}$
\end_inset

,
 
\begin_inset Formula $\mathtt{Z[}0\mathtt{]}\equiv\mathtt{A[}0\mathtt{]}$
\end_inset

,
 and 
\begin_inset Formula $\mathtt{Y[}1\mathtt{]}\equiv\mathtt{A[}8\mathtt{]}$
\end_inset

.
 We must set aside 20 consecutive locations
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{center}
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}[scale=0.55,circle dotted/.style={
\end_layout

\begin_layout Plain Layout

  dash pattern=on 0 off .55cm,
 line cap=round}]
\end_layout

\begin_layout Plain Layout


\backslash
small
\backslash
def
\backslash
sep{0.15}
\end_layout

\begin_layout Plain Layout


\backslash
def
\backslash
ab#1#2{++(1cm,
\backslash
sep) node[above]{$
\backslash
mathtt{#2}_{#1}$} ++(0,-
\backslash
sep)}
\end_layout

\begin_layout Plain Layout


\backslash
def
\backslash
be#1#2{++(1cm,-
\backslash
sep) node[below]{$
\backslash
mathtt{#2}_{#1}$} ++(0,
\backslash
sep)}
\end_layout

\begin_layout Plain Layout


\backslash
def
\backslash
abe#1#2#3#4{++(1cm,
\backslash
sep) node[above]{$
\backslash
mathtt{#2}_{#1}$}
\end_layout

\begin_layout Plain Layout

               ++(0,-2*
\backslash
sep) node[below]{$
\backslash
mathtt{#4}_{#3}$} ++(0,
\backslash
sep)}
\end_layout

\begin_layout Plain Layout


\backslash
draw[line width = 3,circle dotted] (0,0) -- (19cm,0);
\end_layout

\begin_layout Plain Layout


\backslash
draw (-1,0)
\backslash
be{-2}Z
\backslash
be{-1}Z
\backslash
be0Z
\backslash
be1A ++(1cm,0)
\end_layout

\begin_layout Plain Layout

            
\backslash
ab0X
\backslash
ab1X
\backslash
ab2X
\backslash
ab3X
\backslash
ab4X
\end_layout

\begin_layout Plain Layout

            
\backslash
ab5X
\backslash
ab6X
\backslash
abe7X3Y
\backslash
abe8X4Y
\backslash
abe9X5Y
\end_layout

\begin_layout Plain Layout

            
\backslash
abe{10}X6Y
\backslash
be7Y
\backslash
be8Y
\backslash
be9Y
\backslash
be{10}Y;
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
end{center}
\end_layout

\end_inset

for these variables.
 (The location following 
\begin_inset Formula $\mathtt{A[}1\mathtt{]}$
\end_inset

 is not an allowable subscript value for any of the arrays,
 but it must be reserved anyway.)
\end_layout

\begin_layout Standard
The object of this exercise is to modify Algorithm E so that it applies to the more general situation just described.
 Assume that we are writing a compiler for such a language,
 and the tables inside our compiler program itself have one node for each array,
 containing the fields 
\family typewriter
NAME
\family default
,
 
\family typewriter
PARENT
\family default
,
 
\family typewriter
DELTA
\family default
,
 
\family typewriter
LBD
\family default
,
 and 
\family typewriter
UBD
\family default
.
 Assume that the compiler program has previously processed all the 
\family typewriter
ARRAY
\family default
 declarations,
 so that if 
\family typewriter
ARRAY X[
\begin_inset Formula $l:u$
\end_inset

]
\family default
 has appeared and if 
\family typewriter
P
\family default
 points to the node for 
\family typewriter
X
\family default
,
 then
\begin_inset Formula 
\begin{align*}
\mathtt{NAME(P)} & =\text{``\texttt{X}''}, & \mathtt{PARENT(P)} & =\Lambda, & \mathtt{DELTA(P)} & =0,\\
\mathtt{LBD(P)} & =l, & \mathtt{UBD(P)} & =u.
\end{align*}

\end_inset

The problem is to design an algorithm that processes the equivalence declarations,
 so that,
 after this algorithm has been performed,
\end_layout

\begin_layout Quote
\begin_inset Formula $\mathtt{PARENT(P)}=\Lambda$
\end_inset

 means that locations 
\begin_inset Formula $\mathtt{X[LBD(P)]},...,\mathtt{X[UBD(P)]}$
\end_inset

 are to be reserved in memory for this equivalence class;
\end_layout

\begin_layout Quote
\begin_inset Formula $\mathtt{PARENT(P)}=\mathtt{Q}\neq\Lambda$
\end_inset

 means that location 
\begin_inset Formula $\mathtt{X[}k\mathtt{]}$
\end_inset

 equals location 
\begin_inset Formula $\mathtt{Y[}k+\mathtt{DELTA(P)]}$
\end_inset

,
 where 
\begin_inset Formula $\mathtt{NAME(Q)}=\text{``\texttt{Y}''}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{samepage}
\end_layout

\end_inset

For example,
 before the equivalences listed above we might have the nodes
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
vspace{2pt}
\end_layout

\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="6">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
P
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
NAME(P)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
PARENT(P)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
DELTA(P)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
LBD(P)
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
UBD(P)
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\alpha$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
X
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Lambda$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\beta$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
Y
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Lambda$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
3
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\gamma$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
A
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Lambda$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\delta$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
Z
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\Lambda$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $-2$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
vspace{4pt}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
noindent 
\end_layout

\end_inset

After the equivalences are processed,
 the nodes might appear thus:
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
vspace{2pt}
\end_layout

\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="6">
<features tabularvalignment="middle">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<column alignment="center" valignment="top">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\text{\makebox[\widthof{\texttt{P}}][c]{\ensuremath{\alpha}}}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\text{\makebox[\widthof{\texttt{NAME(P)}}][c]{\texttt{X}}}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\text{\makebox[\widthof{\texttt{PARENT(P)}}][c]{\ensuremath{\Lambda}}}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\text{\makebox[\widthof{\texttt{DELTA(P)}}][c]{\ensuremath{*}}}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\text{\makebox[\widthof{\texttt{LBD(P)}}][c]{\ensuremath{-5}}}$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\text{\makebox[\widthof{\texttt{UBD(P)}}][c]{14}}$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\beta$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
Y
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\alpha$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
4
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $*$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $*$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\gamma$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
A
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\delta$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $*$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $*$
\end_inset


\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\delta$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\family typewriter
Z
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $\alpha$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $-3$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $*$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $*$
\end_inset


\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
noindent 
\end_layout

\end_inset

(
\begin_inset Quotes eld
\end_inset


\begin_inset Formula $*$
\end_inset


\begin_inset Quotes erd
\end_inset

 denotes irrelevant information.)
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{samepage}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Design an algorithm that makes this transformation.
 Assume that inputs to your algorithm have the form 
\begin_inset Formula $(\mathtt{P},j,\mathtt{Q},k)$
\end_inset

,
 denoting 
\begin_inset Formula $\mathtt{X[}j\mathtt{]}\equiv\mathtt{Y[}k\mathtt{]}$
\end_inset

,
 where 
\begin_inset Formula $\mathtt{NAME(P)}=\text{``X''}$
\end_inset

 and 
\begin_inset Formula $\mathtt{NAME(Q)}=\text{``Y''}$
\end_inset

.
 Be sure to check whether the equivalences are contradictory;
 for example,
 
\begin_inset Formula $\mathtt{X[}1\mathtt{]}\equiv\mathtt{Y[}2\mathtt{]}$
\end_inset

 contradicts 
\begin_inset Formula $\mathtt{X[}2\mathtt{]}\equiv\mathtt{Y[}1\mathtt{]}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e23311a"

\end_inset

[Read input.] Read a line 
\begin_inset Formula $(\mathtt{P},j,\mathtt{Q},k)$
\end_inset

,
 but if there are no more lines,
 terminate the algorithm.
\end_layout

\begin_layout Enumerate
[Find roots.] If 
\begin_inset Formula $\mathtt{PARENT(P)}\neq\Lambda$
\end_inset

,
 set 
\begin_inset Formula $j\gets j+\mathtt{DELTA(P)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{P}\gets\mathtt{PARENT(P)}$
\end_inset

,
 and repeat this step.
 If 
\begin_inset Formula $\mathtt{PARENT(Q)}\neq\Lambda$
\end_inset

,
 set 
\begin_inset Formula $k\gets k+\mathtt{DELTA(Q)}$
\end_inset

,
 
\begin_inset Formula $\mathtt{Q}\gets\mathtt{PARENT(Q)}$
\end_inset

,
 and repeat this step.
\end_layout

\begin_layout Enumerate
[Merge trees.] If 
\begin_inset Formula $\mathtt{P}\neq\mathtt{Q}$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{PARENT(P)}\gets\mathtt{Q}$
\end_inset

 
\begin_inset Formula $\mathtt{DELTA(P)}\gets k-j$
\end_inset

,
 
\begin_inset Formula $\mathtt{LBD(Q)}\gets\min\{\mathtt{LBD(Q)},\mathtt{LBD(P)}+\mathtt{DELTA(P)}\}$
\end_inset

,
 
\begin_inset Formula $\mathtt{UBD(Q)}\gets\max\{\mathtt{UBD(Q)},\mathtt{UBD(P)}+\mathtt{DELTA(P)}\}$
\end_inset

.
 Otherwise,
 if 
\begin_inset Formula $j\neq k$
\end_inset

,
 notify a contradiction and terminate the algorithm.
 Finally go to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e23311a"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc17[25]
\end_layout

\end_inset

Algorithm F evaluates a 
\begin_inset Quotes eld
\end_inset

bottom-up
\begin_inset Quotes erd
\end_inset

 locally defined function,
 namely,
 one that should be evaluated at the children of a node before it is evaluated at the node.
 A 
\begin_inset Quotes eld
\end_inset

top-down
\begin_inset Quotes erd
\end_inset

 locally defined function 
\begin_inset Formula $f$
\end_inset

 is one in which the value of 
\begin_inset Formula $f$
\end_inset

 at a node 
\begin_inset Formula $x$
\end_inset

 depends only on 
\begin_inset Formula $x$
\end_inset

 and the value of 
\begin_inset Formula $f$
\end_inset

 at the 
\emph on
parent
\emph default
 of 
\begin_inset Formula $x$
\end_inset

.
 Using an auxiliary stack,
 design an algorithm analogous to Algorithm F that evaluates a 
\begin_inset Quotes eld
\end_inset

top-down
\begin_inset Quotes erd
\end_inset

 function 
\begin_inset Formula $f$
\end_inset

 at each node of a tree.
 (Like Algorithm F,
 your algorithm should work efficiently on trees that have been stored in 
\emph on
postorder
\emph default
 with degrees,
 as in (9).)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
[Initialize.] Set the stack to the single element 
\begin_inset Formula $(\infty,\Lambda)$
\end_inset

,
 and let 
\family typewriter
P
\family default
 point to the 
\emph on
last
\emph default
 ode of the forest in post-order.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:e23317b"

\end_inset

[Evaluate 
\begin_inset Formula $f$
\end_inset

.] Let 
\begin_inset Formula $(d,v)$
\end_inset

 be the value at the top of the stack.
 Evaluate 
\begin_inset Formula $f(\mathtt{NODE(P)},v)$
\end_inset

 and save the result as 
\begin_inset Formula $\mathtt{VALUE(P)}$
\end_inset

.
 Then push 
\begin_inset Formula $(\mathtt{DEGREE(P)},\mathtt{VALUE(P)})$
\end_inset

 to the stack.
\end_layout

\begin_layout Enumerate
[Update the stack.] Pop the element 
\begin_inset Formula $(p,v)$
\end_inset

 from the stack.
 If 
\begin_inset Formula $p=0$
\end_inset

,
 repeat this step.
 Otherwise push 
\begin_inset Formula $(p-1,v)$
\end_inset

 into the stack.
\end_layout

\begin_layout Enumerate
[Advance.] If 
\family typewriter
P
\family default
 is the first node in postorder,
 terminate the algorithm.
 Otherwise set 
\family typewriter
P
\family default
 to its predecessor in postorder and return to step 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e23317b"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
\end_layout

\end_body
\end_document