Mastering Algorithms with C: Useful Techniques from Sorting to Encryption

Description

There are many books on data structures and algorithms, including some with useful libraries of C functions. Mastering Algorithms with C offers you a unique combination of theoretical background and working code. With robust solutions for everyday programming tasks, this book avoids the abstract style of most classic data structures and algorithms texts, but still provides all of the information you need to understand the purpose and use of common programming techniques. Implementations, as well as interesting, real-world examples of each data structure and algorithm, are included. Using both a programming style and a writing style that are exceptionally clean, Kyle Loudon shows you how to use such essential data structures as lists, stacks, queues, sets, trees, heaps, priority queues, and graphs. He explains how to use algorithms for sorting, searching, numerical analysis, data compression, data encryption, common graph problems, and computational geometry. And he describes the relative efficiency of all implementations. The compression and encryption chapters not only give you working code for reasonably efficient solutions, they offer explanations of concepts in an approachable manner for people who never have had the time or expertise to study them in depth. Anyone with a basic understanding of the C language can use this book. In order to provide maintainable and extendible code, an extra level of abstraction (such as pointers to functions) is used in examples where appropriate. Understanding that these techniques may be unfamiliar to some programmers, Loudon explains them clearly in the introductory chapters. Table of Contents Preface Organization Part I Part II Part III Key Features About the Code Conventions How to Contact Us Acknowledgments I Introduction An Introduction to Data Structures An Introduction to Algorithms General Approaches in Algorithm Design Randomized algorithms Divide-and-conquer algorithms Dynamic-programming solutions Greedy algorithms Approximation algorithms A Bit About Software Engineering How to Use This Book Pointer Manipulation Pointer Fundamentals Storage Allocation Aggregates and Pointer Arithmetic Structures Arrays Pointers as Parameters to Functions Call-by-Reference Parameter Passing Pointers to Pointers as Parameters Generic Pointers and Casts Generic Pointers Casts Function Pointers Questions and Answers Related Topics Recursion Basic Recursion Tail Recursion Questions and Answers Related Topics Analysis of Algorithms Worst-Case Analysis Reasons for Worst-Case Analysis O-Notation Simple Rules for O-Notation O-Notation Example and Why It Works Computational Complexity Analysis Example: Insertion Sort Questions and Answers Related Topics II Linked Lists Description of Linked Lists Interface for Linked Lists list_init list_destroy list_ins_next list_rem_next list_size list_head list_tail list_is_head list_is_tail list_data list_next ImplementationandAnalysis ofLinkedLists list_init list_destroy list_ins_next list_rem_next list_size, list_head, list_tail, list_is_tail, list_data, and list_next LinkedListExample:Frame Management Description of Doubly-Linked Lists Interface for Doubly-Linked Lists dlist_init dlist_destroy dlist_ins_next dlist_ins_prev dlist_remove dlist_size dlist_head dlist_tail dlist_is_head dlist_is_tail dlist_data dlist_next dlist_prev Implementation and Analysis ofDoublyLinked Lists dlist_init dlist_destroy dlist_ins_next dlist_ins_prev dlist_remove dlist_size, dlist_head, dlist_tail, dlist_is_head, dlist_is_tail, dlist_data, dlist_next, and dli... Description of Circular Lists Interface for Circular Lists clist_init clist_destroy clist_ins_next clist_rem_next clist_size clist_head clist_data clist_next Implementation and Analysis ofCircular Lists clist_init clist_destroy clist_ins_next clist_rem_next clist_size, clist_head, clist_data, and clist_next Circular List Example: Second-Chance Page Replacement Questions and Answers Related Topics Stacks and Queues Description of Stacks Interface for Stacks stack_init stack_destroy stack_push stack_pop stack_peek stack_size Implementation and Analysis of Stacks stack_init stack_destroy stack_push stack_pop stack_peek, stack_size Description of Queues Interface for Queues queue_init queue_destroy queue_enqueue queue_dequeue queue_peek queue_size Implementation and Analysis of Queues queue_init queue_destroy queue_enqueue queue_dequeue queue_peek, queue_size Queue Example: Event Handling Questions and Answers Related Topics Sets Description of Sets Definitions Basic Operations Properties Interface for Sets set_init set_destroy set_insert set_remove set_union set_intersection set_difference set_is_member set_is_subset set_is_equal set_size Implementation and Analysis of Sets set_init set_destroy set_insert set_remove set_union set_intersection set_difference set_is_member set_is_subset set_is_equal set_size Set Example: Set Covering Questions and Answers Related Topics Hash Tables Description of Chained Hash Tables Collision Resolution Selecting a Hash Function Division method Multiplication method Interface for Chained Hash Tables chtbl_init chtbl_destroy chtbl_insert chtbl_remove chtbl_lookup chtbl_size ImplementationandAnalysis ofChainedHashTables chtbl_init chtbl_destroy chtbl_insert chtbl_remove chtbl_lookup chtbl_size ChainedHashTableExample: SymbolTables DescriptionofOpen-Addressed HashTables Collision Resolution Linear probing Double hashing InterfaceforOpen-Addressed HashTables ohtbl_init ohtbl_destroy ohtbl_insert ohtbl_remove ohtbl_lookup ohtbl_size ImplementationandAnalysis of Open AddressedHashTables ohtbl_init ohtbl_destroy ohtbl_insert ohtbl_remove ohtbl_lookup ohtbl_size Questions and Answers Related Topics Trees Description of Binary Trees Traversal Methods Preorder traversal Inorder traversal Postorder traversal Level-order traversal Tree Balancing Interface for Binary Trees bitree_init bitree_destroy bitree_ins_left bitree_ins_right bitree_rem_left bitree_rem_right bitree_merge bitree_size bitree_root bitree_is_eob bitree_is_leaf bitree_data bitree_left bitree_right ImplementationandAnalysis ofBinaryTrees bitree_init bitree_destroy bitree_ins_left bitree_ins_right bitree_rem_left bitree_rem_right bitree_merge bitree_size, bitree_root, bitree_is_eob, bitree_is_leaf, bitree_data, bitree_left, bitree_right BinaryTreeExample: ExpressionProcessing Description of Binary Search Trees Interface for Binary Search Trees bistree_init bistree_destroy bistree_insert bistree_remove bistree_lookup bistree_size ImplementationandAnalysis ofBinarySearchTrees Rotations in AVL Trees LL rotation LR rotation RR rotation RL rotation bistree_init bistree_destroy bistree_insert bistree_remove bistree_lookup bistree_size Questions and Answers Related Topics Heapsand PriorityQueues Description of Heaps Interface for Heaps heap_init heap_destroy heap_insert heap_extract heap_size Implementation and Analysis of Heaps heap_init heap_destroy heap_insert heap_extract heap_size Description of Priority Queues Interface for Priority Queues pqueue_init pqueue_destroy pqueue_insert pqueue_extract pqueue_peek pqueue_size ImplementationandAnalysis ofPriorityQueues Priority Queue Example: Parcel Sorting Questions and Answers Related Topics Graphs Description of Graphs Search Methods Breadth-first search Depth-first search Interface for Graphs graph_init graph_destroy graph_ins_vertex graph_ins_edge graph_rem_vertex graph_rem_edge graph_adjlist graph_is_adjacent graph_adjlists graph_vcount graph_ecount Implementation and Analysis of Graphs graph_init graph_destroy graph_ins_vertex graph_ins_edge graph_rem_vertex graph_rem_edge graph_adjlist graph_is_adjacent graph_adjlists, graph_vcount, graph_ecount Graph Example: Counting Network Hops Graph Example: Topological Sorting Questions and Answers Related Topics III Sorting and Searching Description of Insertion Sort Interface for Insertion Sort issort Implementation and Analysis of Insertion Sort Description of Quicksort Interface for Quicksort qksort ImplementationandAnalysis ofQuicksort Quicksort Example: Directory Listings Description of Merge Sort Interface for Merge Sort mgsort ImplementationandAnalysis ofMergeSort Description of Counting Sort Interface for Counting Sort ctsort ImplementationandAnalysis ofCountingSort Description of Radix Sort Interface for Radix Sort rxsort ImplementationandAnalysis ofRadixSort Description of Binary Search Interface for Binary Search bisearch ImplementationandAnalysis ofBinarySearch Binary Search Example: Spell Checking Questions and Answers Related Topics Numerical Methods Description of Polynomial Interpolation Constructing an Interpolating Polynomial Evaluating an Interpolating Polynomial Interface for Polynomial Interpolation interpol ImplementationandAnalysis ofPolynomialInterpolation Description of Least-Squares Estimation Interface for Least-Squares Estimation lsqe Implementation and Analysis of Least-Squares Estimation Description of the Solution of Equations Finding Roots with Newton’s Method Computing the Derivative of a Polynomial Understanding the First and Second Derivative Selecting an Initial Point for Newton’s Method How Newton’s Method Works Interface for the Solution of Equations root ImplementationandAnalysis oftheSolutionofEquations Questions and Answers Related Topics Data Compression Description of Bit Operations Interface for Bit Operations bit_get bit_set bit_xor bit_rot_left ImplementationandAnalysis ofBitOperations bit_get bit_set bit_xor bit_rot_left Description of Huffman Coding Entropy and Minimum Redundancy Building a Huffman Tree Compressing and Uncompressing Data Effectiveness of Huffman Coding Interface for Huffman Coding huffman_compress huffman_uncompress ImplementationandAnalysis ofHuffmanCoding huffman_compress huffman_uncompress HuffmanCodingExample: OptimizedNetworking Description of LZ77 Maintaining a Dictionary of Phrases Compressing and Uncompressing Data Effectiveness of LZ77 Interface for LZ77 lz77_compress lz77_uncompress Implementation and Analysis of LZ77 lz77_compress lz77_uncompress Questions and Answers Related Topics Data Encryption Description of DES Computing Subkeys Enciphering and Deciphering Data Blocks Interface for DES des_encipher des_decipher Implementation and Analysis of DES des_encipher des_decipher DES Example: Block Cipher Modes Description of RSA Computing Public and Private Keys Enciphering and Deciphering Data Blocks Interface for RSA rsa_encipher rsa_decipher Implementation and Analysis of RSA rsa_encipher rsa_decipher Questions and Answers Related Topics Graph Algorithms Description of Minimum Spanning Trees Prim’s Algorithm Interface for Minimum Spanning Trees mst Implementation and Analysis ofMinimum Spanning Trees Description of Shortest Paths Dijkstra’s Algorithm Interface for Shortest Paths shortest Implementation and Analysis ofShortestPaths Shortest Paths Example: Routing Tables Description of the Traveling-Salesman Problem Applying the Nearest-Neighbor Heuristic Interface for the Traveling-Salesman Problem tsp Implementation and Analysis oftheTraveling-Salesman Problem Questions and Answers Related Topics Geometric Algorithms Description of Testing Whether Line Segments Intersect Standard Test for Intersecting Line Segments Computer Test for Intersecting Line Segments Interface for Testing Whether Line Segments Intersect lint Implementation and Analysis of Testing Whether Line Segments Intersect Description of Convex Hulls Jarvis’s March Interface for Convex Hulls cvxhull ImplementationandAnalysis ofConvexHulls Description of Arc Length onSphericalSurfaces Rectilinear and Spherical Coordinates Converting Between Coordinate Systems Computing the Length of an Arc InterfaceforArcLength onSphericalSurfaces arclen Implementation and Analysis of Arc Length on Spherical Surfaces Arc Length Example: Approximating Distances on Earth Questions and Answers Related Topics Index