path: root/vol1/2.2.5.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
\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
rexerc2[22]
\end_layout

\end_inset

Explain why a list that is singly linked cannot allow efficient operation as a general deque;
 the deletion of items can be done efficiently at only one end of a singly linked list.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

One could,
 in fact,
 implement it reasonably efficiently using the trick from Exercise 2.2.4.18.
 If we assume a normal linked list,
 however,
 deletion of an element requires knowing the link to the previous element.
 We know this for the head of the list,
 as we just have to change the pointer to the head,
 but we do not know it for the tail,
 and if we cached a pointer to the second-to-last element to do this,
 then we would need to update this pointer to point to the new second-to-last element,
 whose address we cannot retrieve efficiently.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc3[22]
\end_layout

\end_inset

The elevator system described in the text uses three call variables,
 
\family typewriter
CALLUP
\family default
,
 
\family typewriter
CALLCAR
\family default
,
 and 
\family typewriter
CALLDOWN
\family default
,
 for each floor,
 representing buttons that have been pushed by the users in the system.
 It is conceivable that the elevator actually needs only one or two binary variables for the call buttons on each floor,
 instead of three.
 Explain how an experimenter could push buttons in a certain sequence with this elevator system to 
\emph on
prove
\emph default
 that there are three independent binary variables for each floor (except the top and bottom floors).
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We need an experiment that proves that,
 for any given floor that is not the top or bottom one,
 the elevator behaves differently for each of the 8 possible combinations of the 3 buttons.
\end_layout

\begin_layout Standard
Let us denote the states by the values of 
\family typewriter
CALLUP
\family default
,
 
\family typewriter
CALLCAR
\family default
 and 
\family typewriter
CALLDOWN
\family default
 in sequence,
 so for example only 
\family typewriter
CALLUP
\family default
 would be 100 and all buttons at once would be 111.
\end_layout

\begin_layout Standard
We first note that the three buttons are not completely independent:
 101 and 111 are equal,
 because the elevator would stop in both directions and then one of 
\family typewriter
CALLUP
\family default
 and 
\family typewriter
CALLDOWN
\family default
 is cleared at the same time as 
\family typewriter
CALLCAR
\family default
 is,
 so there's no observable difference,
 but this state and all others are pairwise different,
 as we shall see.
\end_layout

\begin_layout Standard
000 is trivially different from all the other states since,
 if the elevator is in another floor,
 any other combination would take it to our floor.
 If the elevator is in the lower floor and we call 001 in the current and above floors,
 it would go to the floor above and then to the current one,
 the opposite of what would happen if in the current floor we would call any combination involving 
\family typewriter
CALLUP
\family default
 or 
\family typewriter
CALLCAR
\family default
.
 The opposite experiment (calling 100 in the current and below floors with the elevator in the one above,
 and then changing what we call in the current floor) shows that 100 is also different from all the others.
\end_layout

\begin_layout Standard
To see that 010 and 101 are different,
 we press 
\family typewriter
CALLCAR
\family default
 in the current floor with the elevator in the one above and,
 while it's going down,
 press 
\family typewriter
CALLUP
\family default
 in the floor below and tell it to go two floors up.
 Our design wouldn't stop in our floor when going up,
 but it would if we had pressed both 
\family typewriter
CALLUP
\family default
 and 
\family typewriter
CALLDOWN
\family default
 since 
\family typewriter
CALLUP
\family default
 would still be 1 after stopping when going down.
 Actually,
 this shows that 010 and 011 are different from 101,
 110,
 and 111,
 and the opposite experiment shows that 010 and 110 are different from 101,
 011,
 and 111.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc11[21]
\end_layout

\end_inset

(
\emph on
A sparse-update memory.
\emph default
) The following problem often arises in 
\emph on
synchronous
\emph default
 simulations:
 The system has 
\begin_inset Formula $n$
\end_inset

 variables 
\begin_inset Formula $\mathtt{V[}1\mathtt{]},\dots,\mathtt{V[}n\mathtt{]}$
\end_inset

,
 and at every simulated step new values for some of them are calculated from the old values.
 These calculations are assumed to be done 
\begin_inset Quotes eld
\end_inset

simultaneously
\begin_inset Quotes erd
\end_inset

 in the sense that the variables do not change to their new values until after all assignments have been made.
 Thus,
 the two statements
\begin_inset Formula 
\begin{align*}
\mathtt{V[}1\mathtt{]} & \gets\mathtt{V[}2\mathtt{]} &  & \text{and} &  & \mathtt{V[}2\mathtt{]}\gets\mathtt{V[}1\mathtt{]}
\end{align*}

\end_inset

appearing at the same simulated time would interchange the values of 
\begin_inset Formula $\mathtt{V[}1\mathtt{]}$
\end_inset

 and 
\begin_inset Formula $\mathtt{V[}2\mathtt{]}$
\end_inset

;
 this is quite different from what would happen in a sequential calculation.
\end_layout

\begin_layout Standard
The desired action can of course be simulated by keeping an additional table 
\begin_inset Formula $\mathtt{NEWV[}1\mathtt{]},\dots,\mathtt{NEWV[}n\mathtt{]}$
\end_inset

.
 Before each simulated step,
 we could set 
\begin_inset Formula $\mathtt{NEWV[}k\mathtt{]}\gets\mathtt{V[}k\mathtt{]}$
\end_inset

 for 
\begin_inset Formula $1\leq k\leq n$
\end_inset

,
 then record all changes of 
\begin_inset Formula $\mathtt{V[}k\mathtt{]}$
\end_inset

 in 
\begin_inset Formula $\mathtt{NEWV[}k\mathtt{]}$
\end_inset

,
 and finally,
 after the step we could set 
\begin_inset Formula $\mathtt{V[}k\mathtt{]}\gets\mathtt{NEWV[}k\mathtt{]}$
\end_inset

,
 
\begin_inset Formula $1\leq k\leq n$
\end_inset

.
 But this 
\begin_inset Quotes eld
\end_inset

brute force
\begin_inset Quotes erd
\end_inset

 approach is not completely satisfactory,
 for the following reasons:
\end_layout

\begin_layout Enumerate
Often 
\begin_inset Formula $n$
\end_inset

 is very large,
 but the number of variables changed per step is rather small.
\end_layout

\begin_layout Enumerate
The variables are often not arranged in a nice table 
\begin_inset Formula $\mathtt{V[}1\mathtt{]},\dots,\mathtt{V[}n\mathtt{]}$
\end_inset

,
 but are scattered throughout memory in a rather chaotic fashion.
\end_layout

\begin_layout Enumerate
This method does not detect the situation (usually an error in the model) when one variable is given two values in the same simulated stop.
\end_layout

\begin_layout Enumerate
Assuming that the number of variables changed per step is rather small,
 design an efficient algorithm that simulates the desired actions,
 using two auxiliary tables 
\begin_inset Formula $\mathtt{NEWV[}k\mathtt{]}$
\end_inset

 and 
\begin_inset Formula $\mathtt{LINK[}k\mathtt{]}$
\end_inset

,
 
\begin_inset Formula $1\leq k\leq n$
\end_inset

.
 If possible,
 your algorithm should give an error stop if the same variables is being given two different values in the same step.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The idea,
 of course,
 would be to make a linked list with the 
\family typewriter
LINK
\family default
 table.
 If we assume the table is initially set to 0,
 we could use 
\begin_inset Formula $-1$
\end_inset

 to signify the end of the linked list.
\end_layout

\begin_layout Enumerate
[Initialize.] (This step only happens at the beginning of the simulation.) Set 
\begin_inset Formula $\mathtt{LINK[}k\mathtt{]}\gets0$
\end_inset

,
 
\begin_inset Formula $1\leq k\leq n$
\end_inset

,
 
\begin_inset Formula $\mathtt{Q}\gets-1$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset CommandInset label
LatexCommand label
name "enu:25521b"

\end_inset

[Advance time.] Advance to the next step of the synchronous simulation.
\end_layout

\begin_layout Enumerate
[Run the current state.] For each calculation that needs to be done,
 if 
\begin_inset Formula $k$
\end_inset

 is the variable to be updated,
 raise an error if 
\begin_inset Formula $\mathtt{LINK[}k\mathtt{]}\neq0$
\end_inset

,
 calculate the new value,
 store it in 
\begin_inset Formula $\mathtt{NEWV[}k\mathtt{]}$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{LINK[}k\mathtt{]}\gets\mathtt{Q}$
\end_inset

 and 
\begin_inset Formula $\mathtt{Q}\gets k$
\end_inset

.
\end_layout

\begin_layout Enumerate
[Update variables.] If 
\begin_inset Formula $\mathtt{Q}>0$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{V[Q]}\gets\mathtt{NEWV[Q]}$
\end_inset

,
 
\begin_inset Formula $\mathtt{Q2}\gets\mathtt{LINK[Q]}$
\end_inset

,
 
\begin_inset Formula $\mathtt{LINK[Q]}\gets0$
\end_inset

,
 
\begin_inset Formula $\mathtt{Q}\gets\mathtt{LINK[Q]}$
\end_inset

,
 and repeat this step.
 Otherwise go to 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:25521b"
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
rexerc12[22]
\end_layout

\end_inset

Why is it a good idea to use doubly linked lists instead of singly linked or sequential lists in the simulation program of this section?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

This is because we often delete nodes from the middle of the list without knowing the predecessor or successor,
 like an user who was tired of waiting,
 and doubly linked lists are the only kind that allows doing this efficiently.
\end_layout

\end_body
\end_document