Chapter 2: Algorithm

Discovery and Design

BMM 105 Introduction to Computer Engineering
Fall 2022
Assoc. Prof. Dr. Ayça Kolukısa Tarhan
atarhan@[Link]
Objectives

In this chapter, you will learn about

n Representing algorithms

n Examples of Algorithmic Problem Solving

Invitation to Computer Science, C++ Version, Fourth Edition 2

Representing Algorithms
n Natural language

q Language spoken and written in everyday life

q Problems with using natural language for

algorithms

n Verbose

n Imprecise

q Relies on context and experiences to give precise meaning

to a word or phase

Invitation to Computer Science, C++ Version, Fourth Edition 3

 Figure 2.1
The Addition Algorithm of Figure 1.2 Expressed in Natural Language

Invitation to Computer Science, C++ Version, Fourth Edition 4

Representing Algorithms (continued)

n High-level programming language

q Examples: C++, Java, Python

q Problem with using a high-level programming

language for algorithms
n During the initial phases of design, we are forced to deal with
detailed language issues

Invitation to Computer Science, C++ Version, Fourth Edition 5

 Figure 2.2
The Beginning of the Addition Algorithm of Figure 1.2 Expressed
in a High-Level Programming Language

Invitation to Computer Science, C++ Version, Fourth Edition 6

 Figure 1.2
Algorithm for Adding Two m-digit Numbers

Invitation to Computer Science, C++ Version, Fourth Edition 7

Pseudocode

n English language constructs modeled to look

like statements available in most programming
languages
n Steps presented in a structured manner
(numbered, indented, and so on)
n No fixed syntax for most operations is required

Invitation to Computer Science, C++ Version, Fourth Edition 8

Pseudocode (continued)

n Less ambiguous and more readable than natural

language
n Emphasis is on process, not notation
n Well-understood forms allow logical reasoning
about algorithm behavior
n Can be easily translated into a programming
language

Invitation to Computer Science, C++ Version, Fourth Edition 9

Sequential Operations

n Computation operations

q Example

n Set the value “variable” to “arithmetic expression”

n Set the value “carry” to “0”

q Variable

n Named storage location that can hold a data value

Invitation to Computer Science, C++ Version, Fourth Edition 10

 n Set the value “carry” to “0”

n Set the value “carry” to “4+5”

n Set the value “carry” to “carry + 1”

carry
10

Invitation to Computer Science, C++ Version, Fourth Edition 11

Sequential Operations (continued)
n Input operations
q To receive data values from the outside world
q Example
n Get a value for r, the radius of the circle
n Output operations
q To send results to the outside world for display
q Example
n Print the value of Area

Invitation to Computer Science, C++ Version, Fourth Edition 12

 Gallons used Starting mileage Ending mileage

2 7 15

Distance driven Average miles per gallon

8 4

Invitation to Computer Science, C++ Version, Fourth Edition 13

Conditional and Iterative Operations
n Sequential algorithm
q Also called straight-line algorithm

q Executes its instructions in a straight line from top to

bottom and then stops

n Control operations
q Conditional operations

q Iterative operations

Invitation to Computer Science, C++ Version, Fourth Edition 14

Conditional and Iterative Operations
(continued)
n Conditional operations
q Ask questions and choose alternative actions based on
the answers
q Example
n if x is greater than 25 then
print x
else
print x times 100

Invitation to Computer Science, C++ Version, Fourth Edition 15

 Figure 2.5
Second Version of the Average Miles per Gallon Algorithm

Invitation to Computer Science, C++ Version, Fourth Edition 16

Algorithm for average of three numbers
response=yes
While response = yes do
Get the values of x,y,z
Set the value of sum to (x+y+z)
If sum is greater than
Set the value of average to sum/3
Print the average
Else
Print the “bad data”
Print the message “do you want to do again”?
Get the value of response from the user
End loop
Stop

Invitation to Computer Science, C++ Version, Fourth Edition 17

Conditional and Iterative Operations
(continued)
n Iterative operations – while statement

q Perform “looping” behavior, repeating actions until

a continuation condition becomes false

q Loop

n The repetition of a block of instructions

Invitation to Computer Science, C++ Version, Fourth Edition 18

Conditional and Iterative Operations
(continued)
n Examples
n while j > 0 do
set s to s + aj
set j to j - 1

n repeat
print ak
set k to k + 1
until k > n

Invitation to Computer Science, C++ Version, Fourth Edition 19

Conditional and Iterative Operations
(continued)
n Components of a loop

q Continuation condition

q Loop body

n Infinite loop

q The continuation condition never becomes false

q An error

Invitation to Computer Science, C++ Version, Fourth Edition 20

 Figure 2.7
Third Version of the Average Miles per Gallon Algorithm

Invitation to Computer Science, C++ Version, Fourth Edition 21

Conditional and Iterative Operations
(continued)
n Pretest loop

q Continuation condition tested at the beginning of

each pass through the loop

q It is possible for the loop body to never be

executed

q While loop

Invitation to Computer Science, C++ Version, Fourth Edition 22

Conditional and Iterative Operations
(continued)

n Posttest loop

q Continuation condition tested at the end of loop

body

q Loop body must be executed at least once

q Do/While loop

Invitation to Computer Science, C++ Version, Fourth Edition 23

 Figure 2.9

Summary of
Pseudocode
Language
Instructions

Invitation to Computer Science, C++ Version, Fourth Edition 24

Examples of Algorithmic Problem Solving

n Go Forth and Multiply:

q Multiply two numbers using repeated addition
n Sequential search:
q Find a particular value in an unordered collection
n Find maximum:
q Find the largest value in a collection of data
n Pattern matching:
q Determine if and where a particular pattern occurs in
a piece of text

Invitation to Computer Science, C++ Version, Fourth Edition 25

Example 1: Go Forth and Multiply

n Task

q Implement an algorithm to multiply two numbers,

a and b, using repeated addition

n Algorithm outline
q Create a loop that executes exactly b times, with
each execution of the loop adding the value of a
to a running total

Invitation to Computer Science, C++ Version, Fourth Edition 26

 a b
6 3

count product
3 18

Figure 2.10
Algorithm for Multiplication via Repeated Addition

Invitation to Computer Science, C++ Version, Fourth Edition 27

Example 2: Looking, Looking, Looking

n Task

q Find a particular person’s name from an

unordered list of telephone subscribers

n Algorithm outline

q Start with the first entry and check its name, then
repeat the process for all entries

Invitation to Computer Science, C++ Version, Fourth Edition 28

Example 2: Looking, Looking, Looking
(continued)
n Algorithm discovery
q Finding a solution to a given problem

Invitation to Computer Science, C++ Version, Fourth Edition 29

Example 2: Looking, Looking, Looking
(continued)
n Correct sequential search algorithm
q Uses iteration to simplify the task
q Refers to a value in the list using an index (or
pointer)
q Handles special cases (such as a name not found
in the collection)
q Uses the variable Found to exit the iteration as
soon as a match is found

Invitation to Computer Science, C++ Version, Fourth Edition 30

 Figure 2.13
The
Sequential
Search
Algorithm

i 5 N1 T1
N2 T2 Found
NAME N3 T3
.
Ahmet Ahmet 054332892 NO
.

N10000 T10000

Invitation to Computer Science, C++ Version, Fourth Edition 31

Example 2: Looking, Looking, Looking
(continued)
n The selection of an algorithm to solve a problem
is greatly influenced by the way the data for that
problem is organized

Invitation to Computer Science, C++ Version, Fourth Edition 32

Example 3: Big, Bigger, Biggest

n Task

q Find the largest value from a list of values

n Algorithm outline

q Keep track of the largest value seen so far

(initialized to be the first in the list)

q Compare each value to the largest seen so far,

and keep the larger as the new largest

Invitation to Computer Science, C++ Version, Fourth Edition 33

Example 3: Big, Bigger, Biggest
(continued)
n Once an algorithm has been developed, it may
itself be used in the construction of other, more
complex algorithms

n Library

q A collection of useful algorithms

q An important tool in algorithm design and

development

Invitation to Computer Science, C++ Version, Fourth Edition 34

Example 3: Big, Bigger, Biggest
(continued)

n Find Largest algorithm

q Uses iteration and indices as in previous example

q Updates location and largest so far when needed

in the loop

Invitation to Computer Science, C++ Version, Fourth Edition 35

 Figure 2.14
Algorithm to Find the Largest Value in a List

Invitation to Computer Science, C++ Version, Fourth Edition 36

Example 4: Meeting Your Match

n Task

q Find if and where a pattern string occurs within a

longer piece of text

n Algorithm outline

q Try each possible location of pattern string in turn

q At each location, compare pattern characters

against string characters

Invitation to Computer Science, C++ Version, Fourth Edition 37

Example 4: Meeting Your Match
(continued)
n Abstraction

q Separating high-level view from low-level details

q Key concept in computer science

q Makes difficult problems intellectually manageable

q Allows piece-by-piece development of algorithms

Invitation to Computer Science, C++ Version, Fourth Edition 38

Example 4: Meeting Your Match
(continued)
n Top-down design

q When solving a complex problem

n Create high-level operations in the first draft of an

algorithm

n After drafting the outline of the algorithm, return to

the high-level operations and elaborate each one

n Repeat until all operations are primitives

Invitation to Computer Science, C++ Version, Fourth Edition 39

Example 4: Meeting Your Match
(continued)
n Pattern-matching algorithm

q Contains a loop within a loop

n External loop iterates through possible locations of

matches to pattern

n Internal loop iterates through corresponding

characters of pattern and string to evaluate match

Invitation to Computer Science, C++ Version, Fourth Edition 40

 Figure 2.16
Final Draft of the Pattern-Matching Algorithm

Invitation to Computer Science, C++ Version, Fourth Edition 41

Summary

n Algorithm design is a first step in developing an

algorithm

n Algorithm design must

q Ensure the algorithm is correct

q Ensure the algorithm is sufficiently efficient

n Pseudocode is used to design and represent

algorithms

Invitation to Computer Science, C++ Version, Fourth Edition 42

Summary

u Pseudocode is readable, unambiguous, and

able to be analyzed

u Algorithm design is a creative process; uses

multiple drafts and top-down design to develop
the best solution

u Abstraction is a key tool for good design

Invitation to Computer Science, C++ Version, Fourth Edition 43