ZeePedia Add to Favourites   |   Contact us


Introduction to Computing

<<< Previous ALGORITHMS: Pseudo code, Flowcharts Next >>>
 
img
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
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 ..
99
img
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
img
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
img
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
img
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 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
img
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
img
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
img
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
img
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
img
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- & high-level, interpreted & compiled, and structured &
object-oriented programming languages
108
Table of Contents:
  1. INTRODUCTION
  2. EVOLUTION OF COMPUTING
  3. World Wide Web, Web’s structure, genesis, its evolution
  4. Types of Computers, Components, Parts of Computers
  5. List of Parts of Computers
  6. Develop your Personal Web Page: HTML
  7. Microprocessor, Bus interface unit, Data & instruction cache memory, ALU
  8. Number systems, binary numbers, NOT, AND, OR and XOR logic operations
  9. structure of HTML tags, types of lists in web development
  10. COMPUTER SOFTWARE: Operating Systems, Device Drivers, Trialware
  11. Operating System: functions, components, types of operating systems
  12. Forms on Web pages, Components of Forms, building interactive Forms
  13. APPLICATION SOFTWARE: Scientific, engineering, graphics, Business, Productivity, Entertainment, Educational Software
  14. WORD PROCESSING: Common functions of word processors, desktop publishing
  15. Interactivity to Forms, JavaScript, server-side scripts
  16. ALGORITHMS
  17. ALGORITHMS: Pseudo code, Flowcharts
  18. JavaScript and client-side scripting, objects in JavaScript
  19. Low, High-Level, interpreted, compiled, structured & object-oriented programming languages
  20. Software Design and Development Methodologies
  21. DATA TYPES & OPERATORS
  22. SPREADSHEETS
  23. FLOW CONTROL & LOOPS
  24. DESIGN HEURISTICS. Rule of thumb learned through trial & error
  25. WEB DESIGN FOR USABILITY
  26. ARRAYS
  27. COMPUTER NETWORKS: types of networks, networking topologies and protocols
  28. THE INTERNET
  29. Variables: Local and Global Variables
  30. Internet Services: FTP, Telnet, Web, eMail, Instant messaging, VoIP
  31. DEVELOPING PRESENTATIONS: Effective Multimedia Presentations
  32. Event Handlers
  33. GRAPHICS & ANIMATION
  34. INTELLIGENT SYSTEMS: techniques for designing Artificial Intelligent Systems
  35. Mathematical Functions in JavaScript
  36. DATA MANAGEMENT
  37. DATABASE SOFTWARE: Data Security, Data Integrity, Integrity, Accessibility, DBMS
  38. String Manipulations:
  39. CYBER CRIME
  40. Social Implications of Computing
  41. IMAGES & ANIMATION
  42. THE COMPUTING PROFESSION
  43. THE FUTURE OF COMPUTING
  44. PROGRAMMING METHODOLOGY
  45. REVIEW & WRAP-UP of Introduction to Computing