Mathematics for Computer Science

INDEX682

good count, 181
Google, 661
graph
bipartite, 307
coloring problem, 320
matching, 310
perfect, 310
shortest path, 241
valid coloring, 320
graph coloring, 320
graph ofR, 74
gray edge, 336
greatest common divisors, 183
grid, 283
grows unboundedly, 22

half-adder, 56
Hall’s Matching Theorem, 308
Hall’s Theorem, 311, 509
Hall’s theorem, 347
Halting Problem, 95
Handshake Lemma, 303
Hardy, 183, 199
Harmonic number, 424
Hat-Check problem, 619
head, 235
Herman Rubin, 640
Hoare Logic, 395
hypothesis, 37

identity relation, 268
image, 73 , 76
implications, 13
incident, 300
Inclusion-Exclusion, 471, 473
inclusion-exclusion for probabilities,
534
Inclusion-Exclusion Rule, 471
increasing subsequence, 275
in-degree, 235

independence, 549

independent, 627

independent random variables, 575

indicator random variable, 574

indicator variable, 586, 650

indicator variables, 576

indirect proof, 18

Induction, 113

induction hypothesis, 116

inductive step, 116

inference rules, 11

infinite, 87

Infinity axiom, 100

infix notation, 74

injection relation, 82

injective, 75

integer linear combination, 186

interest rate, 438

interpreters, 95

intersection, 68

Invariant, 187

invariant, 122

inverse, 77 , 81

inverse image, 77

irrational, 15

irreflexive, 245 , 258

irreflexivity, 245

isomorphic, 247 , 382

Kayal, 185

King Chicken Theorem, 262

known-plaintext attack, 208

latency, 282

latency for min-congestion, 296 , 297

Latin square, 344

lattice basis reduction, 483

Law of Large Numbers, 633

leaf, 331

lemma, 10