Discrete Mathematics for Computer Science

46 CHAPTER 1 Sets, Proof Templates, and Induction

Selection Sort Steps

Initial order (^2 1 4 3 5)
Step One 2 1 4 3 5 Identify smallest (nonboxed element) in
four comparisons
W 2 4 3 5 Swap2with I
Step Two [] 2 4 3 5 Identify smallest (nonboxed element) in
three comparisons
EL [ 4 3 5 No swap needed
Step Three W [ 4 3 5 Identify smallest (nonboxed element) in
two comparisons
[] [^4 5 Swap4with3
Step Four [] [ [ 4 5 Identify smallest (nonboxed element) in
one comparison
W ] [ 5 No swap needed

Step Five J] M M [4] 5 Identify smallest (nonboxed element) in

zero comparisons

Final Order 1 2 3 4 5 Number of comparisons = 4 + 3 + 2 + 1 + 0

One way to proceed is to try to find a pattern for small instances of the problem: Add

up, say, the natural numbers from 0 to n for n = 0, 1, 2, 3, 4, and try to find a pattern.

Patterns can be very misleading, however, because a pattern that may look correct for the

first few numbers may very easily fail later on. If a possible pattern is found, it is necessary

to prove whether it works in general. Consider the sums for the first few integers:

0=0

0+1 = 1

0±1+2 = 3

0+1+2+3=6

0 + 1 + 2 + 3 + 4 10

0+1+2+3+4+5=15

To find a different form for the problem often requires an idea that is not particularly

obvious. In this case, if you multiply each of the sums by two and then factor the doubled

value, you can hopefully see a pattern emerging. This transformation of the sums gives

2.0= 0=0.1

2.(0+1)= 2=1.2

2.(0+1+2)= 6=2.3

2.(0+1+2+3)= 12=3.4

2.(0+ 1 +2+3+4) = 20=4.5

The pattern that seems to be emerging is

2.(0+1+2+--.+n) =n.(n+1)