CS1010E: Programming Methodology
Introduction
In the beginning..
[ CS1010E AY1112S1 Lecture 1 ]
Lecture Overview
Computers and Computing Fundamentals
Programming Languages
Problem Solving
Writing Algorithms in pseudo code
[ CS1010E AY1112S1 Lecture 1 ]
Computers as Information Processors
(1/2)
Computer = Hardware + Software.
Hardware: physical components for
computation/processing; should be simple, fast,
reliable.
Software: set of instructions to perform tasks to
specifications; should be flexible, user-friendly,
sophisticated.
Programs are thus software.
[ CS1010E AY1112S1 Lecture 1 ]
Computers as Information Processors
(2/2)
Computer are Information Processors
Raw
data
Computer
system
Processed
information
Data units
Internal representation in machine
o
o
o
1 bit (binary digit): 0 or 1
1 byte = 8 bits
Floating-point representation, etc.
Data types in programs
o
int, char, float, etc.
[ CS1010E AY1112S1 Lecture 1 ]
Computer: Hardware Components
Main Components:
Processor (controls devices and processes data).
Memory: stores programs and intermediate data.
Input Devices: accept data from outside world.
Output Devices: present data to the outside world.
Computer
Processor
Input
Output
Memory
[ CS1010E AY1112S1 Lecture 1 ]
Computer: Hardware Components
Monitor and
speaker (output)
Contains processor,
memory, buses, etc.
Keyboard and
mouse (input)
[ CS1010E AY1112S1 Lecture 1 ]
Software
Software is a written program that directs the
operation of computer
Related terms:
Program: Sequence of instructions that tells a
computer what to do
Execution: Performing the instruction sequence
Programming language: Language for writing
instructions to a computer
[ CS1010E AY1112S1 Lecture 1 ]
Software (1/4)
Program
Execution
Performing the instruction sequence
Programming language
Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors
Machine language or object code
Assembly language
High-level
[ CS1010E AY1112S1 Lecture 1 ]
Software (2/4)
Program
Execution
Performing the instruction sequence
Programming language
Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors
Machine language or object code
Program to which computer can
Assembly language
respond directly. Each instruction
High-level
is a binary code that corresponds
to a native instruction.
Example: 0001001101101110
[ CS1010E AY1112S1 Lecture 1 ]
Software (3/4)
Program
Execution
Performing the instruction sequence
Programming language
Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors
Machine language or object code
Assembly language
Symbolic language
High-level
for coding machine
language instructions.
Example: ADD A, B, C
[ CS1010E AY1112S1 Lecture 1 ]
10
Software (4/4)
Program
Execution
Performing the instruction sequence
Programming language
Sequence of instruction that tells a computer what to do
Language for writing instructions to a computer
Major flavors
Machine language or object code
Assembly language Detailed knowledge of the machine
is not required. Uses a vocabulary
High-level
and structure closer to the problem
being solved.
Examples: Java, C, C++,
Prolog, Scheme.
[ CS1010E AY1112S1 Lecture 1 ]
11
Programming Languages
At the lowest level, hardware components work
on electrical signals with two states:
On or Off (encoded as 1 or 0)
known as binary values
Hence, instructions and data must be expressed
in binary
known as Machine Language (Object Code)
Multiply 3.14159
with 1.23!
[ CS1010E AY1112S1 Lecture 1 ]
????
010111000111?
12
Programming Languages
It is hard to express our ideas using machine
language directly
Several flavors of programming language help to
bridge the gap!
Closer to hardware
Natural
Language
Multiply 3.141
with 1.23
High Level
Language
Assembly
Language
Machine
Language
res = 3.141*1.23;
load $r1, 3.141
load $r2, 1.23
mul $r3, $r1, $r2
0110111011010
1101010101
0110001..
Ease of expression
[ CS1010E AY1112S1 Lecture 1 ]
13
Translating a program
High-level language programs (source
programs) must be translated into machine code
for execution
Translator
Compiler
Standard name for a translator whose source language is a
high-level language
Interpreter
Accepts a program written in a source language and
translates it to a program in a target language
A translator that both translates and executes a source
program
More on the compilation process next lecture
[ CS1010E AY1112S1 Lecture 1 ]
14
How to solve a problem?
Problem solving is a creative process
There is no fixed or universal approach
A great discovery solves a great problem but there is a grain
of discovery in the solution of any problem.
Your problem may be modest; but if it challenges your
curiosity and brings into play your inventive faculties, and if
you solve it by your own means, you may experience the
tension and enjoy the triumph of discovery.
Such experiences at a susceptible age may create a taste for
mental work and leave their imprint on mind and character
for a lifetime.
George Plya
[ CS1010E AY1112S1 Lecture 1 ]
15
Problem Solving Process
Programming can be viewed as a problem
solving process
From the problem specification, derive a solution
expressed in a program
Problem Solving Process
1.
2.
3.
4.
Analysis
Design
Implementation
Testing
[ CS1010E AY1112S1 Lecture 1 ]
16
Problem Solving Process: Analysis
Purpose:
Understand the problem
Establish the scope of the problem
What to do:
Determine the input, known facts and desirable
output
Write down a clear description of the problem so
that solution can be attempted
[ CS1010E AY1112S1 Lecture 1 ]
17
Problem Solving Process: Design
Purpose:
Reduce the problem into several components
Determine the interaction between components
What to do:
Describe the functionality of each of the
components
Describe the interaction between components
[ CS1010E AY1112S1 Lecture 1 ]
18
Problem Solving Process: Implementation
Purpose:
Develop each of the components
What to do:
Flesh out the design into actual usable component
Use the components to produce an overall
solution
[ CS1010E AY1112S1 Lecture 1 ]
19
Problem Solving Process: Testing
Purpose:
Ensure the solution meets the requirement
What to do:
Test each component individually to make sure
they function properly
Test the components as a whole
[ CS1010E AY1112S1 Lecture 1 ]
20
Problem Solving Process
Determine problem
features
Analysis
Write algorithm
Design
Produce code
Implementation
Check for correctness
and efficiency
Testing
Rethink as
appropriate
The flow chart highlights the corresponding
programming activities
[ CS1010E AY1112S1 Lecture 1 ]
21
Algorithmic Problem Solving
An algorithm is a well-defined computational
procedure consisting of a set of instructions, that takes
some value or set of values, as input, and produces
some value or set of values, as output.
Input
[ CS1010E AY1112S1 Lecture 1 ]
Algorithm
Output
22
Algorithms
Characteristics of an algorithm:
1.
2.
3.
4.
Each step of an algorithm must be exact
An algorithm must terminate
An algorithm must be effective
An algorithm must be general
Can be presented in pseudo code or
flowchart
[ CS1010E AY1112S1 Lecture 1 ]
23
Euclidean algorithm
First documented algorithm by Greek mathematician
Euclid in 300 B.C.
To compute the GCD (greatest common divisor) of two integers.
1. Let A and B be integers with A > B 0.
2. If B = 0, then the GCD is A and algorithm ends.
3. Otherwise, find q and r such that
A = q.B + r
where 0 r < B
4. Replace A by B, and B by r. Go to step 2.
[ CS1010E AY1112S1 Lecture 1 ]
24
Algorithm: Observations
The Euclidean Algorithm highlights several
types of control structure (way to carry out
the steps):
Sequential:
Repetition:
Repeating the step(s) multiple times
Selection:
executing the steps one after another
Choose to take some of the steps
Together with the ability to store intermediate
results, all problems can be expressed!
[ CS1010E AY1112S1 Lecture 1 ]
25
Find maximum and average of a list of numbers
(1/3)
Version 1
Declare variables sum, count and max.
First, you initialise sum, count and max to zero.
Then, you enter the input numbers, one by one.
For each number that you have entered, assign it to num and
add it to the sum.
Increase count by 1.
At the same time, you compare num with max. If num is larger
than max, let max be num instead.
After all the numbers have been entered, you divide sum by the
numbers of items entered, and let ave be this result.
Print max and ave.
End of algorithm.
[ CS1010E AY1112S1 Lecture 1 ]
A better version in
next slide
26
Find maximum and average of a list of numbers
(2/3)
Version 2
sum count 0
// sum = sum of numbers
// count = how many numbers are entered?
max 0
// max to hold the largest value eventually
for each num entered,
count count + 1
sum sum + num
if num > max
then max num
ave sum / count
print max, ave
[ CS1010E AY1112S1 Lecture 1 ]
Is there any error
in this algorithm?
27
Find maximum and average of a list of numbers
(3/3)
Terminator box
start
Flowchart
Process box
sum count 0
max 0
Yes
Decision box
end of
input?
No
ave sum/count
increment count
sum sum + num
No
print max, ave
num > max?
Yes
max num
No
end
[ CS1010E AY1112S1 Lecture 1 ]
28
Algorithm: Examples (1/2)
Example 1: Compute the average of three integers.
Variables used:
A possible algorithm:
num1
enter values for num1, num2, num3
ave ( num1 + num2 + num3 ) / 3
print ave
Variables used:
num1
[ CS1010E AY1112S1 Lecture 1 ]
num3
ave
Another possible algorithm:
enter values for num1, num2, num3
total ( num1 + num2 + num3 )
ave total / 3
print ave
num2
num2
num3
total
ave
29
Algorithm: Examples (2/2)
Example 2: Find the sum of positive integers up to n
(assuming that n is a positive integer).
Algorithm:
enter value for n
// Initialise a counter count to 1, and ans to 0
count 1
ans 0
while (count <= n) do the following
ans ans + count
// add count to ans
count count + 1
// increase count by 1
Variables used:
n
count
ans
// Display answer
print ans
[ CS1010E AY1112S1 Lecture 1 ]
30
Step-wise Refinement (1/3)
From preceding examples, we can see that in general
an algorithm comprises three steps:
Input (read data (at the moment from user))
Compute (process the input data to generate some answers)
Output (display the answers)
The compute step is in general the most complex.
Step-wise refinement breaking down a complex step
into smaller steps.
[ CS1010E AY1112S1 Lecture 1 ]
31
Step-wise Refinement (2/3)
Example: Given a list A containing n integers, how
would you find the second largest value in the list?
Before we begin, remember Phase 1 of How To Solve
It: Understanding the problem.
Is the problem clear? If not, ask questions!
One possible algorithm:
read values into A
sort A in descending order
print A1
[ CS1010E AY1112S1 Lecture 1 ]
// step 1: input
// step 2: compute
// step 3: output
32
Step-wise Refinement (3/3)
We can actually stop here, if we are clear about how to
do each step.
If not, we need to refine the step. For instance, step 2,
how do we sort?
We wont discuss this now as sorting will be covered later.
Can you solve this problem without using sorting?
[ CS1010E AY1112S1 Lecture 1 ]
33
Exercise: Palindrome
A word is a palindrome if it reads the same
forward and backward.
Examples: NOON, RADAR
How do you determine if a word W is a
palindrome?
You can use notation Wi to indicate the letter
at location i
The left most position is 0, W0 is the first letter
34
