A, B
- all-pairs shortest path problem, 261, 269–271, 282, 286
- backward approach, 263, 265, 285
- balanced
- k-way merging, 207, 208, 212, 226, 227
- merge sort, 202, 204, 206, 207, 212
- Bellman’s Principle of Optimality, 261, 262, 264, 267, 270, 274, 280, 285
- binary
- decision tree, 101
- search, 1, 18, 28–30, 42, 46, 61, 62, 65, 70, 74, 76–78, 82, 90, 93, 100–105, 108, 116, 119–121, 126–129, 192–195, 241, 243, 272–274, 276–279, 283, 284
- bubble sort, 132–135, 179, 180, 194, 195, 197
- bucket sort, 132, 167, 175–178, 191, 192, 195–197
- buffer handling, 204–207
C
- candidate key, 37, 46
- cascade merge sort, 198, 214, 224–226
- chaining, 2, 4, 13, 24, 32
- CNF-satisfiability, 295, 308
- collision, 2, 4, 5, 7, 11, 12, 14, 18, 25, 27, 30–32, 48
- conjunctive normal form, 294, 295
- constraints, 93, 245–248, 250, 257, 261
- Cook’s theorem, 302–304, 309
- counting sort, 132, 171–175, 190, 191, 195–197
D
- deterministic algorithms, 289, 291, 292, 297, 298, 302, 303
- dictionary, 1, 2, 32, 98, 108, 129
- Dijkstra’s algorithm, 251
- direct file organization, 22, 48, 49, 54, 55, 57–59
- Directed Hamiltonian Circuit problem (DHC), 301, 302
- discriminator, 62, 66, 69
- disjunctive normal form (DNF), 294–296, 306, 307
- Divide and Conquer, 101, 145, 146, 156, 229–231, 233–236, 238–245
- dynamic programming, 261–267, 270, 274, 277–280, 284–286, 288, 302
E, F
- exponential time complexity, 288, 291, 297
- external sorting, 132, 140, 194, 197, 198, 212, 216, 226
- feasible solution, 245, 246, 248, 250, 257, 261
- Fibonacci search, 93, 104–108, 116, 122, 127–129, 213, 223, 226
- file operations, 38, 57
- Floyd’s algorithm, 270–272, 283
- forward approach, 263, 265, 267, 280
G, H
- graph search, 116
- greedy method, 245, 246, 248–254, 257, 258, 261, 262, 285
- halting problem, 299, 309
- hash
- functions, 2–7, 9–11, 13–16, 18, 20–32, 48, 54, 55, 57–59, 129
- tables, 1–19, 21–32, 93, 129
- heap, 34, 38, 39, 57, 58, 76–79, 132, 159–167, 185–187, 193–197
I, K
- Indexed
- Sequential Access Method, 116
- Sequential search, 60, 94, 116
- indexing, 43–47, 51–53, 57, 58
- insertion sort, 132, 135–138, 147, 149, 151, 175, 176, 178, 180, 181, 194, 195, 197
- internal sorting, 131, 132, 194, 197, 198, 202, 205, 206, 212, 221, 226
- interpolation search, 93, 98–100, 116, 119, 127–129
- intractable problems, 288
- k-d trees, 61–75, 83–86, 90, 91
- construction, 65
- delete, 72
- find minimum, 70
- insert, 69
- knapsack problem, 245–249, 251–253, 257, 259, 263
- Kruskal’s algorithm, 246, 249–251, 258
L, M, N
- linear
- probing, 7, 11, 12, 29–32
- search, 39, 40, 42–44, 47, 93–96, 127
- magnetic
- matrix multiplication, 229, 234–244, 287
- max-heap, 76–79, 82
- max-min problem, 231
- merge sort, 132, 140, 143–146, 149, 183, 194–198, 202, 206–208, 214, 220, 229, 233, 243
- min-heap, 76, 77, 91, 192, 193
- multi-dimensional keys, 61, 70
- nondeterministic algorithms, 288–292, 297, 298, 300, 302
- NP class, 287–289, 291, 292, 297, 301, 302, 308
- NP-complete problems, 298, 300–302, 309
- NP-completeness, 288, 289, 292, 298
- NP-hard problems, 297–299, 301, 304, 308, 309
O, P, Q, R
- objective function, 245–248, 250, 261
- optimal
- binary search trees, 261, 263, 274, 276–279, 284–286
- solution, 245, 247, 248, 250, 252, 253, 257, 258, 261, 262, 264, 265
- P class, 287, 292, 302, 308
- polynomial
- polyphase merge sort, 212–214, 224–226
- Prim’s algorithm, 249, 250, 258
- primary keys, 36, 37, 39, 42–44, 46, 47, 50, 52–55, 57–59
- quick sort, 132, 153, 154, 156–158, 184, 185, 194–197, 240, 243
- radix sort, 132, 167–171, 187, 188, 194–197
- recurrence relations, 104, 146, 147, 183, 232, 233, 235, 237, 242, 243, 262–265, 267, 268, 270–272, 275, 277, 279, 280, 285
- rehashing, 11, 27, 31, 32
- relational databases, 2, 18, 19, 21
S
- satisfiability problem, 292, 294, 295, 297, 298, 300–304, 306, 308, 309
- secondary keys, 37, 46, 47, 57, 58
- selection tree, 208–210, 226
- sequential
- file organization, 22, 41, 57, 58
- search, 8, 9, 11, 15, 60, 93, 94, 96, 98, 110, 111, 116, 117, 127
- shell sort, 132, 147–153, 189, 190, 194, 196, 197
- skip lists, 108–114, 125, 126, 128, 129
- space partitioning, 61, 63
- storage devices, 22, 33, 34, 48, 198
- Strassen’s matrix multiplication algorithm, 236
- super key, 37, 57, 58
- symbol table, 18, 19
T
- transpose sequential search, 93, 96–98, 118, 127, 128
- traveling salesperson problem, 261, 266–269, 280, 285, 286, 288
- treaps, 61, 76–82, 87, 89–91
- delete, 79
- insert, 78, 79
- retrieval, 77
- rotations, 78
..................Content has been hidden....................
You can't read the all page of ebook, please click
here login for view all page.