path: root/vol1/2.1.lyx

#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
\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
exerc1[04]
\end_layout

\end_inset

In the situation depicted in (3),
 what is the value of
\end_layout

\begin_layout Enumerate

\family typewriter
SUIT(NEXT(TOP))
\family default
;
\end_layout

\begin_layout Enumerate

\family typewriter
NEXT(NEXT(NEXT(TOP)))
\family default
?
\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
4.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\Lambda$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc2[10]
\end_layout

\end_inset

The text points out that in many cases 
\begin_inset Formula $\mathtt{CONTENTS(LOC(V))}=\mathtt{V}$
\end_inset

.
 Under what conditions do we have 
\begin_inset Formula $\mathtt{LOC(CONTENTS(V))}=\mathtt{V}$
\end_inset

?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\family typewriter
V
\family default
 must be a valid memory address different from 
\begin_inset Formula $\Lambda$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc5[21]
\end_layout

\end_inset

Give an algorithm that essentially undoes the effect of exercise 4:
 Assuming that the pile is not empty and that its bottom card is face down,
 your algorithm should remove the bottom card and make 
\family typewriter
NEWCARD
\family default
 link to it.
 (This algorithm is sometimes called 
\begin_inset Quotes eld
\end_inset

cheating
\begin_inset Quotes erd
\end_inset

 in solitaire games.)
\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
If 
\begin_inset Formula $\mathtt{NEXT(TOP)}=\Lambda$
\end_inset

,
 let 
\begin_inset Formula $\mathtt{NEWCARD}\gets\mathtt{TOP}$
\end_inset

,
 
\begin_inset Formula $\mathtt{TOP}\gets\Lambda$
\end_inset

 and terminate.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\mathtt{X}\gets\mathtt{TOP}$
\end_inset

,
 
\begin_inset Formula $\mathtt{Y}\gets\mathtt{NEXT(TOP)}$
\end_inset

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $\mathtt{NEXT(Y)}\neq\Lambda$
\end_inset

,
 let 
\begin_inset Formula $\mathtt{X}\gets\mathtt{Y}$
\end_inset

,
 
\begin_inset Formula $\mathtt{Y}\gets\mathtt{NEXT(Y)}$
\end_inset

 and repeat this step.
\end_layout

\begin_layout Enumerate
Set 
\begin_inset Formula $\mathtt{NEWCARD}\gets\mathtt{Y}$
\end_inset

 and 
\begin_inset Formula $\mathtt{NEXT(X)}\gets\Lambda$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc6[06]
\end_layout

\end_inset

In the playing card example,
 suppose that 
\family typewriter
CARD
\family default
 is the name of a variable whose value is an entire node as in (6).
 The operation 
\begin_inset Formula $\mathtt{CARD}\gets\mathtt{NODE(TOP)}$
\end_inset

 sets the fields of 
\family typewriter
CARD
\family default
 respectively equal to those of the top of the pile.
 After this operation,
 which of the following notations stands for the suit of the top card?
\end_layout

\begin_layout Enumerate

\family typewriter
SUIT(CARD)
\family default
;
\end_layout

\begin_layout Enumerate

\family typewriter
SUIT(LOC(CARD))
\family default
;
\end_layout

\begin_layout Enumerate

\family typewriter
SUIT(CONTENTS(CARD))
\family default
;
\end_layout

\begin_layout Enumerate

\family typewriter
SUIT(TOP)
\family default
?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset

2 and 4.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc7[04]
\end_layout

\end_inset

In the text's example 
\family typewriter
MIX
\family default
 program,
 (5),
 the link variable 
\family typewriter
TOP
\family default
 is stored in the 
\family typewriter
MIX
\family default
 computer word whose assembly language name is 
\family typewriter
TOP
\family default
.
 Given the field structure (1),
 which of the following sequences of code brings the quantity 
\family typewriter
NEXT(TOP)
\family default
 into register A?
 Explain why the other sequence is incorrect.
\end_layout

\begin_layout Enumerate

\family typewriter
LDA TOP(NEXT)
\end_layout

\begin_layout Enumerate

\family typewriter
LD1 TOP
\begin_inset Newline newline
\end_inset

LDA 0,1(NEXT)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset

2,
 since the first loads the field 
\family typewriter
NEXT
\family default
 from the memory word 
\family typewriter
TOP
\family default
,
 that only contains the address,
 instead of from the node that 
\family typewriter
TOP
\family default
 points to.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc8[18]
\end_layout

\end_inset

Write a 
\family typewriter
MIX
\family default
 program corresponding to steps B1–B3.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

NEXT  EQU  4:5
\end_layout

\begin_layout Plain Layout

LLEN  STJ  CHECK
\end_layout

\begin_layout Plain Layout

      ENTA 0         ;
 B1
\end_layout

\begin_layout Plain Layout

      ENT1 TOP
\end_layout

\begin_layout Plain Layout

2H    J1Z  *         ;
 B2
\end_layout

\begin_layout Plain Layout

      INCA 1         ;
 B3
\end_layout

\begin_layout Plain Layout

      LD1  0,1(NEXT)
\end_layout

\begin_layout Plain Layout

      JMP  2B
\end_layout

\end_inset


\end_layout

\end_body
\end_document