Elementary Functional Algorithms

Edition: $\displaystyle e = \sum \limits _{n=0}^{\infty }{\frac {1}{n!}} = 1 + {\frac {1}{1}}+{\frac {1}{1\cdot 2}}+{\frac {1}{1\cdot 2\cdot 3}}+\cdots = 2.718283$

2024/02

This book presents elementary functional algorithms and data structures with 120 exercises and answers. I wrote the first edition from 2009 to 2017, then rewrote from 2020 to 2023. The second edition in PDF can be downloaded (EN, 中文). The first edition in Chinese (中文) was published in 2017.

Contents

• Preface
• Chapter 1, List;
• Chapter 2, Binary Search Tree;
• Chapter 3, Insertion sort;
• Chapter 4, Red-black tree;
• Chapter 5, AVL tree;
• Chapter 6, Radix tree, Trie and Prefix Tree;
• Chapter 7, B-Trees;
• Chapter 8, Binary Heaps;
• Chapter 9, Selection sort;
• Chapter 10, Binomial heap, Fibonacci heap, and pairing heap;
• Chapter 11, Queue;
• Chapter 12, Sequence;
• Chapter 13, Divide and conquer sort;
• Chapter 14, Search I;
• Chapter 15, Search II;
• Appendices and answers

Install

You may use gitpod to build the PDF book from cloud desktop. (It takes about 15 ~ 20 min to build the workspace at the first time, while later access is quick.) For local build, you need TeXLive. We use LuaLaTeX, an extended version of TeX.

Install TeXLive

In Linux/Unix like environment, do NOT install the TeXLive through package manager (e.g. apt-get or apk). Go to TeXLive official site to download the setup script. In Windows, TeXLive provides a gui based installer, in Mac OS X, there's a MacTeX.

Others

You need the GNU make tool, in Debian/Ubuntu like Linux, it can be installed through:

$ sudo apt-get install build-essential

In Windows, you can use WSL or MSYS. In Mac OS X, please install the developer tool from this command line:

$ xcode-select --install

Font setting

The default build supports Linux, Mac OS X, and Windows. You can install additional font (like Noto CJK) typesetting (see prelude.sty). Some system fonts, e.g. STKaiti, were moved to /System/Library/AssetsV2/com_apple_MobileAsset_Font7 in Mac OS X from 2022, you need add the path to the local TeXLive configuration:

sudo tlmgr conf texmf OSFONTDIR /System/Library/AssetsV2/com_apple_MobileAsset_Font7

Build the book PDF

enter the folder contains the book TeX manuscript, run

$ make

This will generate algoxy-en.pdf and algoxy-zh-cn.pdf. If you only need the Chinese version for example, you can run make cn instead. Run make force-cn or make force-en to force build the book.

--

LIU Xinyu