#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
rexerc1[10]
\end_layout

\end_inset

Operation (9) for popping up a stack mentions the possibility of 
\family typewriter
UNDERFLOW
\family default
;
 why doesn't operation (8),
 pushing down a stack,
 mention the possibility of 
\family typewriter
OVERFLOW
\family default
?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Because you can allocate anywhere so this possibility doesn't exist unless you run out of memory,
 a condition already handled by 
\begin_inset Formula $\mathtt{P}\Leftarrow\mathtt{AVAIL}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc5[24]
\end_layout

\end_inset

Operations (14) and (17) give the effect of a queue;
 show how to define the further operation 
\begin_inset Quotes eld
\end_inset

insert at front
\begin_inset Quotes erd
\end_inset

 so as to obtain all the actions of an output-restricted deque.
 How could the operation 
\begin_inset Quotes eld
\end_inset

delete from rear
\begin_inset Quotes erd
\end_inset

 be defined (so that we would have a general deque)?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Inserting at front can be handled with operation (8),
 just like with a stack.
 Deleting from rear is more difficult.
 One could use doubly linked lists,
 which are covered in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Doubly-Linked-Lists"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

.
 Alternatively,
 if we do not want to change the structure,
 we have to iterate from the front,
 with a pointer called 
\family typewriter
I
\family default
:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\left\{ \begin{array}{l}
\text{If }F=\Lambda,\text{ then }\mathtt{UNDERFLOW};\\
\mathtt{Y}\gets\mathtt{INFO(R)},\mathtt{P\gets}\mathtt{LOC(F)};\\
\text{while }\mathtt{LINK(P)\neq R}\text{ repeat }\mathtt{P}\gets\mathtt{LINK(P)};\\
\mathtt{AVAIL}\Leftarrow\mathtt{R},\mathtt{R}\gets\mathtt{P},\mathtt{LINK(P)}\gets\Lambda.
\end{array}\right.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc7[23]
\end_layout

\end_inset

Design an algorithm to 
\begin_inset Quotes eld
\end_inset

invert
\begin_inset Quotes erd
\end_inset

 a linked linear list such as (1),
 that is,
 to change its links so that the items appear in the opposite order.
 [If,
 for example,
 the list (1) were inverted,
 we would have 
\family typewriter
FIRST
\family default
 linking to the node containing item 5;
 that node would link to the one containing item 4;
 etc.] Assume that the nodes have the form (3).
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We use auxiliary pointers 
\family typewriter
P
\family default
,
 
\family typewriter
C
\family default
,
 and 
\family typewriter
N
\family default
.
\end_layout

\begin_layout Enumerate
Set 
\begin_inset Formula $\mathtt{P}\gets\Lambda$
\end_inset

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

.
\end_layout

\begin_layout Enumerate
If 
\begin_inset Formula $\mathtt{C}\neq\Lambda$
\end_inset

,
 set 
\begin_inset Formula $\mathtt{N}\gets\mathtt{LINK(C)}$
\end_inset

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

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

,
 
\begin_inset Formula $\mathtt{C}\gets\mathtt{N}$
\end_inset

,
 and repeat.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\mathtt{FIRST}\gets\mathtt{P}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc11[24]
\end_layout

\end_inset

The result of topological sorting is not always completely determined,
 since there may be several ways to arrange the nodes and to satisfy the conditions of topological order.
 Find all possible ways to arrange the nodes of Fig.
 6 into topological order.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

First we draw it in a way that simplifies reasoning,
 with all arrows pointing downwards or to the right:
\end_layout

\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

1 ---> 3 ---> 7 ---> 4
\end_layout

\begin_layout Plain Layout

              |      |
\end_layout

\begin_layout Plain Layout

              v      |
\end_layout

\begin_layout Plain Layout

       9 ---> 5      |
\end_layout

\begin_layout Plain Layout

       |      |      |
\end_layout

\begin_layout Plain Layout

       v      v      v
\end_layout

\begin_layout Plain Layout

       2 ---> 8 ---> 6
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Then we explore possibilities by following the idea in algorithm T but backtracking.
 We suppress the arrows for compactness.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\begin{array}{cccccc}
137492586 & 137495286 & 137924586 & 137925486 & 137925846 & 137942586\\
137945286 & 137952486 & 137952846 & 137954286 & 139274586 & 139275486\\
139275846 & 139724586 & 139725486 & 139725846 & 139742586 & 139745286\\
139752486 & 139752846 & 139754286 & 192374586 & 192375486 & 192375846\\
193274586 & 193275486 & 193275846 & 193724586 & 193725486 & 193725846\\
193742586 & 193745286 & 193752486 & 193752846 & 193754286 & 912374586\\
912375486 & 912375846 & 913274586 & 913275486 & 913275846 & 913724586\\
913725486 & 913725846 & 913742586 & 913745286 & 913752486 & 913752846\\
913754286 & 921374586 & 921375486 & 921375846
\end{array}
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Note Note
status open

\begin_layout Plain Layout
TODO verify from here
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc17[21]
\end_layout

\end_inset

 What output does Algorithm T produce if it is presented with the input (18)?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We follow the algorithm with the following table:
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="11">
<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">
<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" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
1
\end_layout

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

\begin_layout Plain Layout
2
\end_layout

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

\begin_layout Plain Layout
3
\end_layout

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

\begin_layout Plain Layout
4
\end_layout

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

\begin_layout Plain Layout
5
\end_layout

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

\begin_layout Plain Layout
6
\end_layout

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

\begin_layout Plain Layout
7
\end_layout

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

\begin_layout Plain Layout
8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
9
\end_layout

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

\begin_layout Plain Layout

\family typewriter
QLINK
\family default
/
\family typewriter
COUNT
\end_layout

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

\begin_layout Plain Layout
1
\end_layout

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

\begin_layout Plain Layout
9
\end_layout

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

\begin_layout Plain Layout
7
\end_layout

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

\begin_layout Plain Layout
2
\end_layout

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

\begin_layout Plain Layout
5
\end_layout

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

\begin_layout Plain Layout
8
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
4
\end_layout

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

\begin_layout Plain Layout
6
\end_layout

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

\begin_layout Plain Layout
3
\end_layout

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

\begin_layout Plain Layout

\family typewriter
TOP
\end_layout

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

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" 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" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $8.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $7.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $6.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $8.$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" 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" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $4,5.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $6.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $5,2.$
\end_inset


\end_layout

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

\begin_layout Plain Layout

\end_layout

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

\begin_layout Plain Layout

\family typewriter
N:
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout

\family typewriter
F:
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout

\family typewriter
R:
\end_layout

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

\begin_layout Plain Layout
6
\end_layout

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

\begin_layout Plain Layout

\family typewriter
P:
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" 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" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

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

\end_inset


\end_layout

\begin_layout Standard
To get the output 
\begin_inset Formula $1\to9\to3\to2\to7\to4\to5\to8\to6(\to0)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc20[24]
\end_layout

\end_inset

Algorithm T uses 
\family typewriter
F
\family default
,
 
\family typewriter
R
\family default
,
 and the 
\family typewriter
QLINK
\family default
 table to obtain the effect of a queue that contains those nodes whose 
\family typewriter
COUNT
\family default
 field has become zero but whose successor relations have not yet been removed.
 Could a stack be used for this purpose instead of a queue?
 If so,
 compare the resulting algorithm with Algorithm T.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Yes,
 because those are nodes that we can already print next after the ones that we have already printed.
 The differences would be:
\end_layout

\begin_layout Enumerate
In T4,
 we would do 
\begin_inset Formula $\mathtt{T}\gets0$
\end_inset

 and,
 for each 
\begin_inset Formula $1\leq k\leq n$
\end_inset

 with 
\begin_inset Formula $\mathtt{COUNT[}k\mathtt{]}=0$
\end_inset

,
 
\begin_inset Formula $\mathtt{QLINK[}k\mathtt{]}\gets\mathtt{T}$
\end_inset

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

.
\end_layout

\begin_layout Enumerate
In T5,
 we would output the value of 
\family typewriter
T
\family default
 rather than 
\family typewriter
F
\family default
,
 and instead of 
\begin_inset Formula $\mathtt{P}\gets\mathtt{TOP[F]}$
\end_inset

 we would do 
\begin_inset Formula $\mathtt{P}\gets\mathtt{TOP[T]}$
\end_inset

.
 We would do 
\begin_inset Formula $\mathtt{T}\gets\mathtt{QLINK[T]}$
\end_inset

 right after T5 instead of doing T7.
\end_layout

\begin_layout Enumerate
In T6,
 the two assignments involving 
\family typewriter
R
\family default
 would instead be 
\begin_inset Formula $\mathtt{QLINK[SUC(P)]}\gets\mathtt{T}$
\end_inset

 and 
\begin_inset Formula $\mathtt{T}\gets\mathtt{SUC(P)}$
\end_inset

.
\end_layout

\begin_layout Standard
Then we wouldn't need 
\begin_inset Formula $\mathtt{QLINK[}0\mathtt{]}$
\end_inset

.
 With input (18),
 this would work as follows:
\end_layout

\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="4" columns="10">
<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">
<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" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

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

\begin_layout Plain Layout
1
\end_layout

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

\begin_layout Plain Layout
2
\end_layout

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

\begin_layout Plain Layout
3
\end_layout

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

\begin_layout Plain Layout
4
\end_layout

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

\begin_layout Plain Layout
5
\end_layout

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

\begin_layout Plain Layout
6
\end_layout

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

\begin_layout Plain Layout
7
\end_layout

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

\begin_layout Plain Layout
8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
9
\end_layout

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

\begin_layout Plain Layout

\family typewriter
QLINK
\family default
/
\family typewriter
COUNT
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
1
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
4
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout
4
\end_layout

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

\begin_layout Plain Layout
1
\end_layout

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

\begin_layout Plain Layout

\family typewriter
TOP
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" 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" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $8.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $7.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $6.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $8.$
\end_inset


\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" 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" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
\begin_inset Formula $4,5.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $6.$
\end_inset


\end_layout

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

\begin_layout Plain Layout
\begin_inset Formula $5,2.$
\end_inset


\end_layout

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

\begin_layout Plain Layout

\end_layout

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

\begin_layout Plain Layout

\family typewriter
N:
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout

\family typewriter
T:
\end_layout

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

\begin_layout Plain Layout
0
\end_layout

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

\begin_layout Plain Layout

\family typewriter
P:
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" 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" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

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

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

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

\end_inset


\end_layout

\begin_layout Standard
Output:
 
\begin_inset Formula $9\to2\to1\to3\to7\to5\to8\to4\to6(\to0)$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc29[21]
\end_layout

\end_inset


\end_layout

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

\end_inset

Give an algorithm to 
\begin_inset Quotes eld
\end_inset

erase
\begin_inset Quotes erd
\end_inset

 an entire list like (1),
 by putting all of its nodes on the 
\family typewriter
AVAIL
\family default
 stack,
 given only the value of 
\family typewriter
FIRST
\family default
.
 The algorithm should operate as fast as possible.
\end_layout

\begin_layout Enumerate
Repeat part 
\begin_inset CommandInset ref
LatexCommand ref
reference "enu:e22429a"
plural "false"
caps "false"
noprefix "false"
nolink "false"

\end_inset

 for a list like (12),
 given the values of 
\family typewriter
F
\family default
 and 
\family typewriter
R
\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
If 
\begin_inset Formula $\mathtt{FIRST}=\Lambda$
\end_inset

,
 we don't have to do anything.
 Otherwise,
 let 
\begin_inset Formula $\mathtt{P}\gets\mathtt{FIRST}$
\end_inset

,
 if 
\begin_inset Formula $\mathtt{LINK(P)}\neq\emptyset$
\end_inset

 then 
\begin_inset Formula $\mathtt{P}\gets\mathtt{LINK(P)}$
\end_inset

 and repeat,
 finally set 
\begin_inset Formula $\mathtt{LINK(P)}\gets\mathtt{AVAIL}$
\end_inset

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

.
\end_layout

\begin_layout Enumerate
Just set 
\begin_inset Formula $\mathtt{LINK(R)}\gets\mathtt{AVAIL}$
\end_inset

 and 
\begin_inset Formula $\mathtt{AVAIL}\gets\mathtt{F}$
\end_inset

.
 This works even if the queue is empty.
\end_layout

\end_body
\end_document