Discrete Mathematics for Computer Science

Chapter Review 147

INPUT: An array A [ 0. .2N - I] of 2N integers

OUTPUT: The same array, with its elements sorted into nondecreasing order

for t =- I to 2N- l

size = 2'

for position = 1 to 2 N - I

B[position] = A[position]

loi = 0

while lol < 2N

hil = lol + size - 1

102 = hi 1 + 1

hi 2 = 102 + size - 1

position, = lol

position 2 = 102

position 3 = lo1

while position 1 < hi 1 and position 2 < hi 2 )

if B[positionj] < B[position 2 ]

then A [position 3 ] = B positionn]

position, = position 1 + 1

else A[position 3 ] = B[position 2 ]

position 2 = position 2 + 1

position 3 = position 3 + 1

while (position, < hi 1 )

A[position 3 ] = B[position 1 ]

position, = position 1 + I

position 3 = position 3 + 1

while (position 2 < hi 2 )

A[position 3 ] = B[position 2 ]

position 2 = position 2 + 1

position 3 = position 3 + 1

lol = lol + 2 • size

Determine what each part of the program does (first experiment with some sample test

lists), and write loop invariants for each loop that clarify why the algorithm works.

W Chapter Review

Propositions are the initial focus of the chapter. After defining propositions, we introduce

common operations to make formulas from propositions. The idea of a proposition being

true is introduced. We can verify whether a formula is true for a particular set of truth

values for its propositions using an expression tree. To find out if a formula is true for

all possible truth values, we use truth tables. The notions of tautologies, contradictions,