Mathematics for Computer Science

INDEX 689

symbol meaning

 the empty string/list

A the finite strings over alphabetA

rev.s/ the reversal of strings

s
t concatenation of stringss;t; append.s;t/

#c.s/ number of occurrences of charactercin strings

mjn integermdivides integern;mis a factor ofn

gcd greatest common divisor

.k;n/ fijk < i < ng

Œk;n/ fijki < ng

.k;nç fijk < ing

Œk;nç fijking

hu!vi directed edge from vertexuto vertexv

IdA identity relation on setA:aIdAa^0 iffaDa^0

R path relation of relationR; reflexive transitive closure ofR

RC positive path relation ofR; transitive closure ofR

hu—vi undirected edge connecting verticesu neqv

E.G/ the edges of graphG

V.G/ the vertices of graphG

Cn the length-nundirected cycle

Ln the length-nline graph

Kn then-vertex complete graph

L.G/ the “left” vertices of bipartite graphG

R.G/ the “right” vertices of bipartite graphG

Kn;m the complete bipartite graph withnleft andmright vertices

Hn thenth Harmonic number

Pn

iD 1 1=i

 asymptotic equality

nŠ nfactorialWWDn
.n1/


 2 
 1

o./ asymptotic notation “little oh”

O./ asymptotic notation “big oh”

‚./ asymptotic notation “Theta”

./ asymptotic notation “big Omega”

!./ asymptotic notation “little omega”

PrŒAç probability of eventA

Pr



AjB



conditional probability ofAgivenB

ExŒRç expectation of random variableR

ExŒRjAç conditional expectation ofRgiven eventA

VarŒRç variance ofR

R standard deviation ofR