diff options
Diffstat (limited to 'vol1/2.2.3.lyx')
| -rw-r--r-- | vol1/2.2.3.lyx | 1685 |
1 files changed, 1685 insertions, 0 deletions
diff --git a/vol1/2.2.3.lyx b/vol1/2.2.3.lyx new file mode 100644 index 0000000..0554045 --- /dev/null +++ b/vol1/2.2.3.lyx @@ -0,0 +1,1685 @@ +#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 |