Mastering Algorithms with C

Organization

This book is divided into three parts. The first part consists of introductory material that is useful when working in the rest of the book. The second part presents a number of data structures considered fundamental in the field of computer science. The third part presents an assortment of algorithms for solving common problems. Each of these parts is described in more detail in the following sections, including a summary of the chapters each part contains.

Part I

Part I contains Chapter 1 through Chapter 4. Chapter 1, introduces the concepts of data structures and algorithms and presents reasons for using them. It also presents a few topics in software engineering, which are applied throughout the rest of the book. Chapter 2 discusses a number of topics on pointers. Pointers appear a great deal in this book, so this chapter serves as a refresher on the subject. Chapter 3 covers recursion, a popular technique used with many data structures and algorithms. Chapter 4 presents the analysis of algorithms. The techniques in this chapter are used to analyze algorithms throughout the book.

Part II

Part II contains Chapter 5 through Chapter 11. Chapter 5 presents various forms of linked lists, including singly-linked lists, doubly-linked lists, and circular lists. Chapter 6 presents stacks and queues, data structures for sorting and returning data on a last-in, first-out and first-in, first-out order respectively. Chapter 7 presents sets and the fundamental mathematics describing sets. Chapter 8 presents chained and open-addressed hash tables, including material on how to select a good hash function and how to resolve collisions. Chapter 9 presents binary and AVL trees. Chapter 9 also discusses various methods of tree traversal. Chapter 10 presents heaps and priority queues, data structures that help to quickly determine the largest or smallest element in a set of data. Chapter 11 presents graphs and two fundamental algorithms from which many graph algorithms are derived: breadth-first and depth-first search.

Part III

Part III, contains Chapter 12 through Chapter 17. Chapter 12 covers various algorithms for sorting, including insertion sort, quicksort, merge sort, counting sort, and radix sort. Chapter 12 also presents binary search. Chapter 13 covers numerical methods, including algorithms for polynomial interpolation, least-squares estimation, and the solution of equations using Newton’s method. Chapter 14 presents algorithms for data compression, including Huffman coding and LZ77. Chapter 15 discusses algorithms for DES and RSA encryption. Chapter 16 covers graph algorithms, including Prim’s algorithm for minimum spanning trees, Dijkstra’s algorithm for shortest paths, and an algorithm for solving the traveling-salesman problem. Chapter 17 presents geometric algorithms, including methods for testing whether line segments intersect, computing convex hulls, and computing arc lengths on spherical surfaces.