path: root/vol1/2.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[06]
\end_layout

\end_inset

An input-restricted deque is a linear list in which items may be inserted at one end but removed from either end;
 clearly an input-restricted deque can operate either as a stack or as a queue,
 if we consistently remove all items from one of the two ends.
 Can an output-restricted deque also be operated either as a stack or as a queue?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Yes.
 If output happens on the left,
 we can use a deque as a queue by inserting on the right or as a stack by inserting on the left.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc2[15]
\end_layout

\end_inset

Imagine four railroad cars positioned on the input side of the track in Fig.
 1,
 numbered 1,
 2,
 3,
 and 4,
 from left to right.
 Suppose we perform the following sequence of operations (which is compatible with the direction of the arrows in the diagram and does not require cars to 
\begin_inset Quotes eld
\end_inset

jump over
\begin_inset Quotes erd
\end_inset

 other cars):
 (i) move car 1 into the stack;
 (ii) move car 2 into the stack;
 (iii) move car 2 into the output;
 (iv) move car 3 into the stack;
 (v) move car 4 into the stack;
 (vi) move car 4 into the output;
 (vii) move car 3 into the output;
 (viii) move car 1 into the output.
\end_layout

\begin_layout Standard
As a result of these operations the original order of the cars,
 
\begin_inset Formula $1\,2\,3\,4$
\end_inset

,
 has been changed into 
\begin_inset Formula $2\,4\,3\,1$
\end_inset

.
 
\emph on
It is the purpose of this exercise and the following exercises to examine what permutations are obtainable in such a manner from stacks,
 queues,
 or deques.
\end_layout

\begin_layout Standard
If there are six railroad cars numbered 
\begin_inset Formula $1\,2\,3\,4\,5\,6$
\end_inset

,
 can they be permuted into the order 
\begin_inset Formula $3\,2\,5\,6\,4\,1$
\end_inset

?
 Can they be permuted into the order 
\begin_inset Formula $1\,5\,4\,6\,2\,3$
\end_inset

?
 (In case it is possible,
 show how to do it.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

For 
\begin_inset Formula $3\,2\,5\,6\,4\,1$
\end_inset

,
 we push 1,
 push 2,
 push 3,
 pop 3,
 pop 2,
 push 4,
 push 5,
 pop 5,
 push 6,
 pop 6,
 pop 4,
 and pop 1.
 We can't get the permutation 
\begin_inset Formula $1\,5\,4\,6\,2\,3$
\end_inset

:
 first,
 we'd need to push 1 and pop it immediately since,
 otherwise,
 it couldn't be the first car to go out;
 then we need to push trains 2 to 5 without popping anything before the 5,
 so that no car is between the 1 and the 5,
 but then we must pop 3 before popping 2,
 so the order wouldn't be respected.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc5[M28]
\end_layout

\end_inset

Show that it is possible to obtain a permutation 
\begin_inset Formula $p_{1}\,p_{2}\,\dots\,p_{n}$
\end_inset

 from 
\begin_inset Formula $1\,2\,\dots\,n$
\end_inset

 using a stack if and only if there are no indices 
\begin_inset Formula $i<j<k$
\end_inset

 such that 
\begin_inset Formula $p_{j}<p_{k}<p_{i}$
\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 Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies]$
\end_inset


\end_layout

\end_inset

Assume,
 by contradiction,
 that there are such indexes.
 When the next element to pop is 
\begin_inset Formula $p_{i}$
\end_inset

,
 
\begin_inset Formula $p_{i}$
\end_inset

 is either at the top of the stack or in the input road.
 In the second case,
 the only valid option is to push all elements from the input until reaching 
\begin_inset Formula $p_{i}$
\end_inset

 and then pop 
\begin_inset Formula $p_{i}$
\end_inset

,
 so in either case,
 
\begin_inset Formula $p_{j}$
\end_inset

 and 
\begin_inset Formula $p_{k}$
\end_inset

 end up in the stack after popping 
\begin_inset Formula $p_{i}$
\end_inset

.
 Then 
\begin_inset Formula $p_{k}$
\end_inset

 has to remain in the stack until the next element is 
\begin_inset Formula $p_{k}$
\end_inset

,
 and in particular it has to remain after popping 
\begin_inset Formula $p_{j}$
\end_inset

,
 but since higher elements in the stack have higher values (this is easily proved by induction on the size of the stack),
 
\begin_inset Formula $p_{k}$
\end_inset

 is over 
\begin_inset Formula $p_{j}$
\end_inset

 and thus it must be popped before popping 
\begin_inset Formula $p_{j}$
\end_inset

,
 giving an incorrect order to the output.
\end_layout

\begin_layout Itemize
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Let's consider the following algorithm for generating such permutation:
 we set 
\begin_inset Formula $m\gets1$
\end_inset

,
 and for 
\begin_inset Formula $j\gets1$
\end_inset

 to 
\begin_inset Formula $n$
\end_inset

,
 if 
\begin_inset Formula $p_{j}\geq m$
\end_inset

,
 we push elements 
\begin_inset Formula $m$
\end_inset

 to 
\begin_inset Formula $p_{j}$
\end_inset

,
 pop 
\begin_inset Formula $p_{j}$
\end_inset

 and set 
\begin_inset Formula $m\gets p_{j}+1$
\end_inset

,
 and otherwise we just pop 
\begin_inset Formula $p_{j}$
\end_inset

.
 In this algorithm,
 
\begin_inset Formula $m$
\end_inset

 represents the next element to be pushed and 
\begin_inset Formula $j$
\end_inset

 is such that 
\begin_inset Formula $p_{j}$
\end_inset

 is to be popped,
 so 
\begin_inset Formula $j\leq m$
\end_inset

 at the beginning of every iteration.
 Thus,
 if 
\begin_inset Formula $p_{j}\geq m$
\end_inset

,
 the car is still in the input road and we have to push elements 
\begin_inset Formula $m$
\end_inset

 to 
\begin_inset Formula $p_{j}$
\end_inset

,
 and otherwise 
\begin_inset Formula $p_{j}$
\end_inset

 is in the stack.
\end_layout

\begin_deeper
\begin_layout Standard
We show that,
 in the latter case,
 if 
\begin_inset Formula $p_{j}$
\end_inset

 weren't at the top of the stack,
 there would be indices 
\begin_inset Formula $i<j$
\end_inset

 and 
\begin_inset Formula $k>j$
\end_inset

 such that 
\begin_inset Formula $p_{j}<p_{k}<p_{i}$
\end_inset

.
 If 
\begin_inset Formula $p_{j}$
\end_inset

 is in the stack but not as the top element,
 the latest operations have been pushing 
\begin_inset Formula $m',m'+1,\dots,p_{i}$
\end_inset

 for some 
\begin_inset Formula $i<j$
\end_inset

 (
\begin_inset Formula $m'$
\end_inset

 is the value of 
\begin_inset Formula $m$
\end_inset

 when processing 
\begin_inset Formula $i$
\end_inset

) and,
 after that,
 to popping 
\begin_inset Formula $p_{i},p_{i}-1,\dots,p_{j}+c$
\end_inset

 for some 
\begin_inset Formula $c\in\{2,\dots,j-i\}$
\end_inset

,
 since at least 
\begin_inset Formula $p_{i}$
\end_inset

 is popped and at least 
\begin_inset Formula $p_{j}+1$
\end_inset

 is not popped (otherwise,
 either 
\begin_inset Formula $p_{j}$
\end_inset

 would have been popped too or it would be at the top).
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $k$
\end_inset

 be the element such that 
\begin_inset Formula $p_{k}=p_{j}+1$
\end_inset

,
 so that 
\begin_inset Formula $p_{j}<p_{k}<p_{i}$
\end_inset

.
 We have 
\begin_inset Formula $i<j$
\end_inset

 because 
\begin_inset Formula $p_{i}$
\end_inset

 was popped earlier than 
\begin_inset Formula $p_{j}$
\end_inset

,
 and we have to show that 
\begin_inset Formula $j<k$
\end_inset

.
 If it were 
\begin_inset Formula $k<j$
\end_inset

,
 
\begin_inset Formula $p_{k}$
\end_inset

 would have already been popped,
 clearly before 
\begin_inset Formula $i$
\end_inset

,
 but then it would be 
\begin_inset Formula $k<i$
\end_inset

 and,
 because the value of 
\begin_inset Formula $m$
\end_inset

 when processing 
\begin_inset Formula $k$
\end_inset

 would be 
\begin_inset Formula $m''\leq m'\leq p_{j}<p_{k}$
\end_inset

,
 we'd have pushed 
\begin_inset Formula $p_{j}$
\end_inset

 when processing 
\begin_inset Formula $k$
\end_inset

,
 not when processing 
\begin_inset Formula $i\#$
\end_inset

.
 Since 
\begin_inset Formula $k\neq j$
\end_inset

,
 we conclude that 
\begin_inset Formula $j<k$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc6[00]
\end_layout

\end_inset

Consider the problem of exercise 2,
 with a queue substituted for a stack.
 What permutations of 
\begin_inset Formula $1\,2\,\dots\,n$
\end_inset

 can be obtained with use of a queue?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Just one;
 a queue would be represented by a bare straight line.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc7[25]
\end_layout

\end_inset

Consider the problem of exercise 2,
 with a deque substituted for a stack.
\end_layout

\begin_layout Enumerate
Find a permutation of 
\begin_inset Formula $1\,2\,3\,4$
\end_inset

 that can be obtained with an input-restricted deque,
 but it cannot be obtained with an output-restricted deque.
\end_layout

\begin_layout Enumerate
Find a permutation of 
\begin_inset Formula $1\,2\,3\,4$
\end_inset

 that can be obtained with an output-restricted deque but not with an input-restricted deque.
 [As a consequence of (1) and (2),
 there is definitely a difference between input-restricted and output-restricted deques.]
\end_layout

\begin_layout Enumerate
Find a permutation of 
\begin_inset Formula $1\,2\,3\,4$
\end_inset

 that cannot be obtained with either an input-restricted or an output-restricted deque.
\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 Formula $4\,1\,3\,2$
\end_inset

 (input all from the right,
 output 4 right,
 1 left,
 3 right,
 then 2).
 With an output-restricted deque,
 to output the 4,
 we'd first have to put 1,
 2,
 and 3 in the deque and (here lies the difference) in the order of the permutation.
 But,
 after inserting the 1,
 we'd have to insert the 2 at the right and then we'd have no place for the 3.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $4\,2\,1\,3$
\end_inset

 (input 1 wherever,
 2 left,
 3 right,
 4 left,
 then output all to the left).
 With an input-restricted deque,
 to output the 4,
 we'd first have to put 1,
 2,
 and 3 in the deque and (here lies the difference) in the order of the input.
 Then we'd have to output 2,
 which is just between 1 and 3.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $4\,2\,3\,1$
\end_inset

.
 With an input-restricted deque,
 to output the 4,
 we'd have to input 1,
 2,
 3 first,
 but then we'd have to output the 2 which lies in the middle.
 With an output-restricted deque,
 we'd have to input 1,
 2,
 3 first in the order 2,
 3,
 1,
 so we'd have to put the 2 to the left of the 1 but then we couldn't place the 3 in the middle.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc14[26]
\end_layout

\end_inset

Suppose you are allowed to use only stacks as data structures.
 How can you implement a queue efficiently with two stacks?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Let 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 be two stacks (elements go from the top of 
\begin_inset Formula $A$
\end_inset

 to the bottom and from the bottom of 
\begin_inset Formula $B$
\end_inset

 to the top).
 To enqueue an element,
 we push it to 
\begin_inset Formula $A$
\end_inset

 (we could push it to 
\begin_inset Formula $B$
\end_inset

 if 
\begin_inset Formula $B$
\end_inset

 is empty).
 To deque an element,
 if 
\begin_inset Formula $B$
\end_inset

 is empty,
 we do 
\begin_inset Formula $x\Leftarrow A,B\Leftarrow x$
\end_inset

 until 
\begin_inset Formula $A$
\end_inset

 is empty;
 if 
\begin_inset Formula $B$
\end_inset

 is still empty,
 the queue is empty,
 and otherwise we pop the element from 
\begin_inset Formula $B$
\end_inset

.
 The time needed to copy 
\begin_inset Formula $n$
\end_inset

 elements from 
\begin_inset Formula $A$
\end_inset

 to 
\begin_inset Formula $B$
\end_inset

 is generally amortized as we won't need to copy for the following 
\begin_inset Formula $n$
\end_inset

 deletions.
\end_layout

\end_body
\end_document