

Introduction
to Computing CS101
VU
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
Offpage
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
..
99
Introduction
to Computing CS101
VU
Sequences
A sequence of
instructions that are
executed in
the precise order
they
are
written in:
statement block
1
statement
block 1
statement
block 2
statement block
2
statement
block 3
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
VU
Problem
Statement
Convert
a decimal number into
binary
Convert 75 to
Binary
remainder
2
75
1
1
2
37
2
18
0
2
9
1
4
2
0
2
2
0
1
1
2
0
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
VU
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
No
Print y
Find
quotieny
= CONC(remainder,
x)
t
&
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
<SCRIPT>
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
VU
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 unsorted:
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
VU
Sorting:
Step A1
Swap?
Yes
Sorting:
Step A2
Sorting:
Step A2
Swap?
Yes
Sorting:
Step A3
Sorting:
Step A3
Swap?
No
104
Introduction
to Computing CS101
VU
Sorting:
After Step A7
Q:
Is the
list sorted?
A:
No
Sorting:
Step B1
Sorting:
Step B1
Swap?
Yes
Sorting:
Step B2
105
Introduction
to Computing CS101
VU
Sorting:
Step B2
Swap?
No
Sorting:
After Step B7
Q:
Is the
list sorted?
A:
No
Sorting:
Step C1
Sorting:
Step C1
Swap?
No
106
Introduction
to Computing CS101
VU
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
No
Yes
n>N ?
n = n+1
No
list[n] >
list
list[n+1]?
No
sorted?
n=0
Yes
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
VU
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 & highlevel,
interpreted & compiled, and structured
&
objectoriented
programming languages
108
Table of Contents:

