Chapter 3
The Fundamentals: Algorithms, the Integers, and Matrices

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter3/self_assessments.html - Chapter self-assessment with answers and explanations .

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter3/extra_examples.html - Extra examples with solutions.

 

Control flow of algorithms - Supplement to Chapter 3.

Control Flow

Sequence

sequence - each statement sequentially executed.

Example

x ← 1 x ← x + 1

Selection

single selection - conditionally executes set of statements.

Example

if x < 0 then x ← x + 1 y ← x

 

two selection - conditionally executes one of two sets of statements.

Example

if x < 0 then x ← x + 1 y ← x else x : = x - 1

 

multiple selection - based on criteria, executes one of multiple sets of statements.

Example

switch x case 1 : x ← x + 1 case 2 : x ← x  - 1 default : x ← 0

 

Loops

definite loop - at the start of the loop, can determine exactly how many times the loop body will be executed.

Example

x ← 0 for i ← 1 to 10 x ← x + 1

Question 3.1

What is  x  after the loop terminates?

What is   i   after the loop terminates?

 

indefinite loop - at the start of the loop, can NOT always determine exactly how many times the loop body will be executed.

Example

i ← 1 while i ≤ 4 i ← i + 1

Question 3.2

1. Count the number of executions of:     while i ≤ 4
    
2. Count the number of executions of:      i ← i + 1
    
3. What is   i  after the loop terminates?

 

pre-test or zero-trip loops - the loop body can be executed zero or more times

Example

i ← 13 while i < 10 i ← i + 1

Question 3.3 - What is   i  after the loop terminates?

 

post-test or one-trip loops - the loop body can be executed one or more times

Example

i ← 13 do i ← i + 1 while i < 10

Question 3.4 - What is   i  after the loop terminates?

 

3.1 Algorithms

Introduction

Definition

algorithm - is a finite sequence of precise instructions for performing a computation or for solving a problem   precondition - describes what must be true before an algorithm can be executed.  If the algorithm's preconditions are not met then the algorithm cannot work correctly.   postcondition - describes what will be true after the algorithm is executed, assuming preconditions are met.   contract - if the user of the algorithm satisfies the preconditions, then the algorithm guarantees to leave things in a state where the postcondition is satisfied

 

ALGORITHM 0 Division -- pre:  ∀x ∈ Z ^ x ≠ 0,   ∀y∈ Z          procedure div( y, x : integers) result ← y / x -- post: result = y / x

Example

div( 15, 3)	precondition met. y = 15 and x = 3 postcondition result = 15/3 = 5
div( 15, 0)	precondition violated. y = 15 and x = 0 postcondition result = ?

Example - max is maximum of an int array.

Loop invariant

Invariant means unchanged The loop contains an invariant which describes what remains unchanged when loop executed Permits understanding what the loop does without having to understand (at the same time) how it does it. Can reason about the loop's effect without hand tracing each loop iteration. The loop invariant is always true: before the loop,   at the end of each loop,   and after the loop completes.

Example - Proof of loop invariant - Factorial

1! = 1
2! = 1! * 2 = 2
3! = 2! * 3 = 6
4! = 3! * 4 = 24
    :
n! = (n-1)! * n

The loop invariant can be proven for small values of n by hand-tracing:

Pk = k! ^ k ≤ n

P_k = k! ^ k ≤ n is always true can be proven for any n using induction

 

Example

The loop result is the maximum of a list of numbers.

The loop invariant is:

∀k: 1 ≤ k < i, ak ≤ max

pre:  ∃a1 procedure max( a1, a2, a3, ..., an : integers) max ← a1 i ← 2 ∀k: 1 ≤ k < i, ak ≤ max while  i ≤ n if max < ai then max ← ai i ← i + 1 post: ∀j: 1 ≤ j ≤ n, aj ≤ max Question 3.7        max( { 7, 5, 19, 8 } )	i n max ai 2 4 7 1 2 3 4 7 5 19 8 3 4 7 1 2 3 4 7 5 19 8 4 4 19 1 2 3 4 7 5 19 8 5 4 19 1 2 3 4 7 5 19 8
What is n?   What does the loop invariant say in English?          ∀k: 1 ≤ k < i, ak ≤ max   Loop invariant true before the while loop?             i?      max?   Loop invariant true after one iteration of the loop?  i?      max?   Loop invariant true after the loop completes?          i?      max?

Note:

Preconditions specify conditions that must be true to ensure postconditions.

Loop invariant accomplishes the work of the max algorithm.

Postconditions specify result of loop invariant when preconditions hold.

pre:  ∃a1                                        loop invariant:   ∀k: 1 ≤ k < i, ak ≤ max post: ∀j: 1 ≤ j ≤ n, aj ≤ max

Must have at least one element in sequence. All k elements, those before i, ak ≤ max. All aj elements are ≤ max

Performance Analysis

Basic idea:

 Determine number of instructions are executed, dependent upon the problem size N.

Determine function f(N) where:

• the domain, N, is the size of the input to the algorithm
   
• N ≥ 0
   
• the range is the number of instructions executed by the algorithm
   
• range ≥ 0
   
• Therefore (since domain and range ≥ 0) this function only exists in the Quadrant I (see Figure 3: http://en.wikipedia.org/wiki/Cartesian_coordinate_system )

 

Example - sum

procedure sum( a1, a2, ..., an : integers) Maximum Executions sum ← 0 1 for i ← 1 to n N sum ← sum + ai N Sum algorithm performs 2 operations for each input and 1 operation to initialize: f(N) = 2N + 1 N = 1000 f(1000) = 2*1000 + 1 = 2001 operations

sum( { 7, 5, 19, 8 } ) i n sum ai 1 4 7 1 2 3 4 7 5 19 8 2 4 12 1 2 3 4 7 5 19 8 3 4 31 1 2 3 4 7 5 19 8 4 4 39 1 2 3 4 7 5 19 8 for loop values

 

Example - max Performance Analysis

• Simplification: start while at 1 (instead of 2 as it appears in the textbook) - makes the analysis a little simpler, and has a negligible effect on the analysis
   
• For input size N, procedure max must look through N integers to find the largest value.

procedure max( a1, a2, a3, ..., an                                            : integers)	Maximum Executions
max ← a1	1
i ← 1	1
while  i ≤ n	N+1
if max < ai	N
then max ← ai	N
i ← i + 1	N

Analysis:

1. Determine the number of times each instruction gets executed by the algorithm on input size N.
    
2. The first 2 assignment statements always execute 1 time no matter the size of N. 
    
3. The while i ≤ n executes N + 1 times, the last test terminates the while.
    
4. All the statements in the while loop body execute N times.
    
5. Create the function f(N)
    
   • total the executions

     1 + 1 + N+1 + N + N + N = 4N + 3

   • f(N) = 4N¹ + 3N⁰  = 4N + 3 
      
6. If the size of the problem N = 1000, then max algorithm will execute:

    f(1000) = 4 * 1000 + 3 = 4003 instructions.

 

Question 3.8   Give the maximum executions of each statement, in terms of a constant or N.

procedure sum(a1, a2, …, aN                : integers)	Maximum Executions
sum ← a1	a.
i ← 2	b.
while  i ≤ n	c.
sum ← sum + ai	d.
i ← i + 1	e.

Question 3.9   What is f(N), the total of executions for problem size N?

 

 

Example using flowcharts

Flowchart Diagram of max

• Shapes Used
  • Oval - marks the beginning and end of the algorithm.  Do not count these as executable statements.
  • Rectangle - marks executable statements that have one way out of the statement, and no condition is being tested and therefore no decision is being made.
  • Diamond - marks executable statements that have multiple (often 2) ways out.  A condition is being tested, and a decision is being made.
• Loop Present
  • If a loop is present in the code, then at least one of the control-flow arrows will be pointed up in the diagram in order to get flow of control back to a previously executed statement.
  • Circuit - the technical term used to indicate that there is a loop in a control-flow diagram

   

• procedure max( a1, a2, a3, ..., an : integers) max := a1 i := 2 while  i ≤ n if max ≤ ai then max := ai i := i + 1

 

• Simplification: start while at 1 (instead of 2 as it appears in the textbook) - makes the analysis a little simpler, and has a negligible effect on the analysis
   
• Let the size of the input be N, i.e., procedure max must look through N integers to find the largest value.

Analysis:

1. Determine the number of times each diamond and each rectangle gets executed by the algorithm on input size N.
    
2. The first 2 assignment statements always execute 1 time no matter the size of N.  That is noted in the diagram by the
    
3. The while i ≤ n test gets executed N + 1 times
    
4. All the statements in the while loop body get executed N times
    
5. Create the function f(N)
   • add up all the numbers '1' - there are 3
      
   • add up all the Ns - there are 4
      
   • f(N) = 4N¹ + 3N⁰  = 4N + 3 
      
6. If the size of the problem N = 1000, then max algorithm will execute:

    f(1000) = 4 * 1000 + 3 = 4003 instructions.

 

Algorithm Properties

Input Output Definiteness Correctness Finiteness Effectiveness Generality (abstract)

 

Searching Algorithms

Linear search

Searches for a given value in an unsorted list of numbers.

Returns location where value found or 0 otherwise.

Example - Successful search

procedure linear search (x: integer, a1, a2, ..., an: integers) Question  3.10              linear search( 13, { 7, 2, 13, 19, 5 } ) What are:                         x              n             a1   Is precondition met?       At the end of execution, what is location?   At the end of execution is postcondition met?    post: ∀j: 1 ≤ j ≤ n, aj ≠ x → location = 0  XOR ∃k: 1 ≤ k ≤ n, ak = x → location = k Remember XOR means only one proposition can be true.

Example - Unsuccessful search

procedure linear search (x: integer, a1, a2, ..., an: integers) Question 3.11     linear search( 10, { 7, 2, 11 } ) What are:                         x              n             a1   Is precondition met?       At the end of execution, what is location?   At the end of execution is postcondition met?    post: ∀j: 1 ≤ j ≤ n, aj ≠ x → location = 0  XOR ∃k: 1 ≤ k ≤ n, ak = x → location = k Remember XOR means only one proposition can be true.

a b a XOR b F F F F T T T F T T T T

Performance Analysis

Worst case: ∀j: 1 ≤ j ≤ n, a_j ≠ x → location = 0

1.	procedure linear search (x: integer, a1, a2, ..., an)	Maximum Executions
2.	i ← 1	1
3.	while (i ≤ n and x ≠ ai)	N+1
4.	i ← i + 1	N
5.	if i ≤ n then	1
6.	location ← i	1
7.	else	1
8.	location ← 0	1

Question 3.12   

1. Are lines 6 and 8 both executed?
    
2. What is f(N)?
    
3. When does the best case (fewest instructions executed) occur?
    
4. What instructions are executed in the best case?
    
5. What is f(N) for those instructions, the best case?

 

Note:

• Requires a Loop: Since the input to procedure linear search can be up to n items, linear search requires a loop in order to process all n of the items.
   
• Indefinite Loop: We need to use an indefinite loop (e.g., 'while') because the loop is searching for the first a_i (in the input) whose value is equal to the value stored in x.  Since that value might be stored in any of the a_i it is possible that the loop body only needs to be executed one time, (if x = a₁), the 'while' makes it so we can exit the loop early, without examining all n items.  Thus possibly saving time.
   
• Two Ways to Exit Loop:
  • Can exit loop when (i ≤ n) evaluates to false, in this case i will be equal to n + 1, and linear search as examined all n items and NOT found what it was looking for.
  • Can exit loop when (x ≠ a_i) evaluates to false, in this case x = a_i and linear search has found what it was looking for.

Binary search

Searches for a given value in a sorted list of numbers.

Returns location where value found or 0 otherwise.

Reduces the search time by dividing the search space in half each iteration.

Question 3.13   

binary search( 49, { 10, 16, 27, 38, 49, 53, 76, 82 } )

1. Is precondition met?

pre: ∃x ^ ∃a₁ ^ ∀j: 2 ≤ j ≤ n, a_j-1 < a_j        

pre: 49 ^ (10<16<27<38<49<53<76<82)

2. Is postcondition met?

post: ∀i: 1 ≤ i ≤ n, a_i ≠ x → loc = 0
         XOR ∃k: 1 ≤ k ≤ n, a_k = x → loc = k

 

Example - when binary search fails.

There are 16 = 2⁴  entries to search.

Requires 4 divisions to reduce size 16 search to size 1.

binary search( 100, { 10, 16, 27, 38, 49, 53, 76, 82, 85, 91, 98, 101, 112, 124, 135, 143 } )

 

Performance Analysis

• The while dominates the execution so will be the focus of the analysis.

  • while l < r    m ← ⌊(l + r) / 2⌋    if x > am then            l ← m + 1    else            r ← m

• Binary search reduces the search space by one half each while iteration.
   
• The number of iterations of

N ← N/2

until N = 1 is the worst-case performance.

Example

N ← 16 while N > 1 N ← N / 2

N ← 16/2 = 8 N ← 8/2 = 4 N ← 4/2 = 2 N ← 2/2 = 1

• 16/16 = 16/2⁴ = 1
   
• implies a k such that

  N/2^k = 1

  k is the number of divisions (iterations) until N = 1.

N/2^k = 1

N = 2^k

log₂ N = log₂ 2^k = k                            Example: log₂ 2⁵ = 5

k = log₂ N                                           Number divisions

• f(N) is dominated and therefore defined by the number of while iterations, k.
   
• f(N) = k = log₂ N

f(1024) = log₂ 1024 = log₂ 2¹⁰ = 10

Binary search (from the more accurate analysis above):

f(N) = 6 log₂ N + 7

f(1024) = 6 log₂ 1024 + 7 = 6 log₂ 2¹⁰ + 7 = 6*10 + 7 = 67

Linear search:

f(N) = 2N + 6

f(1024) = 2 * 1024 + 6 = 2054

Nested loops

Nesting two loops often produces quadratic execution.

A simplified analysis assumes the for statement is executed one time for each iteration.

Example

procedure print (integer n ≥ 0)	Maximum Executions
for i ← 1 to n	N
for j ← 1 to n	N * N
write( i, j )	N * N

f(N) = 2N² + N

 

Nesting three loops often produces cubic execution.

Example

procedure print (integer n ≥ 0)	Maximum Executions
for i ← 1 to n	N
for j ← 1 to n	N * N
for k ← 1 to n	N * N * N
write( i, j, k )	N * N * N

f(N) = 2N³ + N² + N

 

Question 3.14    What would be a good guess analysis for four nested loops, f(N)?

 

Sorting

ALGORITHM 4 Bubble Sort -- pre: a1, a2, ..., an ∈ R and  n ≥ 2 procedure bubble sort (a1, a2, ..., an: real numbers with n ≥ 2) -- loop invariant:  ∀k: 1 ≤ k < i, an-k-1 ≤ an-k          Sorted below index i for i ← 1 to n-1     -- loop invariant:  ∀m: 1 ≤ m < j, am ≤ aj+1        Sorted below index i     for j ← 1 to n-i       if aj > aj+1 then interchange aj and aj+1 -- post: ∀j: 2 ≤ j ≤ n, aj-1 ≤ aj                                        Sorted ascending order

Example

bubble sort( {3, 2, 4, 1, 5} )

First pass places maximum of n values at sequence end. Second pass places maximum of remaining n-1 values.

 

Inner loop invariant is: each m element of sequence is less than or equal to the j+1 element of sequence.

Initial sequence:  {3, 2, 4, 1, 5}

∀m: 1 ≤ m < j, am ≤ aj+1

Before inner loop:                {3, 2, 4, 1, 5}

At end of inner loop for j=1: {2, 3, 4, 1, 5}

At end of inner loop for j=2: {2, 3, 4, 1, 5}

At end of inner loop for j=3: {2, 3, 1, 4, 5}

At end of inner loop for j=4: {2, 3, 1, 4, 5}

Outer loop invariant is: the last i+1 elements of sequence are sorted and are all greater than or equal to the other elements of sequence. When i=1, the last two elements are sorted, i=2, the last three elements are sorted.

Initial sequence:  {3, 2, 4, 1, 5}

∀k: 1 ≤ k < i, an-k-1 ≤ an-k

Underlined numbers sorted at end of outer loop for i=1:    {2, 3, 1, 4, 5}

Underlined numbers sorted at end of outer loop for i=2:    {2, 1, 3, 4, 5}

Underlined numbers sorted at end of outer loop for i=3:    {1, 2, 3, 4, 5}

Underlined numbers sorted at end of outer loop for i=4:    {1, 2, 3, 4, 5}

 

Performance Analysis

procedure bubble sort (a1, a2, ..., an:                                real numbers with n ≥ 2	Maximum Executions
for i ← 1 to n-1	N-1
for j ← 1 to n - i	(N-1)(N-i)
if aj > aj+1 then interchange aj and aj+1	(N-1)(N-i) or    n-1 + n-2 + ... + 2 + 1             (n - 1)n / 2

In this case, listing the execution number directly is not so easy.

However, observe the if is executed one fewer times in each iteration of

for j ← 1 to n-i

Sum of all the if executions is then:

(n-1) + (n-2) + (n-3) + ... + 2 + 1 =   (n-1)*n /2 = (n² - n) / 2

See table below for closed form.

Quadratic function for if executions.

f(N) = (N2 - N) / 2

f(1000) = (1000² - 1000) / 2 = (1,000,000 - 1000) / 2 = 999,000 / 2

Bubble sort:

f(N) = 2 * (N2 - N) / 2 + N - 1 = N2 - 1

f(1000) = 1000² - 1 = 999,999

 

Greedy Algorithms

• optimization problems - the goal when solving such problems is to find a solution to the given problem that either minimizes or maximizes the value of some parameter
   
• greedy algorithms - algorithms that make what seems to be the "best" choice at each step while computing the solution
   
• example - the Change making algorithm is a greedy algorithm that minimizes the number of coins used in making change for some value n (when given choices for change that includes quarters, dimes, nickels and pennies)
   
• Greedy because uses the largest available coin first.

Example

change( { 25, 10, 5, 1 },  66)

i r n change ci ? 4 66 ∅ 1 2 3 4 25 10 5 1 1 4 41 {25} 1 2 3 4 25 10 5 1 1 4 16 {25, 25} 1 2 3 4 25 10 5 1 2 4 6 {25, 25, 10} 1 2 3 4 25 10 5 1 3 4 1 {25, 25, 10, 5} 1 2 3 4 25 10 5 1 4 4 0 {25, 25, 10, 5, 1} 1 2 3 4 25 10 5 1

ALGORITHM 6 Greedy Change Making Algorithm -- pre: c1 > c2 > ... > cr  and  n > 0 -- post: 'change' contains the least number of coins that add up to 'n'   procedure change (c1, c2, ..., cr: values of denominations of coins; n: integer) for i ← 1 to r    while n >= ci       add a coin with value ci to change       n ← n - ci

Question 3.15

Estimate the best-case performance.

Estimate the worst-case performance.

 

Note:

• Requires Two Loops:
  • Outer Loop - Since the input to procedure change can be up to r different coin denominations, change requires a definite loop ('for') in order if each of the denominations of coin can be used to make change.
     
  • Inner Loop - change requires that the inner loop be an indefinite loop ('while') since more than one coin of the same denomination can be used to make the change (e.g., 2 dimes), and this number of coins is not known ahead of time (the indefinite part).

3.2 The Growth of Functions

 

x x+3 2x 1 4 2 2 5 4 3 6 6 4 7 8 5 8 10 6 9 12 7 10 14 8

Question 3.16.1

1. At x = 8, what are the values of x+3 and 2x?
    
2. Do the graphs ever intersect for x+3 and x?
    
3. At what x is the intersection of graphs for 2x and x+3?
    
4. x+3 ≤ 2x after some x?
    

 

Introduction

It is important to compare the efficiency of one algorithm against another.

A linear search algorithm examines every name to determine that someone is not in a list. Adding another 1,000 names increases the search time by a factor of 1,000. We say that the run time grows linearly, by 1000, with the size of the problem. If each name required 0.001 seconds, the 1000 names would add 1 second. Perhaps not a big deal. We would say the growth is n.

Adding 1000 names to a poorly written sort algorithm might increase the run time by 1000² = 1,000,000. If each name required 0.001 seconds, the 1000 names would add 1,000,000*0.001s = 1000 seconds (or over 16 minutes). A big deal! We say that the run time grows by the square, by 1000², with the size of the problem. We would say the growth is n².

Below are some common growth functions where n, the problem size, is the horizontal axis.

log2 n	n	n2	2n	n!	nn
log2 10	10	102	210	10!	1010
3.321928	10	100	1024	3628800	10000000000

 

Big-O notation estimates the number of operations needed to solve a problem. Functions used in these estimates often include those at left. x-axis - size of the problem being solved by some algorithm   y-axis - number of instructions executed by the algorithm when solving the problem   The analysis is always in Quadrant I because: algorithms are not written to solve problems of size zero or of negative size algorithms cannot solve anything by executing zero or a negative number of instructions   Note that for n > 4, the following relationship holds: 1 < log n < n < n log n < n2 < 2n < n!

 

 

Big-O Notation

Defines the upper-bound of complexity (i.e. the worst-case).

Definition 1

f(x) is O( g(x) ) if there are constants C and k such that f(x)    ≤  C  g(x)     ∀x ≥ k

Note that x is the size of the problem.

x ≥ k implies that for any x size problem, the worst performance is O( g(x) ).

For an algorithm, determine its worst or upper-bounds performance.

O( g(x) ) is the upper-bounds of that performance.

 

Example

f(x)  ≤  C g(x)     ∀x ≥ k

f(x) = x + 3

g(x) = x

x + 3  ≤  2x,    ∀x ≥ k = 3

C = 2

k = 3

f(x) is O( x ) x+3 is O( x )

x + 3  ≤  2x ∀x ≥ 3

x x+3 2x 1 4 2 2 5 4 3 6 6 4 7 8 5 8 10 6 9 12 7 10 14

Question 3.16.2    Complete the table and graph

x 2x+2 3x 0     1     2     3     4     5

2x+2 ≤ 3x after what x?   Which function dominates the other?

 

Example

f(x)  ≤  C g(x)     ∀x ≥ k

f(x) = x

g(x) = x²

C = 1

k = 1

     x  ≤  1 x²,   ∀x ≥ k = 1

f(x) is O(x2)

Says the graph of Cx² must be above x after some k.

x x2 1 1 2 4 3 9 4 16 5 25 6 36 7 49

f(x)  ≤  C g(x)     ∀x ≥ k

 

Example - functions in O( n² )

log n     n       n/1000        n^1.999       n²        n²+n        1000n²+50n

n2 ≤ n2,    ∀n ≥ 0 n ≤ n2,    ∀n ≥ 0 n1.999  ≤  n2,    ∀n ≥ 0

n n1.999 n2 0 0 0 1 1 1 2 3.99 4 3 8.99 9 4 15.97 16 5 24.95 25

Example - functions not in O(n²)

n!       n³        n^2.1        2ⁿ

n!  >  n2,   ∀n ≥ 3 2n  >  n2,   ∀n ≥ 4

n n! 2n n2 0 1 1 0 1 1 2 1 2 2 4 4 3 6 8 9 4 24 16 16 5 120 32 25 6 720 64 36 7 5040 128 49

 

f(x)  ≤  C g(x)     ∀x ≥ k

Question 3.17    Which of these functions are O( n )?

1. f(n) = 20n+56
    
2. f(n) = n/4
    
3. f(n) = n2
    
4. f(n) = n log n
    

Mathematics Proof Approach to Finding C and k

Example - Find C

x/2	≤	C x
x/2x	≤	C
1/2	≤	C
C	≥	1/2
C	=	1/2

Question 3.18.1 - Find C

5x	≤	C x
C	=	?

Question 3.18.2

What are the values of 1/n?

n	1/n
1
2
100
∞

Which n gives maximum 1/n?

Example - Find C

4x+2	≤	C x
4x/x + 2/x	≤	C
4 + 2/x	≤	C	2/x maximum at x=1
4 + 2/1	≤	C
C	≥	6
C	=	6

Question 3.18.3 - Find C

2x + 3	≤	C x
C	=	?

 

Question 3.18.4 - Find C

2x	≤	C x2
C	=	?

 

Example - Finding C and k

f(x)  ≤  C g(x)     ∀x ≥ k

f(x) = x + 5

g(x) = x

x+5 is O( x )

Must find:

x + 5  ≤  Cx    ∀x ≥ k

The graph of Cx should be above x + 5 after some k value.

C and k should be the smallest values possible to provide the most accurate measure.

C = 1 is too small, the graph of 1*x is always below x + 5.

C = 2 is equal or above x + 5 from x = 5 on.

x + 5  ≤  2x,    ∀x ≥ 5

C = 2, k = 5, satisfies O( x )

x+5  ≤  2 x     ∀x ≥ 5

x + 5 is O(x)

x x+5 2x 1 6 2 2 7 4 3 8 6 4 9 8 5 10 10 6 11 12 7 12 14 8 13 16 9 14 18 10 15 20

C and k can be other values, as long as:

f(x)  ≤  C g(x)     ∀x ≥ k

C = 8/3, k = 3 satisfies Big-O

     x + 5  ≤  8/3 x,   ∀x ≥ 3

x x+5 8/3 x 1 6 2.67 2 7 5.33 3 8 8.00 4 9 10.67 5 10 13.33 6 11 16.00 7 12 18.67 8 13 21.33 9 14 24.00 10 15 26.67

 

Find C and k mathematically

f(x)  ≤  C g(x)     ∀x ≥ k

f(x) = x + 5

g(x) = x

Show:    x+5 is O(x)

Must find:

x + 5  ≤  Cx    ∀x ≥ k

C the constant

k the value for x ≥ k

Use algebra to solve the following inequality for constant C

f(x)  ≤  C g(x)    ∀x ≥ k

 

f(x) ≤ C * g(x)	From definition of Big-O
x+5  ≤ C x	Substitute: f(x) = x+5 and g(x) = x
x/x + 5/x  ≤  C x/x	divide both sides by x
1 + 5/x  ≤  C	1 + 5/x greatest when x = 1
1 + 5/1  ≤  C	Find smallest C for 1 + 5/x  ≤  C
6  ≤  C	Can pick C = 6 or 1 + 5/x  ≤  6
C = 6
	Find k when C = 6
1 + 5/x ≤ C
1 + 5/k ≤ 6	Substitute C and k
5/k ≤ 5
1/k ≤ 1
1 ≤ k	Can pick k = 1
C = 6, k=1 1 + 5/k ≤ 6	Satisfies f(x) ≤ C * g(x) x + 5 ≤ 6 x, x ≥ 1

Question 3.19    Find C and k to show x+2 is O(x)

f(x) = x+2                    g(x) = x

x+2  ≤  C x       ∀x ≥ k

 

Example

Suppose execution is:

f(N) = 2N + 6

Show:    2n + 6 is O(n)

Solution:

f(n) = 2n + 6

g(n) = n

Must show:    2n + 6 ≤ C n

C the constant

k the value for n ≥ k

Use algebra to solve the following inequality for constant C

f(n)  ≤  C g(n)    ∀n ≥ k

f(n) ≤ C * g(n)	From definition of Big-O
2n + 6  ≤ C n	substitute: f(n) = 2n + 6 and g(n) = n
2 + 6/n  ≤  C	divide both sides by n
2 + 6/1  ≤  C	6/n is maximum when n=1
8  ≤  C
C = 8 2n + 6  ≤ C n 2k + 6 ≤ 8k  6 ≤ 6k  1 ≤ k	Find k when C = 8 Substitute k for n     k = 1
C = 8, k=1 2n + 6 ≤ 8n, n ≥ 1	Satisfies f(n) ≤ C * g(n) 2n + 6 ≤ C n, n ≥ k

Graph illustrates 8n is upper-bound of 2n + 6

2n + 6 is O(n)

2n + 6 ≤ 8n, n ≥ 1

n 2n + 6 8n 0 6 0 1 8 8 2 10 16 3 12 24 4 14 32 5 16 40 6 18 48 7 20 56 8 22 64 9 24 72

Question 3.20    Find C and k to show 5n+2 is O(n)

f(n) = 5n+2             g(n) = n

5n+2  ≤  C n       ∀n ≥ k

 

Example

f(x)  ≤  C g(x)     ∀x ≥ k

Show:    x² + 2x + 1 is O( x² )

Solution:

Must show:    x² + 2x + 1 ≤ C x²

f(x) = x² + 2x + 1

g(x) = x²

Need to determine

C the constant

k the value for x ≥ k

Use algebra to solve the following inequality for constant C

f(x) ≤ C * g(x)

f(x) ≤ C * g(x)	Big-O definition
x2 + 2x + 1 ≤ C x2	Substitute: f(x) = x2 + 2x + 1 and g(x) = x2
1 + 2/x + 1/x2 ≤ C	divide both sides by x2
1 + 2/1 + 1/12 ≤ C	maximum at x=1
4 ≤ C

Know x > 0

• Since x is the size of the problem to be solved by an algorithm, x cannot be negative.
• Also, it is not often (if ever) that a problem size is zero.
• So x can only be larger than 0.

Find C = 4

1 + 2/x + 1/x2 ≤  C

As x grows larger,

2/x and 1/x² grow smaller

Maximum when x = 1

1 + 2/1 + 1/1² = 4 ≤ 4

Find k = 1

1 + 2/x + 1/x2 ≤ 4	C=4
1 + 2/k + 1/k2 ≤ 4	Substitute k
1 + 2/1 + 1/12 ≤ 4	Maximum when k = 1
4 ≤ 4	Pick k = 1
1 + 2/2 + 1/22 ≤ 4 3 1/4 ≤ 4	Or pick k = 2

The constants C=4 and k=1

x² + 2x + 1 ≤ 4x²   ∀x ≥ k
 

In Big-O terms,  f(x) is O(x²)

Means what?

x² + 2x + 1 ≤ 4x² for ∀x ≥ 1

The chart below indicates:

x² + 2x + 1 ≤ 4x² for ∀x ≥ 1            not worst than 4x²

x² + 2x + 1 ≥ x² for ∀x ≥ 1              worse than x²

x x2 + 2x + 1 4x2 x2 1 4 4 1 2 9 16 4 3 16 36 9 4 25 64 16 5 36 100 25 6 49 144 36 7 64 196 49 8 81 256 64 9 100 324 81

 

Example:               7x² is O(x³)

Show: 7x² ≤ C x³       ∀x ≥ k

f(x) = 7x²                             f(x) ≤ C * g(x)

g(x) = x³

Determine

C the constant

k the value for x ≥ k

Find C = 7

f(x) ≤ C * g(x)	Big-O definition
7x2 ≤ C x3	substitute: f(x) = 7x2 and g(x) = x3
7/x ≤  C	divide both sides by x3
7/x ≤  C	7/x maximum when x=1
7/1 ≤ C = 7

Find k = 1

7/x ≤ C
7/k ≤ 7	Substitute k
7 ≤ 7k
1 ≤ k	Pick k = 1

Constants C=7 and k=1

7x² ≤ 7x³   ∀x ≥ k

In Big-O terms,  f(x) is O(x³)

Means what?

7x² ≤ 7x³     ∀x ≥ 1

x 7x2 x3 7x3 1 7 1 7 2 28 8 56 3 63 27 189 4 112 64 448 5 175 125 875 6 252 216 1512 7 343 343 2401 8 448 512 3584 9 567 729 5103

Note above also that:

7x² ≤ x³ for x ≥ 7

C=1, k=7

Question 3.21    Find C and k to show 2n² + 3n is  O(n²):

f(n) = 2n² + 3n

g(n) = n²

f(x)  ≤  C g(x)     ∀x ≥ k

 

Example     x² is not O(x)

For x² is O(x) must show:

x² ≤ Cx for ∀x ≥ k

f(x) = x²

g(x) = x

Need to determine

C the constant

k the value for x ≥ k

f(x) ≤ C * g(x)	Big-O definition
x2 ≤ C x	substitute: f(x) =  x2 and g(x) = x
x ≤ C	divide both sides by x

Know x > 0

• As x grows larger, x grows larger.

No matter how large constant C or k, cannot pick a constant C or k such that

x² ≤ Cx for ∀x ≥ k

x x2 1 1 2 4 3 9 4 16 5 25 6 36 7 49

Question 3.22    Try to find C and k to show 2n² + 3n is not O(n):

f(n) = 2n² + 3n

g(n) = n

f(x)  ≤  C g(x)     ∀x ≥ k

 

 

Some Important Big-O Results

 

THEOREM 1

f(x) = anxn + an-1xn-1 +...+ a1x1 + a0 then f(x) is O(xn)

Example

f(x) = 4x² + 2x + 1   
 

Steps to simplifying a function by Theorem 1

1. Drop lower order terms

   4x² + 2x + 1 drop: 2x + 1

   4x² remains

2. Change constant coefficient of highest order term to 1

   4x² becomes x²

3. Take what remains, wrap in parenthesis and put a upper case O in front:

   x² becomes O(x²)

4. Can say: f(x) is O(x²)

 

Example

Use Big-O to estimate the sum of the first n positive integers.

For n=5:   

1+2+3+4+5 = 15 ≤ 5 + 5 + 5 + 5 + 5 = 5² = 25

1 + 2 + ... + n ≤ n + n + ... + n = 1n²

Because the sum of n positive integers is less than n², implies the sum is O(n²) for C=1 and n>k=1.

 

Example

Use Big-O to estimate n!.

5! = 1 * 2 * 3 * 4 * 5 = 120 ≤ 5 * 5 * 5 * 5 * 5 = 5⁵ = 3125

n! = 1 * 2 *... * n ≤ n * n * ... * n = 1nⁿ

Because n! is less than nⁿ, implies the sum is O(nⁿ) for C = 1 and n ≥ k = 1.

Question 3.22.1    What is the Big-O?

1. 3000n
    
2. 4n² + n
    
3. 1/2 n³ + n² + 5
    
4. n log n + 5

 

The Growth of Combinations of Functions

Many algorithms are combinations of other algorithms.

Example

A( x ) run time is sum of B( x ) and C( x ) run times.

B(x) take 5 seconds

C(x) takes 10 seconds

A(x) takes B(x) + C(x) = 15 seconds, plus the div operation time.

procedure A( x ) result ← B( x ) div C( x )

Suppose:

B(n) is O( n² )

C(n) is O( 2ⁿ )

A( n ) is O( 2ⁿ ) because Big-O notation is a measure of the worse or:

max( |B(n)|, |C(n)|) = max( n², 2ⁿ ) = 2ⁿ

Suppose:

B(n) is O( n⁴ )

C(n) is O( n! )

A( n ) is O( n! )

max( |B(n)|, |C(n)|) = max( n⁴, n! ) = n!

n n^4 n! 1 1 1 2 16 2 3 81 6 4 256 24 5 625 120 6 1296 720 7 2401 5040 8 4096 40320

THEOREM 2

If f1(x) is O(g1(x)) f2(x) is O(g2(x)) then (f1+f2)(x) is O( max( |g1(x)|, |g2(x)|) )

THEOREM 3

If f1(x) is O(g1(x)) f2(x) is O(g2(x)) then (f1* f2)(x) is O( g1(x) * g2(x) )

Example

Suppose

f₁(x) = 4x² which is O( x² )

f₂(x) = 6x³ which is O( x³ )

By Theorem 3

(f₁* f₂)(x) is O( g₁(x) * g₂(x) )

4x² * 6x³ is O( x² * x³ ) = O( x⁵ )

 

Big-Omega and Big-Theta Notation

Big-O gives upper-bound (worst-case).

Big-Omega, Ω, gives lower-bound (best-case), cannot do better, can do worse.

Big-Theta, Θ, gives upper and lower-bound.

 

Definition 1 - Big O  simplified from text version

f(x) is O(g(x)) if there are constants C and k such that f(x) ≤  C g(x)    ∀x ≥ k

Example - functions in O(n)

n       n/1000         log n       1000n         ^v n

Example - functions in O(n²)

n           n/1000      n^1.999       n²        n log n     

n²+n     1000n²+50n       ^v n

Example - functions not in O(n²)

n^2.1       n³        2ⁿ           nⁿ

 

Definition 2 - Big-Omega simplified from text version

f(x) is Ω(g(x)) if there are constants C and k such that   C g(x) ≤ f(x)    ∀x ≥ k

Functions in Ω(n) - will always be equal or above Cn after some point.

n      n/1000      n^1.999      n²      n²+n      1000n²+50n

Functions not in Ω(n²) - will not always be equal or above Cn² after some point.

n      n^{1.999      v} n

x² is O(x³)         f(x) ≤ C g(x)    ∀x ≥ k

x³ is Ω(x²)        C g(x) ≤ f(x)    ∀x ≥ k

x x2 x3 1 1 1 2 4 8 3 9 27 4 16 64 5 25 125 6 36 216 7 49 343 8 64 512 9 81 729

Question 3.23    Which functions are Ω( n² )?

Will always be equal or above some C*n² after some point.

C * n²  ≤   f( n )

1. n³
    
2. n+5
    
3. n² + 5

 

Mathematics Proof Approach to Finding C and k

f(x) is Ω(g(x))   C g(x)  ≤  f(x)    ∀x ≥ k

Example         2n = Ω(n)

Find C = 2

C * g(x)  ≤ f(x)	From definition
C n   ≤  2n	substitute: f(x) = 2n and g(x) = n
C  ≤ 2	divide both sides by n

Find k = 0

C n   ≤  2n
2 k   ≤  2 k	Substitute k and C
k  ≤ k	Can pick any k ≥ 1 Pick k = 1

Constants C = 2 and k = 1

2n  ≤  2n,  ∀n ≥ 1

In Big-Omega terms,  f(n) is Ω(n)

 

Example        x³ = Ω(x²) 

C * g(x)  ≤ f(x)	From definition
C x2  ≤ x3	substitute: f(x) = x3 and g(x) = x2
C  ≤ x	divide both sides by x2

Find C = 1

Know x > 0

C  ≤ x

As x grows larger, x grows larger. Minimum when x = 1.

Pick C = 1,

1  ≤  x

Find k = 1

C  ≤  x
1  ≤  k	Substitute k and C
	Pick k = 1

Constants C = 1 and k = 1

1 * x²  ≤  x³,  ∀x ≥ 1
 

In Big-Omega terms,  x³ is Ω(x²)

x x2 x3 1 1 1 2 4 8 3 9 27 4 16 64 5 25 125 6 36 216 7 49 343 8 64 512 9 81 729

f(x) is Ω(g(x))   C g(x)  ≤ f(x)    ∀x ≥ k

Question 3.23.1

   Is x² + 2x + 1 = Ω(x²)?

 

Example         x² + 2x + 1 is Ω(x²)

 Show:    C x²  ≤ x² + 2x + 1

f(x) = x² + 2x + 1

g(x) = x²

Determine

C the constant

k the value for x > k

C * g(x)  ≤ f(x)	From definition of Ω
C x2  ≤ x2 + 2x + 1	substitute: f(x) = x2 + 2x + 1 and g(x) = x2
C  ≤ 1 + 2/x + 1/x2	divide both sides by x2

C  ≤ 1 + 2/x + 1/x²,  ∀x ≥ k     must hold

Find C = 1

Know x > 0

2/x + 1/x² approaches 0 as x approaches ∞

1 + 2/x + 1/x² approaches 1 as x approaches ∞

1 + 2/∞ + 1/∞²  = 1

C  ≤ 1 = 1 + 2/∞ + 1/∞²

Pick C = 1

Find k = 1

C  ≤  1 + 2/x + 1/x2	∀x ≥ k
1 ≤  1 + 2/k + 1/k2	Substitute k and C
1 ≤  1 + 2/1 + 1/12 = 4	Maximum of 4 when k = 1 Decreases to 1 as k increases.
	Pick k = 1

For constants C = 1 and k=1

1 * x²  ≤ x² + 2x + 1    for all x ≥ 1
 

In Big-Omega terms,  x² + 2x + 1  is Ω(x²)

So what?

x²  ≤  x² + 2x + 1  for ∀x ≥ 1

x x2 + 2x + 1 x2 4x2 1 4 1 4 2 9 4 16 3 16 9 36 4 25 16 64 5 36 25 100 6 49 36 144 7 64 49 196 8 81 64 256 9 100 81 324

f(x) is Ω(g(x))   C g(x)  ≤ f(x)    ∀x ≥ k

Question 3.23.2   Find C and k to show: 2n² + 5n is  Ω( n² )

 

Definition 3 - Big-Theta

f(x) is Θ(g(x)) iff f(x) is O(g(x) ) and Ω(g(x))

Example functions Θ(n)

5      n      2n+5

Example functions not Θ(n)

1/n      n²      log n

Question 3.24.1    Which functions are O( n² )?                 f(x) ≤  C g(x)      ∀x ≥ k

1. n³
    
2. n+5
    
3. n² + 5

Question 3.24.2    Which functions are Ω( n² )?                C g(x)  ≤  f(x)    ∀x ≥ k

1. n³
    
2. n+5
    
3. n² + 5

Question 3.24.3    Which functions are Θ( n² )?

1. n³
    
2. n+5
    
3. n² + 5

 

Example

We have shown that:

x² + 2x + 1 ≤ 4x²      for ∀x ≥ 1 or O( x² )

x²  ≤  x² + 2x + 1      for ∀x ≥ 1, or Ω( x² )

In Big-Theta terms,  x² + 2x + 1 is Θ(x²)

x²  ≤  x² + 2x + 1 ≤ 4x²         for ∀x ≥ 1

As the graph below illustrates, x² + 2x + 1, is between 4x² and x², ∀x ≥ 1

x x2 + 2x + 1 x2 4x2 1 4 1 4 2 9 4 16 3 16 9 36 4 25 16 64 5 36 25 100 6 49 36 144 7 64 49 196 8 81 64 256 9 100 81 324

3.3 Complexity of Algorithms

Introduction

Definition

Computational complexity is a measure of the efficiency of an algorithm in memory space or execution time.

Time Complexity

Generally not actual wall-clock time but the number of operations executed.

Can then compare algorithms whether executing on a fast computer or slow computer.

O(n!) is very bad no matter how fast the computer.

Example

Describe the time complexity of Algorithm 1 for Finding the Maximum Element in a Finite Sequence.

procedure max( a1, a2, a3, ..., an )	Executions
max ← a1	1
i ← 2	1
while  i ≤ n	n
if max < ai then max ← ai	n-1
i ← i + 1	n-1

Will only consider number of comparisons:

while  i ≤ n                                                n comparisons

if max < a_i then max ← a_i                       n-1 comparisons

There are 2n - 1 comparisons.

2n - 1 is O( n )

2n - 1 ≤ Cn

2 - 1/n ≤ C        1/n decreases to 0 as n increases, 2 - 1/n maximum at n =∞

2 - 1/∞ ≤ C

2 - 0 ≤ C

2 ≤ C

C = 2, k=1        2 - 1/n ≤ 2, ∀n ≥ 1

2n - 1 ≤ 2n        ∀n ≥ k

2n - 1 is Ω( n )

Cn  ≤  2n - 1

C ≤  2 - 1/n         1/n decreases to 0 as n increases, 2 - 1/n minimum at n=1

C ≤  2 - 1/1

C ≤  1

C = 1, k=1           1 ≤ 2 - 1/n, ∀n ≥ 1

n  ≤  2n - 1           ∀n ≥ k

∴2n - 1 is Θ(n)

n  ≤  2n - 1 ≤ 2n

n 2n-1 2n 1 1 2 2 3 4 3 5 6 4 7 8 5 9 10 6 11 12 7 13 14 8 15 16 9 17 18

Example

Describe the worst-case time complexity of the Linear Search Algorithm

procedure linear search (x: integer, a1, a2, ..., an)	Comparisons	Assignments
i ← 1		1
while (i ≤ n and x ≠ ai)	2n
i ← i + 1		n+1
if i ≤ n then	1
location ← i		1
else
location ← 0		1

There are 2n + 1 comparisons.

The comparison counts are the worst-case, when x ≠ a_i

2n + 1 is O(n)

The best-case is when x = a₁ for 3 comparisons.

 

Example

Describe the average-case time complexity of the Linear Search Algorithm, assuming x is in the list.

Basic idea is that on average, x is found after searching 1/2 the items in the list.

x =  a₁ requires 3 comparisons

x =  a₂ requires 5 comparisons

:

x =  a_n requires 2n+1 comparisons

On average:

(3+5+...+n)/n

= ( 2(1+2+...+n) + n ) / n

= ( 2(n(n+1)/2) + n ) / n                By Table 2

= ( n(n+1) + n ) / n

= (n+1) + 1 = n + 2

The average-case number of executions is n + 2 when x = a_i

n + 2 is Θ(n)

 

Example - What is the worst-case complexity of the bubble sort in terms of the number of comparisons?

procedure bubble sort (a1, a2, ..., an)	Comparisons
for i ← 1 to n-1
for j ← 1 to n-i
if aj > aj+1 then interchange aj and aj+1	n-1+ n-2+ ... + 2 + 1      (n - 1)n / 2

The worst-case number of executions is (n - 1)n / 2

(n - 1)n / 2 = (n² - n) / 2 is Θ(n²)

 

Understanding the Complexity of Algorithms

 

Definitions

Tractable means the algorithm is polynomial complexity. e.g. Θ( n5 )

Intractable means the algorithm is worst than polynomial complexity. e.g. O( n! )

 

Unsolvable means the algorithm cannot be solved. Not only that there is no known solution but there is no solution possible. e.g. Whether an algorithm will halt.

 

The table above assumes a processor executes one operation in 10^-7s. or 1/10,000,000 s.

Recall that the bubble sort is O(n²).

How long to sort n=10⁶ items, according to the above table?

How long to sort n=10² items, according to the above table?

How long to sort n=10² items, if bubble sort is O(2ⁿ) according to the above table?

 

 

3.4 The Integers and Division

Definition 2

mod yields the remainder of division. div yields the quotient of division.

Example

17 mod 5 = 2

17 div 5 = 3

-1 div 5 = 0

-1 mod 5 = 4

 

Definition 3

a is congruent to b modulo m means m divides a-b. a≡ b mod m

Example

17 ≡ 5 mod 6 is true because 6 divides 17-5=12

24 ≡ 14 mod 6 is false because 6 does not divide 24-14=10

 

Applications of Congruences

Hashing

Hash (or dictionary) function maps a key to some other value.

A dictionary maps an index to the definition.

Example

h(k) = k mod m

h(k) = k mod 10

h(102) = 2

h(17) = 7

Example

Secure communications over public networks to verify that the message sent is the message received.

A hash maps input (such as a message text) to some number.

For example, a hash could operate by:

Code 'A' = 1, 'B'=2, etc.

Sum the values of the message "ABCDEF".

The sum, modulus 16, will be a value between 0-15.

A B C D E F 1 +2 +3 +4 +5 +6

h("ABCDEF") = 21 mod 16 = 5

Send the encrypted message "ABCDEF" along with the hash, 5.

Receiver decrypts message and recomputes the hash on message received.

If computed hash and received hash the same, then verifies no tampering with message. Assuming the divisor is large enough.

Using a modulus 16 creates a 4-bit hash, only 16 possibilities. Allows someone to intercept and too easily change the message in an undetectable way.

SHA-1 (Secure Hash Algorithm 1) developed by NSA processes 512-bit blocks to produce a 160-bit hash. Very difficult to change the message and produce the same hash.

Other common hashes are MD5 (a 32-bit hash by Ronald Rivest, the R in the RSA algorithm). That means there are 2³² possible hash values.

Hashing this file you are reading might produce the 32-bit value: 88659b92

Changing one 'a' to 'A' could produce a completely different hash value: 1c807dfd

Often serves as part of secure transmissions, such as Secure Socket Layer (SSL) or the newer Transport Layer Security (TLS), over public networks.

Example

We saw that linear search was O(n) and binary search was O(log n).

Hashing is O(1) using h(k) = k mod m.

0 1 2 3 4 5 6 7 8 9 20 31 2 53 14         16 107 58  79

h(k) = k mod 10

Search for 35

35 hashes to location 5

h(35) = 35 mod 10 = 5

Requires only one operation.

Example

IBM recently announced the release into the public domain of a hashing algorithm that will significantly reduce the size of router tables on the Internet. Since router table size is a key factor in router performance, the larger the table the slower the routing, the greater the likelihood of lost packets, this is a big deal for bandwidth carnivores.

Cryptology

Cryptology generally depends upon the sender and receiver each possessing a common key.

Sender uses a key to encrypt a message.

Receiver uses a key to decrypt.

Symmetric keys mean the same key is used by sender and receiver.

 

Example - Caesar's Cipher

Represent each letter 'A'=0, 'B'=1, 'C'=2, 'D'=3, 'E'=4, 'F'=5, etc.

Encrypt by adding 3 to each letter.

"CAB" = 2 0 1 which encrypts to: 5 3 4 = "FDE"

f(x) = x + 3

Problem is 'Z'=25 and f(25) = 28, not a letter.

Use mod to map cipher to 0-25 values.

f(x) = (x + 3) mod 26

f('Z') = f(25) = (25 + 3) mod 26 = 2 = 'C'

Decrypt by subtracting 3 from each letter.

"FDE" = 5 3 4 which decrypts to: 2 0 1 = "CAB"

f^-1(x) = (x - 3) mod 26

f^-1(2) = (2 - 3) mod 26 = -1 mod 26 = 25

In reality, such ciphers are easily broken.

 

3.8 Matrices

Matrix Arithmetic

Definition

Matrix addition MS+R =MR+MS

Example

MR+MS 1 2 1 8 10 2 12 14 3 16 18

=

MR 1 2 1 1 2 2 3 4 3 5 6

+

MS 1 2 1 7 8 2 9 10 3 11 12

MR+MS 1 2 1 (R1,1+S1,1) (R1,2+S1,2) 2 (R2,1+S2,1) (R2,2+S2,2) 3 (R3,1+S3,1) (R3,2+S3,2)

 

Definition

Matrix product MR×S = MR×MS

Example

MR×MS 1 2 3 1 27 30 33 2 61 68 75 3 95 106 117

=

MR 1 2 1 1 2 2 3 4 3 5 6

×

MS 1 2 3 1 7 8 9 2 10 11 12

MR×MS 1 2 3 1 1*7+2*10 = 27 1*8+2*11 = 30 1*9+2*12 = 33 2 3*7+4*10 = 61 3*8+4*11 = 68 3*9+4*12 = 75 3 5*7+6*10 = 95 5*8+6*11 = 106 5*9+6*12 = 117

MR×MS 1 2 3 1 (R1,1*S1,1)+(R1,2*S2,1) (R1,1*S1,2)+(R1,2*S2,2) (R1,1*S1,3)+(R1,2*S2,3) 2 (R2,1*S1,1)+(R2,2*S2,1) (R2,1*S1,2)+(R2,2*S2,2) (R2,1*S1,3)+(R2,2*S2,3) 3 (R3,1*S1,1)+(R3,2*S2,1) (R3,1*S1,2)+(R3,2*S2,2) (R3,1*S1,3)+(R3,2*S2,3)

Question 3.25

MR×MS 1 2 1     2

=

MR 1 2 3 1 3 2 1 2 6 5 4

×

MS 1 2 1 1 2 2 3 4 3 5 6

Zero-One Matrices

Definition

MR1 U R2 = MR1 v MR2

MR1 ∩ R2 = MR1 ^ MR2

Example

MR1 U R2 a1 a2 a3 a1 1 0 1 a2 0 1 0 a3 1 0 1             MR1 ∩ R2 a1 a2 a3 a1 1 0 0 a2 0 0 0 a3 0 0 1

MR1 a1 a2 a3 a1 1 0 0 a2 0 1 0 a3 0 0 1

MR2 a1 a2 a3 a1 1 0 1 a2 0 0 0 a3 1 0 1

Definition

Boolean product MR¤S =MR¤MS

Example

MR¤MS 1 2 3 1 1 0 1 2 0 0 0 3 0 0 0

=

MR 1 2 1 1 0 2 0 1 3 0 0

¤

MS 1 2 3 1 1 0 1 2 0 0 0

 

MR¤MS 1 2 3 1 (R1,1^S1,1)v(R1,2^S2,1) (R1,1^S1,2)v(R1,2^S2,2) (R1,1^S1,3)v(R1,2^S2,3) 2 (R2,1^S1,1)v(R2,2^S2,1) (R2,1^S1,2)v(R2,2^S2,2) (R2,1^S1,3)v(R2,2^S2,3) 3 (R3,1^S1,1)v(R3,2^S2,1) (R3,1^S1,2)v(R3,2^S2,2) (R3,1^S1,3)v(R3,2^S2,3)