Chapter 5:
Algorithms
Computer Science: An Overview
Eleventh Edition
by
J. Glenn Brookshear
Copyright 2012 Pearson Education, Inc.
Chapter 5: Algorithms
5.1 The Concept of an Algorithm
5.2 Algorithm Representation
5.3 Algorithm Discovery
5.4 Iterative Structures
5.5 Recursive Structures
5.6 Efficiency and Correctness
Copyright 2012 Pearson Education, Inc. 0-2
1
Definition of Algorithm
An algorithm is an ordered set of
unambiguous, executable steps
that defines a terminating process.
Copyright 2012 Pearson Education, Inc. 0-3
Algorithm Representation
Requires well-defined primitives
A collection of primitives constitutes a
programming language.
Copyright 2012 Pearson Education, Inc. 0-4
2
Figure 5.2 Folding a bird from a
square piece of paper
Copyright 2012 Pearson Education, Inc. 0-5
Figure 5.3 Origami primitives
Copyright 2012 Pearson Education, Inc. 0-6
3
Pseudocode Primitives
Assignment
name expression
Conditional selection
if condition then action
Copyright 2012 Pearson Education, Inc. 0-7
Pseudocode Primitives (continued)
Repeated execution
while condition do activity
Procedure
procedure name (generic names)
Copyright 2012 Pearson Education, Inc. 0-8
4
Figure 5.4 The procedure Greetings
in pseudocode
Copyright 2012 Pearson Education, Inc. 0-9
Polyas Problem Solving Steps
1. Understand the problem.
2. Devise a plan for solving the problem.
3. Carry out the plan.
4. Evaluate the solution for accuracy and
its potential as a tool for solving other
problems
problems.
Copyright 2012 Pearson Education, Inc. 0-10
5
Getting a Foot in the Door
Try working the problem backwards
Solve
S l an easieri related
l t d problem
bl
Relax some of the problem constraints
Solve pieces of the problem first (bottom up
methodology)
Stepwise refinement: Divide the problem into
smaller problems (top-down methodology)
Copyright 2012 Pearson Education, Inc. 0-11
Ages of Children Problem
Person A is charged with the task of determining
the ages of Bs
B s three children
children.
B tells A that the product of the childrens ages is 36.
A replies that another clue is required.
B tells A the sum of the childrens ages.
A replies that another clue is needed.
B tells A that the oldest child plays the piano
piano.
A tells B the ages of the three children.
How old are the three children?
Copyright 2012 Pearson Education, Inc. 0-12
6
Figure 5.5
Copyright 2012 Pearson Education, Inc. 0-13
Iterative Structures
Pretest loop:
while (condition) do
(loop body)
Posttest loop:
repeat (loop body)
until(condition)
Copyright 2012 Pearson Education, Inc. 0-14
7
Figure 5.6 The sequential search
algorithm in pseudocode
Copyright 2012 Pearson Education, Inc. 0-15
Figure 5.7 Components of repetitive
control
Copyright 2012 Pearson Education, Inc. 0-16
8
Figure 5.8 The while loop structure
Copyright 2012 Pearson Education, Inc. 0-17
Figure 5.9 The repeat loop structure
Copyright 2012 Pearson Education, Inc. 0-18
9
Figure 5.10 Sorting the list Fred, Alex,
Diana, Byron, and Carol alphabetically
Copyright 2012 Pearson Education, Inc. 0-19
Figure 5.11 The insertion sort
algorithm expressed in pseudocode
Copyright 2012 Pearson Education, Inc. 0-20
10
Recursion
The execution of a procedure leads to
another
th execution
ti off the
th procedure.
d
Multiple activations of the procedure are
formed, all but one of which are waiting for
other activations to complete.
Copyright 2012 Pearson Education, Inc. 0-21
Figure 5.12 Applying our strategy to
search a list for the entry John
Copyright 2012 Pearson Education, Inc. 0-22
11
Figure 5.13 A first draft of the binary
search technique
Copyright 2012 Pearson Education, Inc. 0-23
Figure 5.14 The binary search
algorithm in pseudocode
Copyright 2012 Pearson Education, Inc. 0-24
12
Figure 5.15
Copyright 2012 Pearson Education, Inc. 0-25
Figure 5.16
Copyright 2012 Pearson Education, Inc. 0-26
13
Figure 5.17
Copyright 2012 Pearson Education, Inc. 0-27
Algorithm Efficiency
Measured as number of instructions
executed
t d
Big theta notation: Used to represent
efficiency classes
Example: Insertion sort is in (n2)
Best,
Best worst
worst, and average case analysis
Copyright 2012 Pearson Education, Inc. 0-28
14
Figure 5.18 Applying the insertion sort in
a worst-case situation
Copyright 2012 Pearson Education, Inc. 0-29
Figure 5.19 Graph of the worst-case
analysis of the insertion sort algorithm
Copyright 2012 Pearson Education, Inc. 0-30
15
Figure 5.20 Graph of the worst-case
analysis of the binary search algorithm
Copyright 2012 Pearson Education, Inc. 0-31
Software Verification
Proof of correctness
Assertions
Preconditions
Loop invariants
Testing
Copyright 2012 Pearson Education, Inc. 0-32
16
Chain Separating Problem
A traveler has a gold chain of seven links.
He must stay at an isolated hotel for seven
nights.
The rent each night consists of one link from the
chain.
What is the fewest number of links that must be
cut so that the traveler can p
pay
y the hotel one link
of the chain each morning without paying for
lodging in advance?
Copyright 2012 Pearson Education, Inc. 0-33
Figure 5.21 Separating the chain
using only three cuts
Copyright 2012 Pearson Education, Inc. 0-34
17
Figure 5.22 Solving the problem with
only one cut
Copyright 2012 Pearson Education, Inc. 0-35
Figure 5.23 The assertions associated
with a typical while structure
Copyright 2012 Pearson Education, Inc. 0-36
18
