Foundations Of Computer Science - Index

✦✦✦ ✦

Index

A

ANSI See American National Standards Institute ANSI C See C Anti-implicant 668 Antisymmetry 388–390 Arc 452, 488 Argument size See Size of arguments Arithmetic expression 46–50, 62–63, 242– 244, 592, 611–615 Arithmetic operator 18–19, 109 Arithmetic series 42 Arity 366 Array 14, 109, 232, 301–306, 308–309, 329– 333, 358–360 See also Adjacency matrix, Characteristic vector, Circular array, Heap (data structure) ASCII 38 Assignment (of values to objects) 157–160 Assignment-statement 19, 109 Associative law 47, 344–345, 441, 570, 652, 675 See also Nonassociative operator Astrahan, M. M. 450 Atom 338 Atomic formula 735 Attribute 404, 414 Automaton 530–556, 571–590, 637–639, 704 See also Deterministic automaton, ǫ-automaton, Nondeterministic automaton Average-case running time 93, 215–216, 270–271 See also Running time Awk 450, 566

Abstract data type 261, 307 See also Dictionary, Priority queue, Queue, Stack Abstract symbol 593–594 Abstraction 1, 3 Abstraction (of sets) 338–339 Acceptance, of input 533, 539 Accepting state 532, 549 Activation record 313 Acyclic graph 454 Acyclic path 456 Addition 10–12, 716–723 See also One-bit adder, Ripple-carry addition Adjacency list 459–461, 463 Adjacency matrix 460–462, 515 Adjacent nodes 456 ADT See Abstract data type Aho, A. V. 155, 335, 450, 527, 589, 641 Aleph-zero See Countable set Algebra 5, 343 See also Algebraic law, Expression, Propositional logic, Regular expression, Relational algebra, Set algebra Algebraic law See Associative law, Commutative law, Distributive law, Idempotence, Identity Algol 641 Algorithm 4–5, 20 Alphabetic order See Lexicographic order Ambiguous grammar 610–616 American National Standards Institute 24 Anagram 178 See also Partial anagram Ancestor 226, 254 See also Lowest common ancestor AND 10, 644, 649, 651–652, 657, 675–679, 688, 700, 740, 756–757 Annihilator 570, 675–676

B Backus, J. W. 641 Backus-Naur form Backward arc 488, 494 Backward induction 72

776

777

INDEX

Bag See Multiset Balanced parentheses 64–68, 594–596, 610– 611 Bar-Hillel, Y. 641 Basis 28, 35, 44–46, 59, 132 Bayes’ rule 202 Bell curve 175–176 Bellman, R. E. 335 Benchmarking 91 Berge, C. 527 Berlekamp, E. R. 88 Big-oh 96–109, 303, 355 Bin 181 Binary operator 50 Binary relation 366, 380–396 Binary search 304–305 Binary search tree 258–271 Binary search tree property 259 Binary tree 253–258 See also Binary search tree, Partially ordered tree Binomial coefficient 176 Bipartite graph 524 Bit 10, 159 Blackjack 187 Block 110–111, 114–115, 117, 122–123, 597 Block, of a program BNF See Backus-Naur form Body, of a production 593 Body, of a rule 763 See also Hypothesis Boole, G. 698 BOOLEAN 22 Boolean algebra 5, 642 Boolean function 647–648, 655–660 Borodin, A. B. 155 Bounce filter 533–535 Bound variable 741–744 Branching factor 232 Break See Jump-statement Bridge 187 Brooks, F. P. 24 BST See Binary search tree Bubbledown 276, 508–509 Bubbleup 274–276, 508–509 Bucket 362

C C 3, 7, 13–20, 22–23, 25, 64, 265, 312, 368, 562, 741–742, 758 Call by reference 265 Calling graph 129–130, 455 Cantor, G. 402 Car 290 Carry 10 Carry-in/out 656 Carry-propagate/generate 717–720 Cartesian product 367–368 Case analysis 683 Cdr 290 Cell 7, 23, 293 Chamberlin, D. D. 450 Character 13 Character class 565 Character string 287, 327–333 Characteristic vector 357–360, 376, 379, 383–384 Child 224, 254 See also Left child, Right child Chip 523, 711, 731 Chomsky, N. 641 Chromatic number 524 Chuck-a-Luck 182 Circuit 523 See also Logic circuit Circuit delay 711, 721, 727–728 Circular array 320–321 Clarity 90 Class See Abstract data type Clause 692, 738 Clear (operation on stacks, queues) 307– 308, 318 Clique 525 Closed expression 755 Closure 393–395, 560–561 See also Connected component, Topological sorting, Transitive closure Codd, E. F. 450 Coersion 20 Coloring 524–525 Combinational circuit 702 Combinations 171–178, 258 Combinatorics 156–187 Common subsequence 321 See also LCS Commutative law 47, 344, 441–442, 570, 674–675 Comparable elements 390 Comparison operator 19, 109

778

Compiler 96 See also Lexical analysis, Parsing Complement event 192 Complete binary tree See Full binary tree Complete graph 522 Complete induction 44–51 Complete proof procedure 695 Complete set of operators 659 Complete tree See Full tree Complex number 340 Component, of a tuple 366 Compound event 208–209 Compound statement 114 See also Statement Concatenation 7, 291, 558–559, 569–570 Conclusion 686 See also Head, of a rule Concordance 328 Conditional See If-statement Conditional probability 193–202 Conjunction 658 Conjunction of events 207–208 See also Compound event Conjunctive normal form See Product of sums Connected component 224, 394–395, 466– 478, 499–500 Connected graph 466 Consistent proof system 770 Constant See Defined constant Constant factor 98 Constant time 103 Containment See Subset Containment, of sets 347–349 Context-free grammar See Grammar Continue See Jump-statement Contradiction 684–685, 695–696 Contrapositive 683–684 Conway, L. 732 Cook, S. A. 698 Countable set 399 Course-conflict graph Cover 662 Cross arc 488, 490, 494 Cryptography 219 Current domain/range 369 Cycle 453, 456–458, 495–498

INDEX

Cyclic graph 454

D Data model 3–4, 6–20 Data object 6 Data structure 4–5, 8, 20 Database 403, 406 Database scheme 406–407, 410 Dead state 555 Declared domain/range 369 Decrement 19 Deduction 686–692 DefCell 23 Defensive programming 71, 117, 246 Defined constant 22 Degree, of a node 252, 462 Degree, of a relation See Arity Delete 378, 380, 384, 407, 417–418 Deletemax 271, 276–279 Deletemin 264–266 Deletion 264–266, 291, 295–297 DeMorgan’s laws 677–678 Dense graph 461 Depth, of a node 226, 254 Depth-first search 484–501 Depth-first search forest 489–490 Depth-first search tree 486–489 Dequeue 318 Dereferencing 7 Descendant 226, 254 Deterministic algorithm 216 Deterministic automaton 537, 547–556 Dewdeney, A. K. 222 Diagonalization 399–400 Dictionary 259, 274, 293, 351, 363–365, 386 See also Deletion, Insertion, Lookup Dictionary order See Lexicographic order Diff 321 Difference 342, 345, 352, 356, 429–430, 436, 441 See also Symmetric difference Digital circuit See Logic circuit Dijkstra, E. W. 527 Dijkstra’s algorithm 502–513 Direct recursion 69, 455 Directed graph 452–456, 702–703 Directory 8 Disjoint sets 539 Disjunction 658 See also Clause

779

INDEX

Disjunction of events 205–207 See also Compound event Disjunctive normal form See Sum of products Distance 502 Distribution 181–184 Distributive law 197–200, 344–345, 675– 676 Divide and conquer 75, 714, 716–722, 724– 730 Domain 368, 414, 745 See also Current domain/range, Declared domain/range Doubly linked list 299–300 Do-while statement See While-statement Duality 678–679 Duplicates, on list 296–298 Dynamic aspects of data model 6 Dynamic programming 323–324

E Edge 224, 456 Editor See Text editor Efficiency 90–91, 95 See also Running time Egrep 546, 564, 567 Empty list 288, 291 Empty set 338, 345–346, 557, 559, 570 ∅-free regular expression 571 Empty stack 307–308 Empty string 29, 557, 559, 570, 594 Empty tree 254–255 Enderton, H. B. 698, 775 Endmarker 331, 618 Enqueue 318 Entailment 769 Enumeration 13 EOF 13, 23 ǫ See Empty string ǫ-automaton 572–581 Equality, of sets 339 Equipotence 396 Equivalence class 392, 467 Equivalence, of automata 547 Equivalence, of cycles 454, 457 Equivalence, of expressions 344, 346–347, 752 Equivalence, of regular expressions 568– 569 Equivalence, of states 555

Equivalence (operator) 651, 674 Equivalence relation 391–393 Error-detecting code 38–40 Euler circuit 484 Even parity See Parity bit Event 188 See also Compound event, Conjunction of events, Disjunction of events, Implication of events, Reinforcing events Exam scheduling 1–2, 524–525 Excluded middle 682–685 Exclusive or 655 Existential quantifier 739, 750, 755–758 Expected value 212–214 Experiment 188 Exponential time 102–103 Expression See Arithmetic expression, Closed expression, Infix expression, Logical expression, Postfix expression, Prefix expression, Quantifier-free expression, Rectified expression, Regular expression Expression tree 228–230, 242–244, 434

F Fact 763 Factor 613 Factorial 57, 60, 170 Fair game 214 FALSE 22 Fan-in/out 712–714 Feature size 711 Feigenbaum, E. A. 335 Feller, W. 221–222 Fermat’s theorem 219 Fibonacci number 135 Field 14 File 8 Find (component of a node) 470–475 Finite automaton See Automaton First 292 First-order logic See Predicate logic Fischer, M. J. 335–336 Floating-point number See Real number Floyd, R. W. 285, 527 Floyd’s algorithm 513–521

780

INDEX

For all See Universal quantifier For-statement 111–112, 115, 117, 121–122, 129 Fortran 641 Forward arc 488, 494 Fredkin, E. 285 free 18 Free variable 741–744 Friedman, A. D. 732 Front 318 Full binary tree 257, 269–270 Full stack 307–308 Full tree Function 17–18, 69, 127–136, 312–318, 370–380 See also Boolean function, Monotone function Fuzzy logic 211

G Garey, M. R. 698 Gate 9–10, 700–701 GCD See Greatest common divisor Genesereth, M. R. 698 Geometric series 42 Global variable 22, 741 See also Static variable Godel, K. 770, 775 Goto See Jump-statement Graham, R. L. 155, 221–222 Grammar 591–641 Graph 369, 451–528, 531 See also Acyclic graph, Bipartite graph, Calling graph, Course-conflict graph, Directed graph, Planar graph, Reduced graph, Undirected graph Greatest common divisor 74–75 Greedy algorithm 481 Green, B. F. 335 Grep See Egrep Ground atomic formula 735 Ground literal 736 Growth rate 99 See also Big-oh Guessing a solution 148–152

H Halmos, P. R. 402 Hash function 362 Hashing 360–366, 376–379, 384, 409 Head, of a list 288 See also Car Head, of a production 593 Head, of a rule 763 See also Conclusion Head, of an arc 452–453 Heap (data structure) 273–279 Heapify 281–282 Heapsort 280–284 Height 226, 244–247, 254, 472–473 Held, G. 450 Hennessy, J. L. 732 Hopcroft, J. E. 155, 335, 527, 589, 641 Huffman, D. A. 589 Hunt, J. W. 335 Hypothesis 686 See also Body, of a rule

I Idempotence 346, 570, 676 Identifier 17 Identity 292, 345, 569, 675 If-statement 112–114, 117, 122, 129, 597, 643 Implicant 661, 665 Implication 650, 652, 679 Implication of events 209–210 Important state 579 Incommensurate functions 108 Incompleteness theorem 770–771 Increment 19 In-degree 462 Independent experiments 195–197, 200– 201 Index 425–426 See also Primary index, Secondary index Index-join 438–439 Indirect recursion 69, 455 Induction 27, 34–51, 253 See also Backward induction, Complete induction, Structural induction Inductive assertion See Loop invariant Inductive definition See Recursive definition Inductive hypothesis 35 Inductive step 28, 35, 44, 59, 132

781

INDEX

Inference rule 686 Infinite set 189, 340, 396–401, 601 Infix expression 243 Infix operator 63, 368 Ingres 450 Injection 371 Inorder 258 Input, circuit 701, 723 Input cursor 618 Input sequence 533 Insert 378, 380, 384, 407, 417–418 Insertion 262–263, 271, 276, 291, 296, 363– 365 Integer 13 See also Natural number Interior node 226, 254 Interpretation 745–751, 769 Intersection 342, 344, 346, 352, 356, 429– 430, 436, 441, 654 Intractable problem 673 Inverse relation 373, 388 Inverter 700 IPL-V 335 IsEmpty (operation on stacks, queues) 292, 308, 318 IsFull (operation on stacks, queues) 308, 318 Iteration 25, 27–34

J Johnson, D. S. 698 Join 432–433, 437–441 Joint probability space 195 Jump-statement 110, 117

K Karnaugh map 660–669 Karp, R. M. 698 Keno 190–192 Kernighan, B. W. 24, 450 Key 32, 411–414, 421 Kleene closure See Closure Kleene, S. C. 589–590 Knowledge representation 3 Knuth, D. E. 88, 155, 221–222, 285, 335, 402, 641 Kreps, P. 450 Kruskal, J. B. 527 Kruskal’s algorithm 479–483 Kuratowski’s theorem 523

L Label 453, 463–465, 536 Labeled tree 228 Language 557, 572, 599–602 Last 292 Last-in-first-out list See Stack Lawler, E. 527–528 LCS 321–327 Leaf 226, 254 Left child 253 Left-factoring 632–633 Leftmost child 235–238 Left-recursion elimination 631–632 Length, of a list 292 Length, of a path 225, 254, 453, 456 Level 226 Lewis, H. R. 698, 775 Lewis, P. M. 641 Lex 565 Lexical analysis 564–565 Lexicographic order 29, 61–62 Library function 109 LIFO list See Stack Line beginning/ending 565–566 Linear search 115, 302 Linear time 92, 103 Linked list 7, 293–301, 310–311, 318–320, 330–331, 375, 381–383 See also Adjacency list Lisp 5, 335 List 7, 286–336, 339, 351–357 See also Doubly linked list, Linked list, Queue, Stack Literal 658, 736 Liu, C.-L. 221–222 LL parser See Table-driven parser Local variable 741 Locality 92 See also 90-10 rule Logarithmic time 103, 106 Logic See Predicate logic, Propositional logic Logic circuit 9–12, 701–731 Logical expression 645–648, 653, 655–660, 705–710, 736–738 Logical operator 19, 109 Longest common subsequence See LCS Lookahead symbol 624

782

INDEX

Lookup 260–262, 291, 294–298, 302–305, 378–379, 381–384, 408, 417–418, 460– 461 Loop 453 Loop invariant 52 Lowest common ancestor 238 Low-order term 98 LR parsing 641

M Machine instruction 96 Macintosh 8 Majority function 704, 730 malloc 18 Manna, Z. 698, 775 Mastermind 169 Matrix See Adjacency matrix Maximal clique 525 Maximal independent set 1–2 Maxterm 660 McCarthy, J. 335 McNaughton, R. 589–590 Mead, C. 732 Mealy, G. H. 335 Mean value 212 Membership 338 Memoing See Dynamic programming Memory 159, 730–731 Mendelson, E. 698, 775 Menon, P. R. 732 Merge 75–79, 136–138, 291 Merge, of connected components 470–475 Merge sort 75–84, 136–144 Metasymbol 593 Micron 711 Microsoft Windows 8 Minimal spanning tree 478–484 Minimization, of automata 555 Minimum distance 502, 514 Minterm 658 Model 769 Module See Abstract data type Modulus operator 19 Modus ponens 688 Monotone function 659 Monte-Carlo algorithm 216–219 Morris, R. 402 MS-DOS 8 Multiplexer 723–730 Multiset 339

Multiway merge sort 82 Munro, I. 155 MUX See Multiplexer

N Name 7, 17 NAND 651–652, 659, 700 Natural join 433 Natural number 340, 396–397 Naur, P. 641 Navigation 423–428 Negation 674–675, 677 See also NOT Neighbor 456 Nested-loop join 437–439 Newell, A 335 Nilsson, N. J. 698 90-10 rule 92 Node 224, 452 Nonassociative operator Nondeterministic automaton 539–556 Nonnegative integer See Natural number Nonplanar graph 522–523 NOR 651–652, 659, 700 NOT 644, 649, 652, 657, 677–679, 700, 740, 755–756 See also Inverter, Negation N P (nondeterministic, polynomial-timesolvable problems) 672–673 NP-complete problem 672–673 NP-hard problem 673 NULL 22 Null character 328 Null statement 117

O O See Big-oh Occurrence, of an element 290 Odd parity See Parity bit One-bit adder 10, 656, 707–709 One-hot decoder 729 One-one-correspondence 371–372 Operating system 8 Operation 18

783

INDEX

Operator See Arithmetic operator, Binary operator, Comparison operator, Complete set of operators, Infix operator, Logical operator, Nonassociative operator, Postfix operator, Prefix operator, Ternary operator, Unary operator OR 644, 649, 652, 657, 675–679, 688, 700, 712–714, 740, 756–757 Ordered tree 227 Ordering 167–169, 178–180, 183 See also Partial order, Postorder, Preorder, Total order Outcome 188 Out-degree 462 Output, circuit 701

P (polynomial-time solvable problems) 672–673 Palindrome 640 Papadimitriou, C. H. 222, 527–528, 698, 775 Parallel execution 699 Parent 224, 237 Parentheses See Balanced parentheses Parity bit 38 Parity function 704 Parse tree 602–610, 630–631 Parsing 617–634 Parsing table 626 See also Table-driven parser Partial anagram 542–546 Partial function 370 See also Function Partial order 390 Partially ordered tree 272–273, 506–512 Pascal 30 Pascal’s triangle 172, 176 Patashnik, O. 155, 221–222 Path 225, 254, 453, 456, 519, 767 Pattern 529–530, 591 Patterson, D. A. 732 Payoff function 212 Perfect induction See Complete induction Perles, M. 641 Permutation 160–167 Peterson, W. W. 402 Pigeonhole principle 638 Pinochle deck 187 Pipe 9

P

Pivot 514 Planar graph 522–523 Plane presentation, of a graph 522 Plauger, P. J. 24 Pointer 7, 15, 109, 232, 235, 237 Poker 184–186 Polynomial time 102 Pop 306, 308 Postfix expression 243 Postfix operator 64 Postorder 241, 492–494 POT See Partially ordered tree POT property See Partially ordered tree Power set 349–350 Precedence, of operators 561–562, 567, 646, 652, 740–741 Predecessor 453, 461 Predicate 734–736, 745 Predicate logic 645, 733–775 Prefix 289 Prefix expression 243 Prefix operator 63 Prenex form 757–758 Preorder 239–241 Primality testing 219 Primary index 414–419 Prime implicant 663 Priority queue 271–279, 506 Probability 187–222 Probability space 188 Probe 306 Procedure See Function Process 9 Product 26, 657, 688 See also Cartesian product, Term Product of sums 660, 693, 738 Product rule 200 Production 593 Profile 64–65 Profiling 92 Program correctness proof 26, 52–59, 84– 87, 130 Program termination See Termination Programming language 6 See also Algol, C, Fortran, IPL-V, Lisp, Pascal, Prolog, SQL Projection 431–432, 436–437, 444–448 Prolog 5, 733

784

INDEX

Proof 682, 759–770 See also Case analysis, Complete proof procedure, Contradiction, Contrapositive, Deduction, Excluded middle, Induction, Program correctness proof, Resolution Propagation delay 712 Proper subset 347 Propositional logic 9, 642–698 Propositional variable 643, 734 Prototyping 21 Push 306, 308 Pushing projections 444–448 Pushing selections 442

Q QED 589 Quadratic time 97, 103 Quantifier See Existential quantifier, Universal quantifier Quantifier-free expression 757 Query 407 See also Relational algebra Queue 318–321

R Rabin, M. O. 221–222, 589–590 Random number generator 191 Range 368, 414 See also Current domain/range, Declared domain/range Reachable nodes 498–499 See also Warshall’s algorithm Read-statement 110 Real number 13, 340, 399–400 Rear 318 Record See Structure Rectified expression Recurrence relation 132, 144–154 Recursion 6, 25, 69–75, 132–136, 239–247, 256–257 See also Direct recursion, Divide and conquer, Recursive descent parsing Recursive definition 26–27, 59–69 Recursive descent parsing 617–625 Reduced graph 391 Reflexive-transitive closure 500 Reflexivity 388, 390–391, 674 Regular expression 5, 556–590, 634–639 Reinforcing events 211–212

Reingold, E. M. 402 Rejection, of input 533 Relation 366–369, 380–396, 403–411 See also Binary relation Relation scheme 405 Relational algebra 428–448 Repeated substitution 134–135, 145–148 Replacement 167, 169, 183 Resolution 692–697 Restructuring, of hash tables 366 Retrieve 292 Return See Jump-statement Return-value 17 Reuse See Software reuse Right child 253 Right sibling 235–238 Ripple-carry addition 11–12, 716 Ritchie, D. M. 24 Roberts, E. 24, 88 Robinson, J. A. 698 Root 224 Rooted tree See Unrooted tree Rosenkrantz, D. J. 641 Rule 763 Running time 27, 89–155, 268–271, 278– 279, 283, 354–356, 365–366, 379, 384– 385, 476, 482–483, 491, 497, 499, 511– 514, 527, 672 Run-time organization 312 Run-time stack 313 Russell’s paradox 341

S Satisfiability problem 673 Scott, D. 589–590 Search See Binary search, Depth-first search, Linear search, Ternary search Secondary index 419–423 Selection 167–178, 430–431, 437, 441–443 Selection sort 29–33, 72–73 Selection statement See If-statement Sentinel 117, 303 Sequential circuit 702 Sequential execution 699 Sequential search See Linear search Set 337–403 See also Infinite set, Probability space

785

INDEX

Set former 339 Sethi, R. 24, 335, 589, 641 Settled node 502 Shamir, E. 641 Shannon, C. E. 732 Shortest path See Dijkstra’s algorithm, Floyd’s algorithm Sibling 226, 254 See also Right sibling Simple cycle 454, 457 Simple statement 109–110, 117, 597 Simplicity 90, 104 Singleton set 350 Size of arguments 71, 85, 127–128, 132 Software development 20–22 Software reuse 21 Sorting 28–33, 163–166, 291, 297 See also Heap sort, Merge sort, Selection sort, Sort-join, Topological sorting Sort-join 438–439 Source node 502 Spanning tree See Depth-first search tree, Minimal spanning tree Sparse graph 461 Special path 502 Splitting lists 79–80, 138–141 Splitting selections 442 SQL 435, 733 Stack 306–318 Start state 533, 548 Start symbol 594 State 530 See also Accepting state, Dead state, Important state, Start state State machine See Automaton Statement See Assignment-statement, Block, of a program, For-statement, Ifstatement, Jump-statement, Readstatement, Simple statement, Whilestatement, Write-statement Static aspects of data model 6 Static variable 17, 313 See also Global variable Stearns, R. E. 641 Steiglitz, K. 527–528 Stonebraker, M. 450 String See Lexicographic order

Strong induction See Complete induction Stroustrup, B. 24 Structural induction 248–252, 259, 573 Structure 14, 32, 109, 368, 405 Structure tree 118–123 Structured query language See SQL Sublist 289 Subsequence 289 See also Common subsequence, Longest common subsequence Subset 347, 387 Subset construction 547–554 Substitution, for variables 760–762 Substitution of equals for equals 669–670 Substitution principle 670–672, 751–752 Subsumption 676 Subtree 226 Successor 453, 461 Suffix 289 Sum 26, 657, 688 Sum of products 658, 738 Summation rule 105–107 Superset 347 Surjection 371 Symmetric difference Symmetry 388–389, 391, 462 Syntactic category 593–594 Syntax tree See Expression tree System R 450 Szymanski, T. G. 335

T Table 405 See also Relation Table-driven parser 625–634 Tabulation See Dynamic programming Tail, of a list 288 See also Cdr Tail, of an arc 452–453 Tarjan, R. E. 285, 527–528 Tautology 669–674, 686–687, 691, 751–759 Tautology problem 672 Term 613 See also Product Terminal 593–594 Termination 57 Ternary operator 64 Ternary search 306 Test suite 22

786

INDEX

Text editor 564 There exists See Existential quantifier Thompson, K. 589–590 Tight bound 103–104 Token 564 Tonge, F. M. 335 Top of stack 306 Topological sorting 394, 497–498 Total function 370 Total order 390–391 See also Topological sorting Transformation 347 Transition 532 Transitive closure 394, 500 Transitive law 101–102, 387, 390–391, 645, 674 Traversal See Inorder, Postorder, Preorder Tree 223–285, 470–475 See also Binary tree, Depth-first search tree, Expression tree, Full tree, Minimal spanning tree, Parse tree, Partially ordered tree, Structure tree, Trie, Unordered tree, Unrooted tree Tree arc 488, 494 Triangular number 41 Trie 233–234, 238 TRUE 22 Truncation 328 Truth assignment 647, 745 Truth table 10, 649–655 Tuple 366, 404–405 Turing, A. M. 775 Turing machine 772–773 Type descriptor 17 Type system 6, 13–17

U Ullman, J. D. 155, 335, 450, 527, 589, 641 Ullman, P. M. 542 Unambiguous grammar See Ambiguous grammar Unary operator 63 Unary relation 366 Uncountable set See Countable set Undecidability 772 Undecidable problem 639 Undirected graph 456–458, 462–463 Union 342, 344, 346, 352–356, 429–430, 436, 441, 558, 569–570, 654 Union type 14

Universal quantifier 739, 750, 755–758, 760 Universal set 341, 345 UNIX 8–9, 529–530, 546, 564–567, 589 Unordered tree 478 See also Ordered tree Unrooted tree 478–479

V Variable 735, 753–754 See also Bound variable, Free variable, Global variable, Local variable, Propositional variable, Static variable Venn diagram 342–343, 346–347, 654

W Wagner, R. A. 335–336 Waldinger, R. 698, 775 Warshall, S. 527–528 Warshall’s algorithm 515 Weak induction 44 Weight 478 Weinberger, P. J. 450 While-statement 57, 115, 117, 120–121, 128, 597 Wild card 566 Williams, J. W. J. 285 Witness 97 Wong, E. 450 Worst-case running time 93, 268–269 See also Running time Write-statement 110

Y Yamada, H. 589–590 Yield, of a tree 603