Mastering Algorithms with C Useful Techniques from Sorting to Encryption

Table of Contents......Page 7
Organization......Page 13
Part III......Page 14
Key Features......Page 15
About the Code......Page 16
How to Contact Us......Page 17
Acknowledgments......Page 18
I......Page 21
Introduction......Page 23
An Introduction to Data Structures......Page 24
An Introduction to Algorithms......Page 25
Divide-and-conquer algorithms......Page 26
Greedy algorithms......Page 27
A Bit About Software Engineering......Page 28
How to Use This Book......Page 30
Pointer Manipulation......Page 31
Storage Allocation......Page 32
Structures......Page 35
Arrays......Page 36
Pointers as Parameters to Functions......Page 37
Call-by-Reference Parameter Passing......Page 38
Pointers to Pointers as Parameters......Page 40
Generic Pointers......Page 41
Function Pointers......Page 43
Questions and Answers......Page 44
Related Topics......Page 45
Recursion......Page 47
Basic Recursion......Page 48
Tail Recursion......Page 52
Questions and Answers......Page 54
Related Topics......Page 57
Analysis of Algorithms......Page 58
Reasons for Worst-Case Analysis......Page 59
Simple Rules for O-Notation......Page 60
O-Notation Example and Why It Works......Page 61
Computational Complexity......Page 62
Analysis Example: Insertion Sort......Page 65
Questions and Answers......Page 67
Related Topics......Page 68
II......Page 69
Linked Lists......Page 71
Description of Linked Lists......Page 72
list_init......Page 73
list_rem_next......Page 74
list_is_tail......Page 75
ImplementationandAnalysis ofLinkedLists......Page 76
list_ins_next......Page 78
list_rem_next......Page 79
list_size, list_head, list_tail, list_is_tail, list_data, and list_next......Page 80
LinkedListExample:Frame Management......Page 85
dlist_init......Page 88
dlist_ins_prev......Page 89
dlist_tail......Page 90
dlist_prev......Page 91
Implementation and Analysis ofDoublyLinked Lists......Page 92
dlist_destroy......Page 93
dlist_ins_next......Page 94
dlist_size, dlist_head, dlist_tail, dlist_is_head, dlist_is_tail, dlist_data, dlist_next, and dli.........Page 95
clist_init......Page 102
clist_rem_next......Page 103
Implementation and Analysis ofCircular Lists......Page 104
clist_ins_next......Page 106
clist_size, clist_head, clist_data, and clist_next......Page 107
Circular List Example: Second-Chance Page Replacement......Page 111
Questions and Answers......Page 114
Related Topics......Page 116
Stacks and Queues......Page 118
Description of Stacks......Page 119
stack_destroy......Page 120
stack_size......Page 121
Implementation and Analysis of Stacks......Page 122
stack_pop......Page 123
stack_peek, stack_size......Page 124
queue_init......Page 125
queue_dequeue......Page 126
Implementation and Analysis of Queues......Page 127
queue_dequeue......Page 128
queue_peek, queue_size......Page 129
Queue Example: Event Handling......Page 130
Questions and Answers......Page 133
Related Topics......Page 134
Sets......Page 135
Description of Sets......Page 136
Basic Operations......Page 137
Properties......Page 138
set_destroy......Page 139
set_union......Page 140
set_is_subset......Page 141
Implementation and Analysis of Sets......Page 142
set_init......Page 143
set_union......Page 144
set_is_subset......Page 145
set_size......Page 146
Set Example: Set Covering......Page 153
Questions and Answers......Page 158
Related Topics......Page 160
Hash Tables......Page 161
Collision Resolution......Page 163
Selecting a Hash Function......Page 164
Multiplication method......Page 165
chtbl_destroy......Page 167
chtbl_size......Page 168
ImplementationandAnalysis ofChainedHashTables......Page 169
chtbl_destroy......Page 170
chtbl_size......Page 171
ChainedHashTableExample: SymbolTables......Page 177
Collision Resolution......Page 181
Linear probing......Page 182
Double hashing......Page 183
ohtbl_init......Page 184
ohtbl_remove......Page 185
ImplementationandAnalysis of Open AddressedHashTables......Page 186
ohtbl_insert......Page 188
ohtbl_size......Page 189
Questions and Answers......Page 196
Related Topics......Page 197
Trees......Page 198
Traversal Methods......Page 200
Preorder traversal......Page 201
Tree Balancing......Page 202
bitree_init......Page 203
bitree_ins_right......Page 204
bitree_size......Page 205
bitree_left......Page 206
ImplementationandAnalysis ofBinaryTrees......Page 207
bitree_rem_left......Page 209
bitree_size, bitree_root, bitree_is_eob, bitree_is_leaf, bitree_data, bitree_left, bitree_right......Page 210
BinaryTreeExample: ExpressionProcessing......Page 219
Description of Binary Search Trees......Page 223
bistree_init......Page 224
bistree_remove......Page 225
ImplementationandAnalysis ofBinarySearchTrees......Page 226
LL rotation......Page 227
RR rotation......Page 228
RL rotation......Page 229
bistree_destroy......Page 232
bistree_insert......Page 233
bistree_remove......Page 234
bistree_size......Page 235
Questions and Answers......Page 250
Related Topics......Page 253
Heapsand PriorityQueues......Page 255
Description of Heaps......Page 256
heap_init......Page 257
heap_extract......Page 258
Implementation and Analysis of Heaps......Page 259
heap_insert......Page 260
heap_size......Page 262
Description of Priority Queues......Page 270
pqueue_insert......Page 271
ImplementationandAnalysis ofPriorityQueues......Page 272
Priority Queue Example: Parcel Sorting......Page 274
Questions and Answers......Page 276
Related Topics......Page 278
Graphs......Page 279
Description of Graphs......Page 281
Breadth-first search......Page 284
Depth-first search......Page 286
graph_init......Page 287
graph_ins_edge......Page 288
graph_adjlist......Page 289
Implementation and Analysis of Graphs......Page 290
graph_init......Page 292
graph_ins_edge......Page 293
graph_is_adjacent......Page 294
graph_adjlists, graph_vcount, graph_ecount......Page 295
Graph Example: Counting Network Hops......Page 304
Graph Example: Topological Sorting......Page 310
Questions and Answers......Page 315
Related Topics......Page 317
III......Page 319
Sorting and Searching......Page 321
issort......Page 323
Implementation and Analysis of Insertion Sort......Page 324
Description of Quicksort......Page 327
ImplementationandAnalysis ofQuicksort......Page 328
Quicksort Example: Directory Listings......Page 334
Description of Merge Sort......Page 337
ImplementationandAnalysis ofMergeSort......Page 338
Description of Counting Sort......Page 344
ImplementationandAnalysis ofCountingSort......Page 345
rxsort......Page 349
ImplementationandAnalysis ofRadixSort......Page 350
Description of Binary Search......Page 353
ImplementationandAnalysis ofBinarySearch......Page 354
Binary Search Example: Spell Checking......Page 357
Questions and Answers......Page 359
Related Topics......Page 361
Numerical Methods......Page 363
Description of Polynomial Interpolation......Page 364
Constructing an Interpolating Polynomial......Page 365
Evaluating an Interpolating Polynomial......Page 366
interpol......Page 368
ImplementationandAnalysis ofPolynomialInterpolation......Page 369
Description of Least-Squares Estimation......Page 372
lsqe......Page 373
Implementation and Analysis of Least-Squares Estimation......Page 374
Finding Roots with Newton’s Method......Page 375
Understanding the First and Second Derivative......Page 376
Selecting an Initial Point for Newton’s Method......Page 377
How Newton’s Method Works......Page 378
ImplementationandAnalysis oftheSolutionofEquations......Page 380
Questions and Answers......Page 382
Related Topics......Page 383
Data Compression......Page 385
bit_set......Page 389
bit_get......Page 390
bit_rot_left......Page 391
Entropy and Minimum Redundancy......Page 395
Building a Huffman Tree......Page 396
Compressing and Uncompressing Data......Page 397
Effectiveness of Huffman Coding......Page 398
huffman_uncompress......Page 399
huffman_compress......Page 400
huffman_uncompress......Page 401
HuffmanCodingExample: OptimizedNetworking......Page 416
Maintaining a Dictionary of Phrases......Page 419
Effectiveness of LZ77......Page 420
lz77_compress......Page 422
lz77_compress......Page 423
lz77_uncompress......Page 425
Questions and Answers......Page 438
Related Topics......Page 440
Data Encryption......Page 442
Description of DES......Page 445
Computing Subkeys......Page 446
Enciphering and Deciphering Data Blocks......Page 448
des_encipher......Page 452
des_encipher......Page 453
des_decipher......Page 455
DES Example: Block Cipher Modes......Page 465
Description of RSA......Page 468
Computing Public and Private Keys......Page 469
Enciphering and Deciphering Data Blocks......Page 471
Implementation and Analysis of RSA......Page 472
rsa_encipher......Page 473
rsa_decipher......Page 474
Questions and Answers......Page 476
Related Topics......Page 478
Graph Algorithms......Page 480
Description of Minimum Spanning Trees......Page 483
Prim’s Algorithm......Page 484
mst......Page 485
Implementation and Analysis ofMinimum Spanning Trees......Page 486
Description of Shortest Paths......Page 492
Dijkstra’s Algorithm......Page 493
shortest......Page 494
Implementation and Analysis ofShortestPaths......Page 495
Shortest Paths Example: Routing Tables......Page 501
Description of the Traveling-Salesman Problem......Page 505
Applying the Nearest-Neighbor Heuristic......Page 506
tsp......Page 507
Implementation and Analysis oftheTraveling-Salesman Problem......Page 508
Questions and Answers......Page 513
Related Topics......Page 515
Geometric Algorithms......Page 516
Description of Testing Whether Line Segments Intersect......Page 519
Standard Test for Intersecting Line Segments......Page 520
Computer Test for Intersecting Line Segments......Page 521
lint......Page 522
Implementation and Analysis of Testing Whether Line Segments Intersect......Page 523
Jarvis’s March......Page 525
ImplementationandAnalysis ofConvexHulls......Page 527
Description of Arc Length onSphericalSurfaces......Page 532
Converting Between Coordinate Systems......Page 533
Computing the Length of an Arc......Page 534
arclen......Page 535
Implementation and Analysis of Arc Length on Spherical Surfaces......Page 536
Arc Length Example: Approximating Distances on Earth......Page 537
Questions and Answers......Page 540
Related Topics......Page 543
Index......Page 545