Introduction to Computing

(CS111)

Junar A. Landicho

junarlandicho@ustp.edu.ph

“

Motivation is what gets you started. Habit is what keeps you going.”

Jim Ryun

Topic 5:

Algorithms

IT 416

Information Systems Development and Management

Learning Outcomes

By the end of this topic, students will be able to:

Apply a creative development process when creating computational artifacts.

Develop an algorithm for implementation in a program. Express an algorithm in a language.

Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity.

CS 111 – Introduction to Computing

Overview

1. The Concept of an Algorithm 2. Algorithm Representation 3. Algorithm Discovery

4. Iterative Structures

5. Recursive Structures

6. Efficiency and Correctness

CS 111 – Introduction to Computing

The Concept of an Algorithm

Python

Java

PHP

CS 111 – Introduction to Computing

The Concept of an Algorithm

Algorithms from previous topics

▪ Converting from one base to another

▪ Correcting errors in data

▪ Compression

Many researchers believe that every

activity of the human mind is the

result of an algorithm

CS 111 – Introduction to Computing

Formal Definition of Algorithm

An algorithm is an ordered set of

unambiguous, executable steps

that defines a terminating process

The steps of an algorithm can be

sequenced in different ways

▪ Linear (1, 2, 3, …)

▪ Parallel (multiple processors)

▪ Cause and Effect (circuits)

CS 111 – Introduction to Computing

Formal Definition of Algorithm

A Terminating Process

▪ Culminates with a result

▪ Can include systems that run

continuously (Hospital systems, Long

Division Algorithm)

A Non-terminating Process

▪ Does not produce an answer

CS 111 – Introduction to Computing

The Abstract Nature of Algorithms

There is a difference between an

algorithm and its representation.

▪ Analogy: difference between a story and a

book

A Program is a representation of an

algorithm.

A Process is the activity of executing an

algorithm.

CS 111 – Introduction to Computing

Algorithm Representation Java

PHP

Python

CS 111 – Introduction to Computing

Algorithm Representation

Is done formally with well-defined Primitives

▪ A collection of primitives constitutes a programming language.

Is done informally with Pseudocode

▪ Pseudocode is between natural language and a programming

language.

CS 111 – Introduction to Computing

Primitives

Folding a bird from a square piece of paper

CS 111 – Introduction to Computing

Primitives

Origami primitives

CS 111 – Introduction to Computing

Designing a Pseudocode Language

Choose a common programming

language

Loosen some of the syntax rules

Allow for some natural language

Use consistent, concise notation

We will use a Python-like

Pseudocode

CS 111 – Introduction to Computing

Pseudocode Primitives

Assignment

name = expression

Example

RemainingFunds = CheckingBalance +

SavingsBalance

CS 111 – Introduction to Computing

Pseudocode Primitives

Conditional selection

if (condition):

activity

Example

if (sales have decreased):

lower the price by 5%

CS 111 – Introduction to Computing

Pseudocode Primitives Conditional selection

if (condition):

activity

else:

activity

Example

if (year is leap year):

daily total = total / 366

else:

daily total = total / 365

CS 111 – Introduction to Computing

Pseudocode Primitives

Repeated execution

while (condition):

body

Example

while (tickets remain to be sold):

sell a ticket

CS 111 – Introduction to Computing

Pseudocode Primitives

Indentation shows nested conditions

if (not raining):

if (temperature == hot):

go swimming

else:

play golf

else:

watch television

CS 111 – Introduction to Computing

Pseudocode Primitives

Define a function

def name():

Example

def ProcessLoan():

Executing a function

if (. . .):

ProcessLoan()

else:

RejectApplication()

CS 111 – Introduction to Computing

Pseudocode Primitives

The procedure Greetings in pseudocode

def Greetings():

Count = 3

while (Count > 0):

print('Hello')

Count = Count - 1

CS 111 – Introduction to Computing

Pseudocode Primitives

Using parameters

def Sort(List):

.

.

Executing Sort on different lists

Sort(the membership list)

Sort(the wedding guest list)

CS 111 – Introduction to Computing

Algorithm Discovery Java

PHP

Python

CS 111 – Introduction to Computing

Algorithm Discovery

The first step in developing a program More of an art than a skill

A challenging task

CS 111 – Introduction to Computing

Polya’s 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.

CS 111 – Introduction to Computing

Polya’s Steps in the Context of Program Development

1. Understand the problem.

2. Get an idea of how an algorithmic function

might solve the problem.

3. Formulate the algorithm and represent it

as a program.

4. Evaluate the solution for accuracy and its

potential as a tool for solving other

problems.

CS 111 – Introduction to Computing

Getting a Foot in the Door

Try working the problem backwards Solve an easier related problem

▪ 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)

CS 111 – Introduction to Computing

Ages of Children Problem

Person A is charged with the task of

determining the ages of B’s three children.

▪ B tells A that the product of the children’s ages is

36.

▪ A replies that another clue is required.

▪ B tells A the sum of the children’s ages.

▪ A replies that another clue is needed.

▪ B tells A that the oldest child plays the piano.

▪ A tells B the ages of the three children.

How old are the three children?

CS 111 – Introduction to Computing

Ages of Children Problem

CS 111 – Introduction to Computing

Iterative Structures Java

PHP

Python

CS 111 – Introduction to Computing

Iterative Structures

A collection of instructions repeated in a looping manner

Examples include:

▪ Sequential Search Algorithm

▪ Insertion Sort Algorithm

CS 111 – Introduction to Computing

The Sequential Search Algorithm in Pseudocode

def Search (List, TargetValue):

if (List is empty):

Declare search a failure

else:

Select the first entry in List to be TestEntry while (TargetValue > TestEntry and entries remain): Select the next entry in List as TestEntry

if (TargetValue == TestEntry):

Declare search a success

else:

Declare search a failure

CS 111 – Introduction to Computing

Components of Repetitive ControlCS 111 – Introduction to Computing

Iterative Structures

Pretest loop:

while (condition):

body

Posttest loop:

repeat:

body

until(condition)

CS 111 – Introduction to Computing

Iterative Structures

While Loop _{Repeat Loop}

CS 111 – Introduction to Computing

Sorting the list Fred, Alex, Diana, Byron, and Carol alphabetically

CS 111 – Introduction to Computing

The Insertion Sort Algorithm expressed in Pseudocode

def Sort(List):

N = 2

while (N <= length of List):

Pivot = Nth entry in List

Remove Nth entry leaving a hole in List

while (there is an Entry above the

hole and Entry > Pivot):

Move Entry down into the hole leaving

a hole in the list above the Entry

Move Pivot into the hole

N = N + 1

CS 111 – Introduction to Computing

Recursive Structures Java

PHP

Python

CS 111 – Introduction to Computing

Recursive Structures

Repeating the set of instructions as

a subtask of itself.

Multiple activations of the procedure

are formed, all but one of which are

waiting for other activations to

complete.

Example: The Binary Search

Algorithm

CS 111 – Introduction to Computing

Applying our strategy to search a list for the entry John

CS 111 – Introduction to Computing

A First Draft of the Binary Search Technique

if (List is empty):

Report that the search failed

else:

TestEntry = middle entry in the List

if (TargetValue == TestEntry):

Report that the search succeeded

if (TargetValue < TestEntry):

Search the portion of List preceding TestEntry for TargetValue, and report the result of that search if (TargetValue > TestEntry):

Search the portion of List following TestEntry for TargetValue, and report the result of that search

CS 111 – Introduction to Computing

The Binary Search Algorithm in Pseudocode

def Search(List, TargetValue):

if (List is empty):

Report that the search failed

else:

TestEntry = middle entry in the List

if (TargetValue == TestEntry):

Report that the search succeeded

if (TargetValue < TestEntry):

Sublist = portion of List preceding TestEntry

Search(Sublist, TargetValue)

if (TargetValue < TestEntry):

Sublist = portion of List following TestEntry

Search(Sublist, TargetValue)

CS 111 – Introduction to Computing

Recursively Searching

CS 111 – Introduction to Computing

Second Recursive Search CS 111 – Introduction to Computing

Second Recursive Search, Second Snapshot

CS 111 – Introduction to Computing

Recursive Control

Requires initialization, modification,

and a test for termination (base

case)

Provides the illusion of multiple

copies of the function, created

dynamically in a telescoping

manner

Only one copy is actually running at

a given time, the others are waiting

CS 111 – Introduction to Computing

Efficiency and Correctness

Python

Java

PHP

CS 111 – Introduction to Computing

Efficiency and Correctness

Requires initialization, modification,

and a test for termination (base

case)

Provides the illusion of multiple

copies of the function, created

dynamically in a telescoping

manner

Only one copy is actually running at

a given time, the others are waiting

CS 111 – Introduction to Computing

Efficiency

Measured as number of instructions executed

Uses big theta notation:

Example: Insertion sort is in Θ(n2)

Incorporates best, worst, and average case analysis

CS 111 – Introduction to Computing

Applying the Insertion Sort in a Worst Case Situation

CS 111 – Introduction to Computing

Graph of the Worst-case Analysis of the Insertion Sort Algorithm

CS 111 – Introduction to Computing

Software Verification

Proof of correctness (with formal

logic)

▪ Assertions (Preconditions and Loop

invariants)

Testing is more commonly used to

verify software

Testing only proves that the

program is correct for the test cases

used

CS 111 – Introduction to Computing

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 pay the hotel one link of the chain each

morning without paying for lodging in advance?

CS 111 – Introduction to Computing

Separating the Chain using only Three Cuts

CS 111 – Introduction to Computing

Solving the problem with only One Cut

CS 111 – Introduction to Computing

The Assertions Associated with a typical While Structure

CS 111 – Introduction to Computing

Flowchart Symbols

CS 111 – Introduction to Computing

CS 111 – Introduction to Computing

</End>