Changed layout for more manageable volumes

1 files changed, 443 insertions, 0 deletions

diff --git a/vol1/2.3.4.5.lyx b/vol1/2.3.4.5.lyx
new file mode 100644
index 0000000..8bd484a
--- /dev/null
+++ b/vol1/2.3.4.5.lyx
@@ -0,0 +1,443 @@
+#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 Note Note
+status open
+
+\begin_layout Plain Layout
+TODO 3,
+ 4,
+ 12 (2pp.,
+ 1:14)
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc3[M24]
+\end_layout
+
+\end_inset
+
+An extended binary tree with 
+\begin_inset Formula $m$
+\end_inset
+
+ external nodes determines a set of path lengths 
+\begin_inset Formula $l_{1},l_{2},\dots,l_{m}$
+\end_inset
+
+ that describe the lengths of paths from the root to the respective external nodes.
+ Conversely,
+ if we are given a set of numbers 
+\begin_inset Formula $l_{1},l_{2},\dots,l_{m}$
+\end_inset
+
+,
+ is it always possible to construct an extended binary tree in which these numbers are the path lengths in some order?
+ Show that this is possible if and only if 
+\begin_inset Formula $\sum_{j=1}^{m}2^{-l_{j}}=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+We assign each external node an interval of real numbers as follows:
+ start with 
+\begin_inset Formula $[l,u)=[0,1)$
+\end_inset
+
+;
+ then,
+ for each edge in the path from the root to the node,
+ if it's a left edge,
+ set 
+\begin_inset Formula $[l,u)\gets[l,\frac{l+u}{2})$
+\end_inset
+
+,
+ and if it's a right edge,
+ set 
+\begin_inset Formula $[l,u)\gets[\frac{l+u}{2},u)$
+\end_inset
+
+,
+ so the interval's length is 
+\begin_inset Formula $2^{-l}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $l$
+\end_inset
+
+ being the path length.
+ It's easy to see that these intervals are disjoint and that,
+ for each 
+\begin_inset Formula $x\in[0,1)$
+\end_inset
+
+,
+ there is a special node whose interval contains 
+\begin_inset Formula $x$
+\end_inset
+
+.
+ With this in mind:
+\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
+
+This is precisely the sum of the lengths of the intervals,
+ which is 1 because 
+\begin_inset Formula $[0,1)$
+\end_inset
+
+ is the disjoint union of these intervals.
+\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
+
+We just have to sort the path lengths in increasing order,
+ assign consecutive intervals of length 
+\begin_inset Formula $2^{-l_{k}}$
+\end_inset
+
+ starting from 0 and converting the intervals to paths (more precisely,
+ to sequences of left/right turns),
+ which we can do since the increasing order ensures that the starting point 
+\begin_inset Formula $l_{k}$
+\end_inset
+
+ of an interval 
+\begin_inset Formula $[l_{k},u_{k})$
+\end_inset
+
+ is a multiple of the length 
+\begin_inset Formula $u_{k}-l_{k}$
+\end_inset
+
+.
+ These paths are all different and none is a prefix of another one,
+ so they define the leaves of a binary tree.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc4[M25]
+\end_layout
+
+\end_inset
+
+(E.
+ S.
+ Schwartz and B.
+ Kallick.) Assume that 
+\begin_inset Formula $w_{1}\leq w_{2}\leq\dots\leq w_{m}$
+\end_inset
+
+.
+ Show that there is an extended binary tree that minimizes 
+\begin_inset Formula $\sum w_{j}l_{j}$
+\end_inset
+
+ and for which the terminal nodes in left to right order contain the respective values 
+\begin_inset Formula $w_{1},w_{2},\dots,w_{m}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $T$
+\end_inset
+
+ be an extended binary tree that minimizes 
+\begin_inset Formula $\sum w_{j}l_{j}$
+\end_inset
+
+.
+ For 
+\begin_inset Formula $i<j$
+\end_inset
+
+,
+ if 
+\begin_inset Formula $w_{i}<w_{j}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $l_{i}\geq l_{j}$
+\end_inset
+
+ in that tree,
+ as otherwise we could reduce the weight path length by swapping their positions as
+\begin_inset Formula 
+\[
+(w_{i}l_{j}+w_{j}l_{i})-(w_{i}l_{i}+w_{j}l_{j})=(w_{i}-w_{j})(l_{j}-l_{i})<0\#.
+\]
+
+\end_inset
+
+Thus we might assume 
+\begin_inset Formula $l_{i}\geq l_{j}$
+\end_inset
+
+ for all 
+\begin_inset Formula $i<j$
+\end_inset
+
+.
+ This means lengths 
+\begin_inset Formula $l_{1},\dots,l_{m}$
+\end_inset
+
+ are in decreasing order,
+ so the proof in the previous exercise gives us a tree whose nodes,
+ in the order of the tree,
+ are 
+\begin_inset Formula $w_{m},\dots,w_{1}$
+\end_inset
+
+ with lengths 
+\begin_inset Formula $l_{m},\dots,l_{1}$
+\end_inset
+
+,
+ and we just have to swap left and right edges in that tree.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc12[M20]
+\end_layout
+
+\end_inset
+
+Suppose that a node has been chosen at random in a binary tree,
+ with each node equally likely.
+ Show that the average size of the subtree rooted at that node is related to the path length of the tree.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $V_{1},\dots,V_{m}$
+\end_inset
+
+ be the internal nodes,
+ with path lengths 
+\begin_inset Formula $l_{1},\dots,l_{m}$
+\end_inset
+
+.
+ The average size of the subtrees is the sum of the number of nodes in each subtree divided by 
+\begin_inset Formula $m$
+\end_inset
+
+,
+ but in this sum,
+ each node 
+\begin_inset Formula $V_{k}$
+\end_inset
+
+ is counted 
+\begin_inset Formula $l_{k}+1$
+\end_inset
+
+ times,
+ one for the subtree generated by each node in the path from the root to 
+\begin_inset Formula $V_{k}$
+\end_inset
+
+ including both ends of the path.
+ Thus this average is precisely
+\begin_inset Formula 
+\[
+\frac{1}{m}\sum_{k}(l_{k}+1)=\frac{1}{m}(I+m)=\frac{I}{m}+1,
+\]
+
+\end_inset
+
+where 
+\begin_inset Formula $I$
+\end_inset
+
+ is the internal path length of the tree.
+\end_layout
+
+\end_body
+\end_document