From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Fri, 16 May 2025 22:18:44 +0200
Subject: Changed layout for more manageable volumes

---
 2.2.1.lyx | 910 --------------------------------------------------------------
 1 file changed, 910 deletions(-)
 delete mode 100644 2.2.1.lyx

(limited to '2.2.1.lyx')

diff --git a/2.2.1.lyx b/2.2.1.lyx
deleted file mode 100644
index 27287f7..0000000
--- a/2.2.1.lyx
+++ /dev/null
@@ -1,910 +0,0 @@
-#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
-- 
cgit v1.2.3