#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
rexerc1[M21]
\end_layout

\end_inset

In Section 2.3.4 we saw that trees are special cases of the 
\begin_inset Quotes eld
\end_inset

classical
\begin_inset Quotes erd
\end_inset

 mathematical concept of a directed graph.
 Can Lists be described in graph-theoretic terminology?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Yes,
 we can consider Lists as ordered trees where,
 in general,
 only the leaves have labels.
 If we allow Lists to be referenced from multiple places,
 then we can consider them as graphs where outgoing arcs from a given node are ordered and such that there is a distinguished vertex 
\begin_inset Formula $R$
\end_inset

 such that there is at least one path from 
\begin_inset Formula $R$
\end_inset

 to any other vertex.
 These Lists can be used to reason about computer memory in higher level programming languages.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc6[00]
\end_layout

\end_inset

The quantitative discussion at the end of this section says that the cost of garbage collection is approximately 
\begin_inset Formula $c_{1}\mathtt{N}+c_{2}\mathtt{M}$
\end_inset

 units of time;
 where does the 
\begin_inset Quotes eld
\end_inset


\begin_inset Formula $c_{2}\mathtt{M}$
\end_inset


\begin_inset Quotes erd
\end_inset

 term come from?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

From scanning the memory in search of nodes to collect.
\end_layout

\end_body
\end_document