#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} \makeatletter \newcommand{\biggg}{\bBigg@\thr@@} \newcommand{\Biggg}{\bBigg@{3.5}} \makeatother \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 true \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 10 \spacing single \use_hyperref true \pdf_bookmarks true \pdf_bookmarksnumbered false \pdf_bookmarksopen false \pdf_bookmarksopenlevel 1 \pdf_breaklinks false \pdf_pdfborder false \pdf_colorlinks false \pdf_backref false \pdf_pdfusetitle true \papersize custom \use_geometry true \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 \paperwidth 198mm \paperheight 297mm \leftmargin 23mm \topmargin 33mm \rightmargin 43mm \bottommargin 66mm \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 2 \paperpagestyle fancy \tablestyle default \listings_params "basicstyle={\ttfamily}" \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 Title Exercises on \emph on The Art Of Computer Programming \emph default \begin_inset Newline newline \end_inset \size larger Volume 1: Fundamental Algorithms \begin_inset Newline newline \end_inset Third Edition \end_layout \begin_layout Author Juan MarĂ­n Noguera \end_layout \begin_layout Standard \begin_inset CommandInset toc LatexCommand tableofcontents \end_inset \end_layout \begin_layout Standard \begin_inset Note Note status open \begin_layout Plain Layout Equivalent page size can be obtained with the following layouts (in mm): \end_layout \begin_layout Plain Layout \begin_inset Tabular \begin_inset Text \begin_layout Plain Layout Height \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Width \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Top \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Bottom \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Inner \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Outer \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Recommended headers \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 297 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 198 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 33 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 66 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 23 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 43 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Fancy \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 210 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 140 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 4 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 8 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 3 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout 5 \end_layout \end_inset \begin_inset Text \begin_layout Plain Layout Empty \end_layout \end_inset \end_inset \end_layout \begin_layout Plain Layout The first one follows Tschichold's canon except for \begin_inset Formula $\unit[1]{mm}$ \end_inset given to the inner margin from the outer one to account for a minimal folding. The golden ratio resulted in way too narrow pages on A5 paper. \end_layout \begin_layout Plain Layout Proposed notation for in-progress: \end_layout \begin_layout Plain Layout \begin_inset listings inline false status open \begin_layout Plain Layout atom = ( \begin_inset Quotes eld \end_inset A \begin_inset Quotes erd \end_inset | \begin_inset Quotes erd \end_inset R \begin_inset Quotes erd \end_inset ) ?( \begin_inset Quotes eld \end_inset B \begin_inset Quotes erd \end_inset | \begin_inset Quotes erd \end_inset M \begin_inset Quotes erd \end_inset ) (( \begin_inset Quotes eld \end_inset 0 \begin_inset Quotes erd \end_inset .. \begin_inset Quotes erd \end_inset 4 \begin_inset Quotes erd \end_inset ) ( \begin_inset Quotes eld \end_inset 0 \begin_inset Quotes erd \end_inset .. \begin_inset Quotes erd \end_inset 9 \begin_inset Quotes erd \end_inset ) / \begin_inset Quotes eld \end_inset @ \begin_inset Quotes erd \end_inset ) / 1DIGIT *DIGIT / *1(1DIGIT *DIGIT) \begin_inset Quotes eld \end_inset .. \begin_inset Quotes erd \end_inset *1(1DIGIT *DIGIT) \end_layout \begin_layout Plain Layout base = atom / \begin_inset Quotes eld \end_inset ( \begin_inset Quotes eld \end_inset progress \begin_inset Quotes eld \end_inset ) \begin_inset Quotes erd \end_inset \end_layout \begin_layout Plain Layout intersection = atom / intersection \begin_inset Quotes eld \end_inset * \begin_inset Quotes erd \end_inset atom \end_layout \begin_layout Plain Layout progress = intersection / progress ( \begin_inset Quotes eld \end_inset + \begin_inset Quotes erd \end_inset / \begin_inset Quotes erd \end_inset - \begin_inset Quotes erd \end_inset ) intersection \end_layout \end_inset \end_layout \begin_layout Plain Layout An \family typewriter atom \family default represents all/recommended exercises, optionally excluding M or HM/excluding HM, and up to the given difficulty level/all difficulty levels, or else a single exercise with the given number, or a range of exercises (both ends inclusive). Then \family typewriter * \family default is used for intersection, \family typewriter + \family default for union, and \family typewriter - \family default for set difference. \end_layout \end_inset \end_layout \begin_layout Chapter* Notes on the Exercises \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "0.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R30 \end_layout \end_inset \end_layout \begin_layout Chapter Basic Concepts \end_layout \begin_layout Section Algorithms \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.1.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R30 \end_layout \end_inset \end_layout \begin_layout Section Mathematical Preliminaries \end_layout \begin_layout Subsection Mathematical Induction \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.1.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R30 \end_layout \end_inset \end_layout \begin_layout Subsection Numbers, Powers, and Logarithms \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.2.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Sums and products \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.3.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25+29 \end_layout \end_inset \end_layout \begin_layout Subsection Integer Functions and Elementary Number Theory \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.4.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Permutations and Factorials \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.5.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25+11 \end_layout \end_inset \end_layout \begin_layout Subsection Binomial Coefficients \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.6.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25+44 \end_layout \end_inset \end_layout \begin_layout Subsection Harmonic Numbers \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.7.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Fibonacci Numbers \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.8.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Generating Functions \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.9.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Analysis of an Algorithm \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.10.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Asymptotic Representations \end_layout \begin_layout Subsubsection The \begin_inset Formula $O$ \end_inset -notation \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.11.1.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection Euler's summation formula \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.11.2.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection Some asymptotic calculations \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.2.11.3.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Section \family typewriter MIX \end_layout \begin_layout Subsection Description of \family typewriter MIX \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.3.1.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25+22 \end_layout \end_inset \end_layout \begin_layout Subsection The \family typewriter MIX \family default Assembly Language \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.3.2.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Applications to permutations \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.3.3.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Section Some Fundamental Programming Techniques \end_layout \begin_layout Subsection Subroutines \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.4.1.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Coroutines \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.4.2.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Interpretive Routines \end_layout \begin_layout Subsubsection A \family typewriter MIX \family default simulator \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.4.3.1.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection Trace Routines \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.4.3.2.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Input and Output \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "1.4.4.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25+4 \end_layout \end_inset \end_layout \begin_layout Section \family typewriter MMIX \end_layout \begin_layout Subsection Description of \family typewriter MMIX \end_layout \begin_layout Subsection The \family typewriter MMIX \family default Assembly Language \end_layout \begin_layout Section Some Fundamental Programming Techniques ( \family typewriter MMIX \family default ) \end_layout \begin_layout Subsection Subroutines \end_layout \begin_layout Subsection Coroutines \end_layout \begin_layout Subsection Interpretive Routines \end_layout \begin_layout Chapter Information Structures \end_layout \begin_layout Section Introduction \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.1.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Section Linear lists \end_layout \begin_layout Subsection Stacks, Queues, and Deques \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.2.1.lyx" literal "true" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R30 \end_layout \end_inset \end_layout \begin_layout Subsection Sequential Allocation \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.2.2.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Linked Allocation \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.2.3.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Circular Lists \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.2.4.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection \begin_inset CommandInset label LatexCommand label name "subsec:Doubly-Linked-Lists" \end_inset Doubly Linked Lists \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.2.5.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Arrays and Orthogonal Lists \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.2.6.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Section Trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Traversing Binary Trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.1.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Binary Tree Representation of Trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.2.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Other Representations of Trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.3.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Basic Mathematical Properties of Trees \end_layout \begin_layout Subsubsection Free trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.4.1.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection Oriented trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.4.2.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection The \begin_inset Quotes eld \end_inset infinity lemma \begin_inset Quotes erd \end_inset \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.4.3.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection Enumeration of trees \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.4.4.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection Path length \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.4.5.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsubsection History and bibliography \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.4.6.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Subsection Lists and Garbage Collection \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.3.5.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Section Multilinked Structures \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.4.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \begin_layout Section Dynamic Storage Allocation \end_layout \begin_layout Standard \begin_inset CommandInset include LatexCommand input filename "2.5.lyx" literal "false" \end_inset \begin_inset Note Note status open \begin_layout Plain Layout \family typewriter A10+R25 \end_layout \end_inset \end_layout \end_body \end_document