Data Structures & Algorithms: Review of Discrete Math

Instructor: M.S. Schmalz

In this class, we must express mathematical operations in a rigorous fashion, in order to (a) understand their structure and function, (b) predict consequences of changing function or procedure parameters, and (c) have a unified basis for comparing algorithms. Thus, we provide the following brief theoretical introduction.

NOTE: Bold-italic-face titles or names denote special terms that we will use in class.

1. Sets and Set Operations

Sets are the basic entities and are the building blocks of mappings that we will subsequently use to define images. A few concepts and conventions are noteworthy:

Sets are customarily denoted by upper-case letters in roman (regular) or italic face (e.g., A, G), or by the empty set Ø.

Value Sets or Alphabets are denoted by bold upper-case letters from the head of the alphabet (e.g., A, B, ...). Additionally, we call F the generalized value set. Commonly-used value sets include the

• Natural numbers: N

• Integers: Z

• Real numbers: R

• Complex numbers: C

Furthermore, we have the integers modulo n, which are denoted by Z_n. In the special case of the binary numbers, we write B Z₂ for purposes of brevity.

Intervals. Occasionally, we use a concise specification of a contiguous subset of a given set, called an interval. For example, [1,4]Z denotes the set {1,2,3,4}, while the half-open interval (1,4]Z denotes the set {2,3,4}. Similarly, (2,4]R = {xR: 2 < x 4}.

Point Sets, Domain Sets, or Domains are denoted by bold upper-case letters from the tail of the alphabet (e.g., U, V, W, X, and Y). Additionally, we call X the generalized point set. Customary point sets include

• Euclidean n-space: Rⁿ

• Discrete n-space: Zⁿ

Set Operations. The customary set operations of union (), intersection (), subtraction (\), complement (´), cardinality (|A|), and choice (choice) are used in this course.

Unary arithmetic functions such as -x or sin(x) are used in this course. Such functions can be applied to subsets of the real numbers (e.g., max or , min or , and abs). Note that abs denotes absolute value of a set instead of |A|, which is reserved for cardinality.

2. Arrays

One usually thinks of an array as a two-dimensional matrix of reals or integers, which is sufficient for this class.

Definition. A vector a Fⁿ has n elements, each of which is a member of a set F. We can also write a as [a_n], which is defined by its element a_i F, i = 1..n.

Assumption. For the purposes of this course, an array a F_{m × n} is assumed to have m rows and n columns, where each element of the array, denoted by a_i,j, is a member of a set F. We can also write a as [a_m,n], which is defined by its element a_i,j F, i = 1..m, j = 1..n.

Remark. Alternatively, a vector or array can be thought of as a mapping from a point set (domain of the mapping) to a value set (range space of the mapping).

Example. Given X R_{m × n}, a mapping a : X -> R denotes a real-valued array a with m columns and n rows. This is also a concise way of denoting the set of all mappings from X to F, which is a little different from the notation we used in Discrete Math class.

Definition. If a F^X, then X = domain(a) and F = range(a).

Definition. The graph of a F^X is denoted by

G(a) = {(x, a(x)) : a(x) F, x X} .

We also write a G(a), where denotes equivalence.

Observation. Given an n-tuple a Fⁿ, observe that p_k denotes projection onto the k^th coordinate, such that p_k(a) denotes the k-th value of a, that is a_k.

Note that p₁(G(a)) = X = domain(a) and p₂(G(a)) = F = range(a).

Remark. Although a point set or value set can be any set, one must take care to specify arrays using only those value or point sets for which operations are defined.

Definition. A special class of arrays are called constant-valued arrays. Given a constant value
k F, we denote a constant array k {k}^X as

k {(x, a(x)) : a(x) = k, x X} = {(x,k): x X} .

Example. The unitary array on X is denoted as 1_X, or simply 1, with X understood.

3. Array Operations.

In order to manipulate arrays, we must specify a few simple operations. We thus concentrate on the pointwise unary and binary operations, as well as matrix multiplication, which are frequently used in computer science.

Definition. Let a denote an array in F^X. A unary pointwise operation g:F^X -> F^X is induced over X by the corresponding scalar operation g:F -> F.

Example. We have the following cases of real and Boolean negation:

-a {(x, -[a(x)]) : a(x) R, x X}
¬a {(x, ¬[a(x)]) : a(x) B, x X}

where B = {0,1}, as before.

Definition. A special type of unary operation is called the global reduce operation O: F^X -> F, which maps an array a F^X to an element of its value set.

Example. If a B^X, then the operation

a = a(x)

determines the number of unitarily-valued elements in a. Alternatively, replacing with would tell us if there are any unitary values in a.

Definition. A binary pointwise array operation g:F^X × F^X -> F^X is induced over X by the corresponding scalar operation g:F × F -> F. Note that the operands (input arrays) must have the same domain, which the result (output array) also has.

Example. Given the arrays a,b F^X, we have the pointwise arithmetic operations

c = a + b {(x, c(x)) : c(x) = a(x) + b(x), where a(x),b(x) R, x X}
c = a · b {(x, c(x)) : c(x) = a(x) · b(x), where a(x),b(x) R, x X} .

Example. If a and b are Boolean arrays on X, then we have the following definition of the exclusive-or function:

c = (a xor b) {(x, c(x)) : c(x) = |a(x) - b(x)|, x X} .

Observation. A wide variety of binary operations can be described (e.g., a^b and log_ab), provided that value sets are properly defined. However, in the case of the logarithm, we must set range(a), range(b) R⁺, the positive reals. Otherwise, the logarithm is not defined.

Definition. A matrix is an m × n-element array (i.e., m rows and n columns). Matrix addition and subtraction were defined previously in terms of pointwise arithmetic operations on arrays.

Definition. A special type of operation, called matrix multiplication, is used to multiply matrices. Given an m × n-element matrix a and an n × p-element matrix b, matrix multiplication of a and b, denoted by c = a · b, is defined in terms of an element of c, as follows:

c_i,j = a_i,k · b_k,j

Thus, matrix multiplication requires n multiplications per element of c. Since c has m rows and p columns, there is a total requirement of mnp multiplications and mp(n-1) additions for multiplying a by b.

4. Basic Combinatorics.

It is useful to know the probability of finding a given object in a collection of objects. This concept and associated techniques have applications in gaming theory, simulation, and analysis of algorithm complexity.

Definition. The number of possible combinations of n things taken k at a time, in no particular order, is given by

C(n,k) = n! / (k! · (n - k)!) .

where x! denote x factorial.

Definition. The number of possible permutations of n things taken k at a time, in a particular order, is given by

P(n,k) = n! / (n - k)! .

Definition. The probability of occurrence of an event E that has N possible combinations in a total of M N outcomes is given by

Pr(E) = N / M .

Definition.The product rule of probabilities states that if two events E₁ and E₂ have respective probabilities p₁ and p₂, and E₁ and E₂ are independent, then the probability of E₁ and E₂ occurring simultaneously (also called conjointly) is given by

Pr(E₁ and E₂) = Pr(E₁) · Pr(E₂) = p₁ · p₂ .

Example. Given a standard deck of playing cards, what is the probability of having three cards from the suit called hearts in a hand of five cards?

Since there are 13 hearts in a deck of cards, and we are choosing three of them in no particular order, we denote the number of possible combinations as C(13,3). Since there are 52-3 = 49 cards remaining, of which we choose any two, the remaining number of combinations are denoted by C(49,2). The total number of combinations possible in a hand of five cards is denoted by C(52,5). By the product rule of probabilities, we have:

Pr(3-hearts in five-card-hand) = C(13,3) · C(49,2) / C(52,5) .

5. Big-Oh Complexity Notation.

In algorithm and software design, we need to be able to analyze an algorithm to determine how many operations it requires, and under what conditions. In Discrete Math class, we discussed Big-Oh, Big-Omega, and Big-Theta notation. In this class, we will mainly use Big-Oh notation, which is summarized as follows.

Observation. "Big-Oh Notation" (e.g., O(x²) reads Big-Oh of x-squared) is used to specify the upper bound on the complexity of a function f. The bound is specified in terms of another function g and two constants, C and k.

Definition. Let f,g : R -> R be functions. We say that f(x) = O(g(x)) if there exist constants C,k R such that

| f(x) | C · | g(x) | ,

whenever x > k.

Example. Let f = x³ + 3x². If C = 2, then

| f(x) | = | x³ + 3x² | 2 · | x³ | ,

whenever x > 2. The constants C,k = 2 fulfill the preceding definition, and f(x) = O(g(x)).

Definition. An algorithm is a finite set of instruction for performing a computation or solving a problem.

Classification. In this course, we will concentrate on several different types of relatively simple algorithms, namely:

Selection -- Finding a value in a list, counting numbers; Sorting -- Arranging numbers in order of increasing or decreasing value; and Comparison -- Matching a test pattern with patterns in a database .

Properties of Algorithms. It is useful for an algorithm to have the following properties:

Input -- Values that are accepted by the algorithm are called input or arguments.

Output -- The result produced by the algorithm is the solution to the problem that the algorithm is designed to address.

Definiteness -- The steps in a given algorithm must be well defined.

Correctness -- The algorithm must perform the task it is designed to perform, for all input combinations.

Finiteness -- Output is produced by the algorithm after a finite number of computational steps.

Effectiveness -- Each step of the algorithm must be performed exactly, in finite time.

Generality -- The procedure inherent in a specific algorithm should be applicable to all algorithms of the same general form, with minor modifications permitted.

Measures of Complexity. In order to facilitate the design of efficient algorithms, it is necessary to estimate the bounds on complexity of candidate algorithms. Complexity is typically represented via the following measures, which are numbered in the order that they are typically computed by a system designer:

Work W(n) -- How many operations of each given type are required for an algorithm to produce specified output given n inputs?

Space S(n) -- How much storage (memory or disk) is required for an algorithm to produce specified output given n inputs?

Time T(n) -- How long does it take to compute the algorithm (with n inputs) on a given architecture?

Cost C(n) = T(n) · S(n) -- Sometimes called the space-time bandwidth product, this measure tells a system designer what expenditure of aggregate computational resources is required to compute a given algorithm with n inputs.

Analytical Procedure. Analysis of algorithmic complexity generally proceeds as follows:

Step 1. Decompose the algorithm into steps and operations.

Step 2. For each step or operation, determine the desired complexity measures, typically using Big-Oh notation, or other types of complexity bounds discussed below.

Step 3. Compose the component measures obtained in Step 2 via theorems presented below, to obtain the complexity estimate(s) for the entire algorithm.

Example. Consider the following procedure for finding the maximum of a sequence of numbers. An assessment of the work requirement is given to the right of each statement.

    Let {an} = (a1,a2,...,an)
     { max = a1               # One I/O operation
       for i = 2 to n do:     # Loop iterates n-1 times
         { if ai  max then   # One comparison per iteration
              max := ai }     # Maybe one I/O operation
     }

Analysis. (1) In the preceding algorithm, we note that there are n-1 comparisons within the loop. (2) In a randomly ordered sequence, half the values will be less than the mean, and a₁ would be assumed to have the mean value (for purposes of analysis). Hence, there will be an average of n/2 I/O operations to replace the value max with a_i. Thus, there are n/2 + 1 I/O operations. (3)This means that the preceding algorithm is O(n) in comparisons and I/O operations. More precisely, we assert that, in the average case:

W(n) = n-1 comparisons + (n/2 - 1) I/O operations.

Regimes of Complexity. Using Big-Oh notation, we find the following regimes to be useful categories for classifying algorithm complexity, where an algorithm has n inputs:

1. Constant complexity -- O(1), regardless of n

2. Logarithmic complexity -- O(log n)

3. Linear complexity -- O(n)

4. Log-linear complexity -- O(n · log(n))

5. Quadratic complexity -- O(n²)

6. Cubic complexity -- O(n²)

7. Exponential complexity -- O(kⁿ), where k is a constant greater than unity.

For example, later in this course we will show that sorting a random sequence of numbers in increasing or decreasing order requires at least log-linear work.

The preceding concepts and theory are not the only tools required for this class, but comprise the majority of building blocks we will employ. Recursion relations, which will also be employed, will be reviewed in a later section of these notes.

This concludes our discussion of basic concepts from discrete math. Other concepts will be defined as they are introduced in theory development.