path: root/2.3.4.5.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 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