Table of Contents for

Algorithmic Problem Solving

Index

Bool set of booleans 224

false boolean constant false 107, 222, 225

true boolean constant true 222, 225, 269

set of integers 233, 296

set of natural numbers 233, 296

set of real numbers 233

:= assignment symbol 12–13

empty set 224

{} empty set (alternative notation) 224

∞ infinity 239

↑ (binary) maximum 312–315

∈ membership relation 224

↑ (binary) minimum 312, 315

set brackets 224

|| number of elements 234

⇓ minimum quantifier 303

⇑ maximum quantifier 303

⇐ if, follows from 246, 262, 274

⇒ only if, implies 246, 262, 274

< less than 248, 260–261

∧ conjunction (“and”) 271

∨ disjunction (inclusive “or”) 270

= equals 261

≡ equivalence 261

≡ equivalence quantifier 303

inequivalence 114

inequivalence quantifier 303

¬ (boolean) negation 107, 269

∑ summation 287

multiplication 297

∀ “for all” quantifier 191, 279, 298

∃ “there exists” quantifier 191, 298

(arbitrary) quantifier 302

{ } set comprehension 288

bv : range : term quantifier notation 302

A

absorption 272–273

abstraction 11–12, 30–31, 41, 301

absurdity 276

acyclic graph 70, 328, 354–357

addition of a semiring 244

additive inverse 244

al-Adli ar-Rumi 218

adults and children problem 36, 40

algebraic properties 236–244

algorithmics 6

Allardice, R.E. 156

anti-monotonicity 311

anti-reflexive relation 112

anti-symmetric relation 251–252, 354

anti-symmetry

of “at most” 279, 309–310

of “follows from” 279, 283

of the subset relation 283

arithmetic 237

array, two-dimensional 351

assertion 162

assignment

simultaneous 12

statement 12

symbol 12–13

associative operator 99, 102

associatively 103–104

associativity 102, 240–241, 267, 294

of addition 97, 99

of conjunction 273

of disjunction 270

of equality 99

of equivalence 99, 104–105, 107

of maximum 313

of multiplication 99

of relation composition 331–332

atomic proposition 97

auxiliary variable 21

axiom 97

B

bag 185, 227, 302

balanced ternary notation 146

base type 233

basis (of an inductive argument) 119

bijection 295, 340

binary operator 230

binary relations 112, 246–257

binary search 163–166, 197–198

binomial coefficient 361

addition formula 363

black and white balls problem 8–9

Boole, George 222–223, 248–249

boolean 20, 222

boolean algebra 223, 237, 267–283

boolean operators 244–246

bound variable 223, 226, 286–287, 289–291, 302–303

bridge problem 4–5, 54–63, 183–200

brute-force search 35–42, 91, 201

C

calculation 30–31, 257–263

cancellative 311

capture (of free variables) 291, 299, 303

carrier (of an operator) 237

cartesian product 79, 233–234

case analysis 64, 157, 314

chameleons of Camelot problem 178, 180

characteristic function 236

Chen, Wei xii

chicken-chasing problem 5, 166–177

chocolate-bar problem 7–8, 10–16

Chong, Siang Yew, xii

Claus, M. 147

closure (of a relation) 252

reflexive 252, 254, 309

reflexive transitive 252, 254, 338–339, 354

transitive 252, 254, 328, 334–339

closure (operators) 353–356

coin problem 81, 92

combinatorics 40, 185, 357–366

commutativity 237

comparison 137

complexity theory 65, 217

composition

of functions 340

of relations 330–332, 347–348

conclusion of a calculation 260

conditional statement 63–65, 72

conjectures 128

false 129–130

conjunction 244–245, 271–274

conjunctional (use of an operator) 103–104, 250, 261

constant 222, 226

constant-false function 245

constant-true function 245

construction 131

continued

addition 108, 240

disjunction 270

equality 23, 104, 268

equivalence 104, 107, 115, 269

expression 103, 240, 242, 250–251

product 286

summation 285

contradiction 274, 276

contraposition 109–111, 276, 310

convergence (of infinite summations) 297

converse 247, 249, 310

cutting the plane 121, 123–126

cycle 328

D

daisy game 81–82, 92

De Morgan’s rule 273–274, 276, 306

decryption 116

deduction, mathematical 128

definitional equality 229

diagrams 12, 40

Dijkstra, Edsger W. xii, 66, 117, 146, 180, 217

dimension 232, 351

directed state-transition graph 37

disjoint sum 233–234

disjunction 244–245, 270–272, 274

distributivity 241–242, 333

addition over maximum 314

“at most” over maximum 313

conjunction through disjunction 273

conjunction through equivalence 274

disjunction through conjunction 273

disjunction through equivalence 270

“if” over conjunction 278, 282

“if” over disjunction 278, 282

implication 276, 279

properties 304–306

distributivity rule

existential quantification 301

general quantifications 306

summations 297

universal quantification 300

divides (relation on numbers) 247

divides relation 252, 315–316

divisor 315

domain 228, 235

dominoes problem 9

dotdotdot notation 285–286, 291, 298

double negation, rule of 109, 281

duality (between conjunction and disjunction) 274

dummy 226, 287–288, 302–303

dummy renaming 291–292, 299–300, 303

dummy rules 292

Dutch national flag problem 180

dynamic programming 198, 357

E

edge 38, 70, 325

edge-count 327

element (of a set) 224

elementary algebra 243

empty-box problem 8, 16–21

empty path 327

empty range 161, 287, 294, 299, 300–301, 303

empty relation 332–333

empty set 224, 236, 280

empty word 265

encryption 116

equality 255–256, 260, 261

definitional 229

of booleans 98–100, 103–104, 244–245, 261, 267–269

of propositions 97

of sets 279

symbol 255–256, 261

equivalence class 257

equivalence relation 216, 256–257

equivales 104

Euclid’s algorithm 316

everywhere brackets 100, 223

excluded middle 271

exclusive-or 26, 114, 116

existential quantification 64, 297–298, 300–301, 303

expression 222

boolean 222–223

F

factorial function 359–360

factorisation 242

fake-coin problem 137–144

Ferreira, João F. xii, 180

field 282

figures 12, 40

Find program 180

flashlight problem 4–5, 200

follows-from relation 274

for-all quantification 71

for loop 165, 197

FORTRAN 229

Fraser, A.Y. 156

free variable 223, 226–227, 289–291, 303

frequencies 343–344

function 227–232

application 54–55, 228–230

composition 340

higher-order 235

space 233

types 235–236

unary 229

functional relation 340

G

Galois field 282

games 67–93

Gantt chart 368

Gardner, Martin 156

Gaussian elimination 353

global variable 290

goat, cabbags and wolf problem 36, 37–39, 41, 44

Gödel, Kurt 117

golden rule 271–272, 282

graph

acyclic 70, 328, 354–357

bipartite 329

directed 37, 325–327

labelled 325–326

and relations 328–339

state-transition 37

undirected 37, 326–327

greatest common divisor 230, 238–239, 241, 252, 315–316

Gries, David xii, 73, 180

group 216, 243

abelian 243

guard 63

guarded command 63–65

H

Hamiltonian-circuit problems 216–217

handshake problems 112–113

Hasse diagram 246, 252–255, 328, 339

heterogeneous relations 328–329

hint (in a calculation) 14, 259

Hoare, C.A.R. 50, 180

Hoare triple 50, 72

homogeneous relation 328, 334

I

idempotence 239–240

of disjunction 270

idempotent semiring 244

identity function 235, 245

identity relation 338

if relation 20, 262, 275

if step 19, 262–263

iff (if and only if) 278, 282

implication 25–27, 244, 272–279

implies relation 274

in-line expression 261

inclusive-or 26

indirect equality 310, 313–314

induction 15, 119–135, 157

in experimental sciences 128

hypothesis 124, 126

mathematical 128

principle of mathematical 15–16, 30

step 119

inequality 58, 309–312

of booleans 245

inequivalence 114–115

infinite quantification 287

infinite summation 297, 301

infinity 239

infix notation 54–55, 229

infix operator 102–103

injective relation 340

input---output relation 4

instance (of an expression) 223

integer division 316–320

intermediate-value theorem 163

interpretation 31

intersection (of sets) 225, 280

invariant 7–34, 159

of an assignment 13, 15

system 38

inverse distributivity law 242

inverse functions 295

isomorphism 234, 328

iterative algorithm 157–158

K

knave 95

knight 95

knights-and-knaves puzzles 95–117

knight’s circuit 201–217

Knuth, Donald E. 6

L

law 14, 96–97, 223–224

least common multiple 238, 316

Leibniz 278

see also substitution of equals for equals

Leibniz, Gottfried Wilhelm 97, 255–256, 277

Leibniz’s rule 99, 255, 267, 278

lexicographic ordering 184

limit (infinite quantification) 297

linear combination 18

linear search 165–166, 197

list comprehension 302

local variable 289

logical connective 97, 244

loop 157–160

body 158

losing position 68

lower bound 183–184, 279

Loyd, Sam 5, 166–169, 180

Lucas, Edouard 147

Lukasiewicz, J. 117

M

Manhattan distance 169

Marked-coin problem 140–143

matchstick games 67–77, 79–83, 88–89, 128–129

matrices 351–353

measure of progress 159

membership relation 224

Mendes, Alexandra xiii

meta-rule 277

mex function 85, 91

mex number 85–86, 92

calculation of 87–91

Michaelis, Diethard xii, 180, 217

modular arithmetic 25, 316–322

modulo-n number 320–322

modulus 25

modus ponens 273, 276–277

monoid 243

monotonicity 310–311, 333

multiple 315

multiset 185, 227

Murray, H.J.R. 217

mutual implication 278–279, 282

N

naming the elements of a problem 36, 41, 44

natural language 105–106

natural number 119

negation 106–117, 269

boolean 245

modulo Q 323

nervous-couples problem 36, 40, 42–50, 179–180, 358–359

nesting 290, 292–293, 295, 299–300, 303

Nim 92

node 38, 70, 325

non-deterministic choice 23–24

notation, mathematical 221

NP-complete problems 217

number theory 309–324

O

one-point rule 294–295, 299, 301, 303

one-to-one correspondence 340

only-if relation 262, 275

only-if statement 26

only-if step 263

operator

binary 230

precedence 230–232

symbol 230

unary 229

order isomorphism 311

ordering 252–255

lexicographic 184

partial 252–253

total 252, 309, 313

overloading 20, 233–234, 256

overweight problem 36, 39–40

P

parameter 5

parity 23, 104–105

parsing 232

partial ordering 252–253

path 39, 327–328

counting 341–343

empty 327–328

finish node 327

simple 328, 336

start node 327

path-finding problems 341–351

permutation 56, 359–360

Pi notation 286

point-free 335–336, 338

Pólya, George 17

polymorphism 235

polynomial 132

postcondition 50

postfix notation 228

power set 236

precedence 231

in calculations 262

operator 230–232

precondition 50

predicate 226

prefix notation 228

problem decomposition 35–36, 45–48

product 301, 303

of a semiring 244

proposition 97

atomic 97

Q

quantification 71

quantifier 285–308

notation 286–297, 302–303

Quicksort 180

quotient space 257

R

range

empty 161, 287, 294, 299–301, 303

of a function 235

infinite 306

part 303–304

of a quantification 286–288, 302

rearranging

rule 300, 301, 303–304

summations 293–297

universal quantification 299

Recorde, Robert 106, 255 recurrence relation 361, 363

recursion 151

reflexivity 98, 247–248, 267, 276

regular algebra 354

relation

algebra 237

anti-symmetric 251–252, 354

binary 112, 246–257, 328

composition 330–332, 347–348

empty 332–333

equivalence 256–257

functional 340

heterogeneous 328–329

homogeneous 328, 334

recurrence 361, 363

reflexive 247–248

symmetric 112, 248–249

total 340

transitive 249–251

union 332–334

universal 333

release (of bound variables) 291–292, 299, 303

replacement rules 276–279

ring 244

river-crossing problems 35–66

Roget, Peter Mark 217

Rote, Günter 200

S

scope 289–290

of bound variables 287

self-loop 326–327

semantic side condition 289

semiring 243–244, 349–350, 353–354,

sequential composition 51, 157

set 224–227

calculus 279–281

cardinality 234

comprehension 225–227, 281

empty 224, 236, 280

enumeration 224

equality 279

finite 224

intersection 225, 280

union 225, 280

shortest distances 344–345

shunting 276

side condition 289, 291, 299–300

Sigma notation 285–286

skip statement 22–23

Smullyan, Raymond 117

splitting rule

for existential quantifications 301

general form 303

idempotent operators 304

for summations 294–295, 299

for universal quantification 299–300

Sprague---Grundy number 92

state-space explosion problem 40

state-transition 37

graph 37

straight-move circuits 202–206

strengthening 27, 262–263, 275–276

subset 236

substitution 277

of equals for equals 61, 99, 255, 267, 257, 259, 277–278

subtraction-set games 74–78

in quantified expressions 291

sum of games 78–91

summation 287–288, 301–303

properties 291–297

supersquares 206–209

surjective relation 340

symmetric 98–99, 267

operator 102

relation 112, 248–249

symmetry 35–36, 41–44, 46–47, 81–82, 237–238, 294

of addition 99, 237

of disjunction 270

of equivalence 107

of multiplication 99, 237

syntactic side condition 289

T

target 235

Tarski, Alfred 117

term (of a quantification) 286–287, 302

rules for 296–297, 300, 304

termination condition 159

tetromino 9–10

tetrominoes problem 9–10, 24–30

thru 64

tiling problem 135

topological ordering 355–357

topological search 70, 88, 356–357

torch problem 200

total ordering 252, 309, 313

total relation 340

Tower of Hanoi 147–156

trading rule 291, 296, 300–301, 304

transitive closure 252, 254, 328, 334–339

transitive relation 249–251, 260

transitivity 99, 103, 267

of equality 99, 260

of implication 278

of less-than 260

translation rule 295–296

idempotent operators 307–308

trapezium problem 121–123

triomino problem 121–122, 126–127

trit 146

truth table 244–245

tumbler problem 8, 22–24, 179

type 224–225, 232–236

dependent 86

type (of a bound variable) 302

U

unary function 229

unary operator 229

undirected state-transition graph 37

union 225

of sets 225, 280

of relations 332–334

unit 287, 302

of disjunction 271

of a symmetric binary operator 238–239

universal quantification 71, 161, 279, 297–303

universal relation 333

universe 225

unnesting 291, 293

upper bound 183–184, 279

V

van Gasteren, A. (Netty) G.M. 66

variable 222

bound 223, 226, 286–287, 289–291, 302–303

free 223, 226–227, 289–291, 303

verification 130–131

vernacular, mathematical 221

Vierkant Voor Wiskunde 34

W

weakening 27, 263

while statement 159

Wiltink, Gerard 117

winning position 68

winning strategy 67–74

Woodward, John, xii

Z

zero of a symmetric binary operator 238–239