ALGORITHMS: Pseudo code, Flowcharts

<< ALGORITHMS

JavaScript and client-side scripting, objects in JavaScript >>

Introduction to Computing CS101

LESSON 17

ALGORITHMS II

Focus of the last Lesson was on Algorithms

Became familiar with the concept of algorithms:

What they are? (SEQUENCE OF STEPS)

What is their use?

What are their types?

What are the techniques used for representing them?

Pseudo code

Flowcharts

Actual code

Today ...

We will continue our discussion on algorithms that we started during the 16th lecture

In particular, we will look at the building blocks that are used in all algorithms

We will also discuss the pseudo code and flowcharts for particular problems

In addition, we will outline the pros and cons of those two techniques

17.1 Algorithm Building Blocks

All problems can be solved by employing any one of the following building blocks or their

combinations

Sequences

Conditionals

Loops

Start or stop

Flowchart

Process

Elements

Input or output

Decision

Flow line

Connector

Off-page connector

This review was essential because we we will be using these building blocks quite often today.

OK. Now on with the three building blocks of algorithms. First ..

Introduction to Computing CS101

Sequences

A sequence of instructions that are

executed in the precise order they

are written in:

statement block 1

statement block 2

statement block 3

Conditionals

Select between alternate courses of

action depending upon the evaluation

of a condition

If ( condition = true )

True

False

condition

statement block 1

Else

statement block 2statement

statement

End if

block 1

block 2

Loops

Loop through a set of statements as

long as a condition is true

Loop while ( condition = true )

statement block

End Loop

True

statement

condition

block

False

We will now present the algorithm for a problem whose solution is familiar to us

We will first go through the problem statement and then present the algorithm in three different formats:

1. Pseudo code

2. Flowchart

3. Actual code

100

Introduction to Computing CS101

Problem Statement

Convert a decimal number into binary

Convert 75 to Binary

remainder

1001011

We did write down the pseudo code for this problem last time. Lets do it again, and in a slightly more

formal way

17.2 Solution in Pseudo Code

Let the decimal number be an integer x, x > 0

Let the binary equivalent be an empty string y

Repeat while x > 0 {

Determine the quotient & remainder of x ÷ 2

y = CONCATENATE( remainder, y )

x = quotient

}

Print y

Stop

Q: Is this the only possible algorithm for converting a decimal number into a binary representation?

If not, then is this the best?

In terms of speed?

In terms of memory requirement?

In terms of ease of implementation?

You must ask these questions after writing any algorithm

17.3 Tips on Writing Good Pseudo Code

Use indention for improved clarity

Do not put "code" in pseudo code make your pseudo code language independent

101

Introduction to Computing CS101

Don't write pseudo code for yourself write it in an unambiguous fashion so that anyone with a

reasonable knowledge can understand and implement it

Be consistent

Prefer

formulas over English language descriptions

Start

Flowchart of

Decimal

Get x

to Binary

Conversion

x>0 ?

Yes

Print y

Find quotieny = CONC(remainder, x)

& remainder

x = quotient

Does the

flowchart

depict the

"correct"

x is the decimal number

algorithm?

y is the binary equivalent

What do we

mean by

"correct", or better yet, what do we

check for "correctness"?

One way is to check the algorithm

for a variety of inputs

Does it perform satisfactorily for:

x=0?

negative numbers?

numbers with fractional parts?

Decimal to Binary Conversion in JavaScript

x = 75;

// x is the decimal number

y = "";

// y is the binary equivalent

while ( x > 0) {

remainder = x % 2;

quotient = Math.floor( x / 2 );

y = remainder + y;

x = quotient;

}

document.write("y = " + y);

</SCRIPT>

NOTE: Don't worry if

you don't understand

this code for now; you

will - later!

102

Introduction to Computing CS101

Another Example: Sorting

Sort the following objects w.r.t. their

heights

Expected Result

Strategy

There are many strategies for solving this problem. We demonstrate a simple one:

Repeat the following steps while the list is un-sorted:

Start with the first object in the list

Swap it with the one next to it if they are in the wrong order

Repeat the same with the next to the first object

Keep on repeating until you reach the last object in the list

Back to the Objects to be Sorted

Q: Is the list sorted?

A: No

Sorting: Step A1

103

Introduction to Computing CS101

Sorting: Step A1

Swap? Yes

Sorting: Step A2

Swap? Yes

Sorting: Step A3

Swap? No

104

Introduction to Computing CS101

Sorting: After Step A7

Q: Is the list sorted?

A: No

Sorting: Step B1

Swap? Yes

Sorting: Step B2

105

Introduction to Computing CS101

Sorting: Step B2

Swap? No

Sorting: After Step B7

Q: Is the list sorted?

A: No

Sorting: Step C1

Swap? No

106

Introduction to Computing CS101

Sorting: After Step C7

Q: Is the list sorted?

A: Yes

STOP

Let's now look at this same process of sorting being applied to a bigger list

---FLASH MOVIE FOR BUBBLE SORT GOES HERE---

Start

Flowchart for the Sorting Process

list is an array containing the heights

N is the total number of objects in the list

Get list

Yes

n>N ?

n = n+1

list[n] >

list

list[n+1]?

sorted?

n=0

Yes

SWAP

Stop

list[n], list[n+1]

Dim swapFlag As Boolean, list(8) As Integer

readList( list() ) `this needs to be defined

swapFlag = True

Do While swapFlag = True

For n = 1 To 8

If list(n) > list(n + 1) Then

temp = list(n)

list(n) = list(n + 1)

list(n + 1) = temp

swapFlag = True

107

Introduction to Computing CS101

End If

Next

Loop

For n = 1 To 8

Debug.Print list(n)

Next

Q: Is this the only possible algorithm for sorting a list?

A: Certainly not! In fact this one (called the "Bubble sort") is probably the worst (reasonable) algorithm

for sorting a list it is just too slow

You will learn a lot more about sorting in your future courses

17.4 Pros and Cons of Flowcharts (1)

I personally don't find flowcharts very useful

The process of writing an algorithm in the form of a flowchart is just too cumbersome

And then converting this graphical form into code is not straight forward

However, there is another kind of flowcharts called Structured Flowcharts that may be better suited

for software developers

17.5 Pros and Cons of Flowcharts (2)

The good thing about flowcharts is that their symbols are quite intuitive and almost universally

understood

Their graphical nature makes the process of explaining an algorithm to one's peers quite straightforward

17.6 Pros and Cons of Pseudo Code (1)

Quite suitable for SW development as it is closer in form to real code

One can write the pseudo code, then use it as a starting point or outline for writing real code

Many developers write the pseudo code first and then incrementally comment each line out while

converting that line into real code

17.7 Pros and Cons of Pseudo Code (2)

Pseudo code can be constructed quite quickly as compared with a flowchart

Unlike flowcharts, no standard rules exist for writing pseudo code

With that we have reached the end of the materials that we wanted to cover today.

However, I still need to tell you about your assignment #6

In Today's Lecture, We ...

We continued our discussion on algorithms that we had started during the 16th lecture

In particular, we looked at the building blocks that are used in all algorithms

We also discussed the pseudo code and flowcharts for particular problems

In addition, we outlined the pros and cons of those two techniques

Focus of the Next Lecture: Programming Languages

To understand the role of programming languages in computing

To understand the differences among low- & high-level, interpreted & compiled, and structured &

object-oriented programming languages

108

Table of Contents: