• 0/1 knapsack problem, 261, 263–265, 285, 299

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
  • resolution, 2, 11, 27, 31
• 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
  • sort, 132, 159, 160, 163–167, 186, 187, 194–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
  • disks, 33, 36
  • tapes, 33, 35, 39, 198–200, 226
• 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
  • equivalence, 300
  • time complexity, 262, 287, 291, 292, 297
• 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
  • external, 33, 116, 132, 197, 198
  • random access, 33, 200, 206
  • sequential, 33
• 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