# APPENDIX C: ALGORITHM INDEX BY CHAPTER

Exchange sorting--SORT 1.3

Binary search--BINSRCH 1.3

FIBONACCI 1.4

Filling a magic square--MAGIC 1.4

CHAPTER 2--ARRAYS

Fibonacci polynomials--MAIN 2.2

Sparse matrix transpose--TRANSPOSE 2.3

Sparse matrix transpose--FAST-TRANSPOSE 2.3

Sparse matrix multiplication--MMULT 2.3

CHAPTER 3--STACKS AND QUEUES

Path through a maze--PATH 3.2

Evaluation of a postfix expression--EVAL 3.3

Translating infix to postfix--POSTFIX 3.3

Create a list with 2 nodes--CREATE 2 4.1

Insert a node in a list--INSERT 4.1

Delete a node from a list--DELETE 4.1

Finding a new node--GETNODE 4.3

Initializing available space--INIT 4.3

Returning a node to available space--RET 4.3

Erasing a circular list--CERASE 4.4

Concatenating two lists--CONCATENATE 4.5

Circular list insertion--INSERT-FRONT 4.5

Length of a circular list--LENGTH 4.5

Finding equivalence classes--EQUIVALENCE 4.6

Erasing a linked sparse matrix--MERASE 4.7

First fit allocation--FF, ALLOCATE 4.8

Returning freed blocks--FREE

General lists--COPY, EQUAL, DEPTH 4.9

Erasing a list with reference counts--ERASE 4.9

Garbage collection--DRIVER, MARK 1, MARK 2 4.10

Compacting storage--COMPACT 4.10

Strings--SINSERT 4.11

Finding a pattern--FIND, NFIND, PMATCH, FAIL 4.11

Initializing available space in FORTRAN-INIT 4.12

Initializing available space in PASCAL-INIT 4.12

CHAPTER 5--TREES

Inorder traversal--INORDER,INORDER1,2,3 5.4

Preorder traversal--PREORDER 5.4

Postorder traversal--POSTORDER 5.4

Copy a binary tree--COPY 5.5

Equivalence of binary trees--EQUAL 5.5

Evaluating propositional expressions--POSTORDER-EVAL 5.5

The inorder successor--INSUC 5.6

Traversing a threaded binary tree--TINORDER 5.6

Insertion in a threaded tree--INSERT-RIGHT 5.6

Disjoint set union--U, F, UNION, FIND 5.8

Decision trees--EIGHTCOINS 5.8

Game playing--VE,AB(alpha-beta) 5.8

CHAPTER 6--GRAPHS

Depth first search--DFS 6.2

Connected components--COMP 6.2

Minimum spanning tree--KRUSKAL 6.2

Shortest path, single source--SHORTEST-PATH 6.3

Shortest paths, ALL__COSTS 6.3

TOPOLOGICAL-ORDER 6.4

The first m shortest paths--M-SHORTEST 6.5

CHAPTER 7--INTERNAL SORTING

Sequential search--SEQSRCH 7.1

Binary search--BINSRCH 7.1

Fibonacci search--FIBSRCH 7.1

Determining equality of two lists--VERIFY1, VERIFY2 7.1

Insertion sorting--INSERT, INSORT 7.2

Quicksort--QSORT 7.3

Two-way merge sort--MERGE, MPASS, MSORT, RMSORT 7.5

Rearranging sorted records--LIST1, LIST2, TABLE 7.8

CHAPTER 8--EXTERNAL SORTING

K-way merging 8.2

K-way sorting--BUFFERING 8.2

Run generation--RUNS 8.2

Tape k-way merge--Ml, M2, M3 8.3

CHAPTER 9--SYMBOL TABLES

Binary search trees--SEARCH 9.1

Minimum external path length--HUFFMAN 9.1

Optimal binary search tree--OBST 9.1

Binary search tree insertion--BST, AVL-INSERT 9.2

Hashing--LINSRCH, CHNSRCH 9.3

CHAPTER 10--FILES

Searching an m-way tree--MSEARCH 10.2

Inserting into a B-tree--INSERTB 10.2

Deletion from a B-tree--DELETEB 10.2

Tree searching--TRIE 10.2