1 files changed, 910 insertions, 0 deletions
diff --git a/vol1/2.2.1.lyx b/vol1/2.2.1.lyx
new file mode 100644
index 0000000..27287f7
--- /dev/null
+++ b/vol1/2.2.1.lyx
@@ -0,0 +1,910 @@
+#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