CS101 - Introduction to Computing - Lecture Handout 17

User Rating:  / 0
PoorBest 

Related Content: CS101 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Introduction to Computing

Algorithms II

Focus of the last lecture 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

Algorithm Building Blocks

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

Algorithm Building Blocks

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 ..

Sequences

Loops

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

Problem Statement

Convert a decimal number into binary

Convert 75 to Binary

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

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

Tips on Writing Good Pseudo Code

Use indention for improved clarity
Do not put “code” in pseudo code – make your pseudo code language independent
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

Tips on Writing Good Pseudo Code

Does the flowchart depict the “correct” algorithm?
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

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

Back to the Objects to be Sorted

Sorting: Step A2

Sorting Step A2

Sorting: Step A3

Sorting Step A3

Sorting: Step B1

Sorting Step B1

Sorting: After Step B7

Sorting After Step B7

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

FLASH MOVIE FOR BUBBLE

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

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

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

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

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