1 files changed, 0 insertions, 443 deletions
diff --git a/2.3.4.5.lyx b/2.3.4.5.lyx
deleted file mode 100644
index 8bd484a..0000000
--- a/2.3.4.5.lyx
+++ /dev/null
@@ -1,443 +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 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