Mastering Algorithms with C

'This is an O'Reilly book, surely one of the best publishers of technical books areound. I love 'em, from the animal cover to the Colophon, and it is rare indeed that I come across an O'Reilly book that I regret buying....So, all in all, an enjoyable book and one I will move onto my Important Algorithm Book shelf, rather than on the floor in a pile with the also-rans. Recommended.' - Julian M Bucknall Developers Review, August 2000

Kyle Loudon is a software engineer at Jeppesen Dataplan in Los Gatos, California, where he leads the graphical interface development group in developing flight planning software used by commercial airlines, corporate flight departments, and other facets of general aviation. Before Jeppesen, Kyle worked as a system programmer for IBM. Kyle's technical interests at this time include operating systems, networking, and human-computer interaction. Kyle attended Purdue University, where in 1992 he received a B.S. in computer science and a minor in French, and was elected to Phi Beta Kappa. While at Purdue, he coordinated and taught a course for three years in the Department of Computer Science. During this time he also wrote his first book, Understanding Computers, a practical and conceptual introduction to computers. Currently he is patiently pursuing an advanced degree while continuing to work in Silicon Valley's software industry. Aside from computers, Kyle has enjoyed playing and teaching tennis for a number of years. He also enjoys mountain biking, skiing, and on occasion, golf with friends on courses that favor a sometimes overactive slice. In addition, Kyle enjoys various forms of theater, great food, and several styles of music and art as a wishful but hopeless pianist and artist himself. Kyle found his present position at Jeppesen after he started flying airplanes in 1992. Currently he is an active pilot holding a commercial pilot certificate with the FAA.

Preface. I. Preliminaries 1. Introduction An Introduction to Data Structures An Introduction to Algorithms A Bit About Software Engineering How to Use This Book. 2. Pointer Manipulation Pointer Fundamentals Storage Allocation Aggregates and Pointer Arithmetic Pointers as Parameters to Functions Generic Pointers and Casts Function Pointers Questions and Answers Related Topics. 3. Recursion Basic Recursion Tail Recursion Questions and Answers Related Topics. 4. Analysis of Algorithms Worst-Case Analysis O-Notation Computational Complexity Analysis Example: Insertion Sort Questions and Answers Related Topics. II. Data Structures. 5. Linked Lists Description of Linked Lists Interface for Linked Lists Implementation and Analysis of Linked Lists Linked List Example: Frame Management Description of Doubly-Linked Lists Interface for Doubly-Linked Lists Implementation and Analysis of Doubly Linked Lists Description of Circular Lists Interface for Circular Lists Implementation and Analysis of Circular Lists Circular List Example: Second-Chance Page Replacement Questions and Answers Related Topics. 6. Stacks and Queues Description of Stacks Interface for Stacks Implementation and Analysis of Stacks Description of Queues Interface for Queues Implementation and Analysis of Queues Queue Example: Event Handling Questions and Answers Related Topics. 7. Sets Description of Sets Interface for Sets Implementation and Analysis of Sets Set Example: Set Covering Questions and Answers Related Topics. 8. Hash Tables Description of Chained Hash Tables Interface for Chained Hash Tables Implementation and Analysis of Chained Hash Tables Chained Hash Table Example: Symbol Tables Description of Open-Addressed Hash Tables Interface for Open-Addressed Hash Tables Implementation and Analysis of Open Addressed Hash Tables Questions and Answers Related Topics. 9. Trees Description of Binary Trees Interface for Binary Trees Implementation and Analysis of Binary Trees Binary Tree Example: Expression Processing Description of Binary Search Trees Interface for Binary Search Trees Implementation and Analysis of Binary Search Trees Questions and Answers Related Topics. 10. Heaps and Priority Queues Description of Heaps Interface for Heaps Implementation and Analysis of Heaps Description of Priority Queues Interface for Priority Queues Implementation and Analysis of Priority Queues Priority Queue Example: Parcel Sorting Questions and Answers Related Topics. 11. Graphs Description of Graphs Interface for Graphs Implementation and Analysis of Graphs Graph Example: Counting Network Hops Graph Example: Topological Sorting Questions and Answers Related Topics. III. Algorithms. 12. Sorting and Searching Description of Insertion Sort Interface for Insertion Sort Implementation and Analysis of Insertion Sort Description of Quicksort Interface for Quicksort Implementation and Analysis of Quicksort Quicksort Example: Directory Listings Description of Merge Sort Interface for Merge Sort Implementation and Analysis of Merge Sort Description of Counting Sort Interface for Counting Sort Implementation and Analysis of Counting Sort Description of Radix Sort Interface for Radix Sort Implementation and Analysis of Radix Sort Description of Binary Search Interface for Binary Search Implementation and Analysis of Binary Search Binary Search Example: Spell Checking Questions and Answers Related Topics. 13. Numerical Methods Description of Polynomial Interpolation Interface for Polynomial Interpolation Implementation and Analysis of Polynomial Interpolation Description of Least-Squares Estimation Interface for Least-Squares Estimation Implementation and Analysis of Least-Squares Estimation Description of the Solution of Equations Interface for the Solution of Equations Implementation and Analysis of the Solution of Equations Questions and Answers Related To