University of Hawaii
ICS141:
Discrete Mathematics for
Computer Science I
Dept. Information & Computer Sci., University of Hawaii
Jan Stelovsky
based on slides by Dr. Baek and Dr. Still
Originals by Dr. M. P. Frank and Dr. J.L. Gross
Provided by McGraw-Hill
ICS 141: Discrete Mathematics I – Fall 2011 13-1
University of Hawaii
Lecture 14
Chapter 3. The Fundamentals
3.1 Algorithms
ICS 141: Discrete Mathematics I – Fall 2011 13-2
Algorithms
University of Hawaii
n Previously…
n Characteristics of algorithms
n Pseudocode
n Examples: Max algorithm
n Today…
n Examples: Sum algorithm
n Problem of searching an ordered list
n Linear search & binary search algorithms
n Sorting problem
n Bubble sort & insertion sort algorithms
ICS 141: Discrete Mathematics I – Fall 2011 13-3
Practice Exercises
University of Hawaii
n Devise an algorithm that finds the sum of all
the integers in a list.
n procedure sum(a1, a2, …, an: integers)
s := 0 {sum of elements so far}
for i := 1 to n {go thru all elements}
s := s + ai {add current item}
{now s is the sum of all items}
return s
ICS 141: Discrete Mathematics I – Fall 2011 13-4
Searching Algorithms
University of Hawaii
n Problem of searching an ordered list.
n Given a list L of n elements that are sorted into
a definite order (e.g., numeric, alphabetical),
n And given a particular element x,
n Determine whether x appears in the list,
n And if so, return its index (position) in the list.
n Problem occurs often in many contexts.
n Let’s find an efficient algorithm!
ICS 141: Discrete Mathematics I – Fall 2011 13-5
Linear Search (Naïve)
University of Hawaii
{Given a list of integers and an integer x to look up,
returns the index of x within the list or 0 if x is not in the list}
procedure linear_search
(x: integer, a1, a2, …, an: distinct integers)
i := 1 {start at beginning of list}
while (i ≤ n ∧ x ≠ ai) {not done and not found}
i := i + 1 {go to the next position}
if i ≤ n then index := i {it was found}
else index := 0 {it wasn’t found}
return index {index where found or 0 if not found}
ICS 141: Discrete Mathematics I – Fall 2011 13-6
Alg. #2: Binary Search
University of Hawaii
n Basic idea: At each step, look at the middle
element of the remaining list to eliminate half of it,
and quickly zero in on the desired element.
<x <x <x >x
ICS 141: Discrete Mathematics I – Fall 2011 13-7
Search Alg. #2: Binary Search
University of Hawaii
procedure binary_search
(x: integer, a1, a2, …, an: increasing integers)
i := 1 {left endpoint of search interval}
j := n {right endpoint of search interval}
while i < j begin {while interval has > 1 item}
m := ⎣(i + j)/2⎦ {midpoint}
if x > am then i := m + 1 else j := m
end
if x = ai then location := i else location := 0
return location {index or 0 if not found}
ICS 141: Discrete Mathematics I – Fall 2011 13-8
Search Example
University of Hawaii
n Search for 19 in the list
Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22
i i i j j
n using linear search i
n using binary search
n Entering while loop: i = 1, j = 16
n m = ⎣(i+j)/2⎦ = ⎣(1+16)/2⎦ = ⎣8.5⎦ = 8, i = 9, j = 16
n m = ⎣(i+j)/2⎦ = ⎣(9+16)/2⎦ = ⎣12.5⎦ = 12, i = 13, j = 16
n m = ⎣(i+j)/2⎦ = ⎣(13+16)/2⎦ = ⎣14.5⎦ = 14, i = 13, j = 14
n m = ⎣(i+j)/2⎦ = ⎣(13+14)/2⎦ = ⎣13.5⎦ = 13, i = 14, j = 14
n Exit loop
ICS 141: Discrete Mathematics I – Fall 2011 13-9
Sorting Algorithms
University of Hawaii
n Sorting is common in many applications.
n E.g. spreadsheets and databases
n We can search quickly when data is odrered!
n Sorting is also widely used as a subroutine in
other data-processing algorithms.
n Two sorting algorithms shown in textbook:
However, these are not
n Bubble sort
very efficient, and you should
n Insertion sort not use them on large data sets!
We’ll see some more efficient algorithms later in the course.
ICS 141: Discrete Mathematics I – Fall 2011 13-10
Bubble Sort
University of Hawaii
n Smaller elements “float” up to the top of the list, like
bubbles in a container of liquid, and the larger
elements “sink” to the bottom.
ICS 141: Discrete Mathematics I – Fall 2011 13-11
Bubble Sort Algorithm
University of Hawaii
procedure bubble_sort
(a1, a2, …, an: real numbers, n ≥ 2)
for i := 1 to n – 1 {iterate n – 1 passes}
for j := 1 to n – i
if aj > aj+1 then interchange aj and aj+1
{an-i+1, …, an is sorted and ≤ a1, …, an-i}
{a1, a2, …, an is sorted}
n Example 4: Use the bubble sort to put 3, 2, 4,
1, 5 into increasing order. (See previous slide)
ICS 141: Discrete Mathematics I – Fall 2011 13-12
Insertion Sort
University of Hawaii
n English description of algorithm:
n Start with the second element,
for each item in the input list:
n “Insert” it into the correct place in the sorted
output list generated so far. Like so:
n Find the location where the new item should
be inserted using linear or binary search.
n Then, shift the items from that position
onwards up by one position.
n Put the new item in the remaining hole.
ICS 141: Discrete Mathematics I – Fall 2011 13-13
Insertion Sort Example
University of Hawaii
n Use the insertion sort to put 3, 2, 4, 1, 5 into increasing order
n Insert the 2
nd element 2 in the right position:
n 3 > 2 ⇒ put 2 in front of 3. ⇒ 2, 3, 4, 1, 5
n Insert the 3
rd element 4 in the right position:
n 4 > 2 ⇒ do nothing. Move to the next comparison.
n 4 > 3 ⇒ do nothing. Done. ⇒ 2, 3, 4, 1, 5
n Insert the 4
th element 1 in the right position:
n 2 > 1 ⇒ put 1 in front of 2. ⇒ 1, 2, 3, 4, 5
n Insert the 5
th element 5 in the right position:
n 5 > 1 ⇒ do nothing. Move to the next comparison.
n 5 > 2 ⇒ do nothing. Move to the next comparison.
n 5 > 3 ⇒ do nothing. Move to the next comparison.
n 5 > 4 ⇒ do nothing. Done. ⇒ 1, 2, 3, 4, 5
ICS 141: Discrete Mathematics I – Fall 2011 13-14
Insertion Sort Algorithm
University of Hawaii
procedure insertion_sort
(a1, a2, …, an: real numbers, n ≥ 2)
for i := 2 to n begin
m := ai {the element to be inserted}
j := 1
while aj < m {look for the index of the hole with j }
j := j + 1
{now a1, …, aj-1 < m ≤ aj, …, ai }
{the hole is at j; j ≤ i, i.e. possibly j = i }
for k := j + 1 to i
ak := ak+1
ai := m
{a1, a2, …, ai are sorted in increasing order}
end {a1, a2, …, an are sorted in increasing order}
ICS 141: Discrete Mathematics I – Fall 2011 13-15
Efficiency of Algorithms
University of Hawaii
n Intuitively we see that binary search is much
faster than linear search,
n Also, we may see that insertion sort is better
than bubblesort in some cases (why? when?),
n But how do we analyze the efficiency of
algorithms formally?
n Use methods of algorithmic complexity,
which utilize the order-of-growth concepts
ICS 141: Discrete Mathematics I – Fall 2011 13-16
