Lecture Overview

Top Down Approach to Problem Solving

Functions

CS1010E Programming Methodology

Functions

Get this job done for me!

basic idea
execution flow
prototype and declaration
scoping rules

C Standard Library

Math Library

[ CS1010E AY1112S1 Lecture 3 ]

Top Down Approach

Example 1

When solving large problems, it is hard to

come up
p with a detailed solution right
g away
y
A common approach is:

One way to calculate the PI constant:

4
1

4
3

4
5

4
7

4
9

.........

Specify the major steps of the algorithm

Review each major step and break it down into
smaller steps ((step-wise refinement))
Repeat this process if needed until the steps are
well defined

When you compute the term using the

q
above:
sequence
1. PI starts as 4/1

(PI 4/1)

2 Subtract 4/3 from PI (PI PI 4/3)

2.

This is known as Top Down Approach to

problem solving

3. Add 4/5 to PI

(PI PI + 4/5)

4. Subtract 4/7 from PI

(PI PI 4/7)

5.
[ CS1010E AY1112S1 Lecture 3 ]

Example 1(contd)

PI Algorithm
even terms are
negative

4
1

4
3

4
5

4
7

4
9

.........

Denominator increases
by 2 every term

1. Initialize PI 4
2. Denom 3
3 nTerm 2
3.
4. while nTerm is <= 1000
i. Calculate new term
ii. Update PI
iii. nTerm nTerm + 1
5. Show PI

odd terms
e sa
are
e
positive

A more general algorithm:

1. Initialize PI 4
2. Denom 3
3. nTerm 2
4. while nTerm is <= 1000
i. Calculate new term
ii. Update PI
iii nTerm
iii.
T
nTerm
T
+1
5. Show PI

First draft with only the major steps

Example 2: Anagrams

a If nTerm is even
a.
PI PI Term
b. If nTerm is odd
PI PI + Term

refines

Major steps are further broken

down

[ CS1010E AY1112S1 Lecture 3 ]

Example: Anagram Algorithm

Two phrases are anagrams if one is formed

byy rearranging
g g the letters of the other,,
disregarding spaces and punctuation marks.

a. Term 4 / Denom

One possible solution using sorting

1. Read two words w1 and w2 from user

Debit card = Bad credit

The eyes = They see
Astronomer = Moon starer
A telescope = To see place
A decimal point = Im a dot in place

2. len1 = length of w1, len2 = length of w2

Steps to calculate the

length

3. if len1 not equal len2

print "Not
Not Anagrams
Anagrams" and stop
4. Sort w1 and w2 by alphabetical order

Steps to sort a word

into alphabetical
order

5. From position 0 to len1 - 1

If w1position not equal w2position

print "Not Anagrams" and stop

How
o do you de
determine
e
e if two
o words
o ds X a
and
dY
are anagrams?

6. print They are Anagrams" and Stop

7

[ CS1010E AY1112S1 Lecture 3 ]

Guidelines on Top Down Approach

Functions

As you learn more about C, you can see

clearer whether an algorithm
g
step
p is
expressible in C with simple statement(s)

Using the top down approach:

1.

If it is not p
possible, break it down further to simpler
p
sub-problems

To learn a programming language is to know:

The expressive power of the language
The limitations of the syntax
Such that high level algorithms can be translated
effectively

[ CS1010E AY1112S1 Lecture 3 ]

Duplicated coding:

2.

Problem: A plate with 3 holes

A major step may correspond to many smaller

steps after refinement
If we place all the statements in one place, the
actual major step may no longer be obvious
Large chunks of statements are hard to understand

Some computations may be needed multiple times

in an algorithm
E
Error
prone and
d wasteful
t f l to
t repeatt the
th coding
di

[ CS1010E AY1112S1 Lecture 3 ]

10

Algorithm: A plate with 3 holes

Given the following plate, what is the area of

the shaded region
g
after we drill 3 holes into
it?

A simple algorithm could be:

1. Read R, Ra, Rb and Rc from user
2. Calculate Area = R2
3. Calculate Areaa = Ra2

4. Calculate Areab = Rb2

b

[ CS1010E AY1112S1 Lecture 3 ]

Given:
R = radius of the plate
Ra, Rb and Rc = radii
of the circles a, b and
c respectively

Duplicate coding!

5. Calculate Areac = Rc2

6. Calculate Areashaded = Area Areaa- Areab - Areac
7 Show Areashaded
7.

11

Step 1 is also another source of duplicated

coding

[ CS1010E AY1112S1 Lecture 3 ]

12

Function: Syntax

Functions: The basic idea

A function in C:

A program unit that performs a well defined task

May take input and produces output

function header

result_datatype function_name( [input parameters] )

Visualization:
input

Function

SY
YNTAX

output

[0 or more declaration statements]

[0 or more other statements]
[return statement]
}

Example:
function body

sum

12

[ CS1010E AY1112S1 Lecture 3 ]

13

Function Header
Function header indicates:

Input (if any)

Data type of output result (if any)
3
9
sum takes two
integer inputs

14

Function Header: Input Parameters

sum

The syntax for input parameters is similar to

declaration statements:
Note that the data type is required before every
identifier

12

SYNTAX

[ CS1010E AY1112S1 Lecture 3 ]

sum gives
integer result

int sum( int x, int y )

datatype id1, datatype id2, ...

If the function does not take in any input

You can leave the input parameters blank

OR, you can use void
void is
i a special
i ld
data
t ttype th
thatt means "N
"Nothing"
thi "

Function Name is an identifier

Th usuall identifier
The
id tifi naming
i rule
l applies
li

[ CS1010E AY1112S1 Lecture 3 ]

15

[ CS1010E AY1112S1 Lecture 3 ]

16

Function Header: Output Data Type

You need to specify the type of values that a

function will produce
p

Function Body: Statements

The statements in a function body:

If the function does not return anything, you must

use a void to indicate that

Follow the rules we have learned so far

Additional variables can be declared
Computation
p
can be expressed
p
by
y statements

A function can return at most 1 result directly

Examples of function headers:

The input parameters:

double areaOfCircle( double radius )

void print_info( )
void print_info( void )

Work as variables declared in this function

Only difference is that their values are initialized
at the point of function call (more on this later)

void something( int x, double y, int z )

[ CS1010E AY1112S1 Lecture 3 ]

17

Some Functions:

[ CS1010E AY1112S1 Lecture 3 ]

18

Functions in a Program
//Preprocessor directive not shown

int sum( int x, int y )

{
additional variable
int result;

int sum( int x, int y )

{
int result;

result = x + y;

x and y will have well defined values

return result;

return the calculated result

result = x + y;
return result;

void print_info( )
{

int main( )
{
int input1, input2;

printf("Take a 4-digit number X\n");

printf("Rearrange the digits to get Y\n");
printf("Subtract and get R\n");

return;
}

Print instructions for the

user to follow

Any number of functions, complete

with header and body can be
placed before the main()

//read input1 and input2 from user

//use sum() to add the two inputs

no need to return anything

Only restriction: You must

have the function declared
b f
before
its
i point
i off usage

}
[ CS1010E AY1112S1 Lecture 3 ]

19

[ CS1010E AY1112S1 Lecture 3 ]

20

Function Calls: Parameters and Arguments

Function Calls and Execution Flow

fformall parameter
t

int sum( int x, int y )

{

3.

int sum( int x, int y )

{
............
}

int result;
result = x + y;
return result;

4.

Effectively:
int
i t x = 3;
3
int y = 9;

}
sum( 3, 9 );
int main( )
{
i t input1,
int
i
t1 i
input2,
t2 output;
t t
1.

actual arguments

Actual arguments in a function call have a

1-to-1
1
to 1 correspondence with the formal
parameters declared in function header

//read inputs

2.
2
5.

output = sum( input1, input2 );

printf("Sum is %d\n", output);

6.

}
[ CS1010E AY1112S1 Lecture 3 ]

21

Function Calls: Returned Result

The effect is jjust like a variable declaration with

initialization in that function

[ CS1010E AY1112S1 Lecture 3 ]

22

Problem: A plate with 3 holes

#include <stdio.h>
#define PI 3.14159

The result returned by a function:

//a function call

is a single value
essentially replaces the function call and can be
used in normal arithmetic operations and
assignment

double circleArea( double radius )

{
double area = PI * radius * radius;
return area;
}
int main( )
{
double rPlate, rA, rB, rC;
double areaPlate;

result = sum( 3, 9 ) + sum( 5, 2 );

//read rPlate, rA, rB, rC not shown

result = 12 + sum( 5, 2 );
//calculate area of plate

areaPlate = circleArea( rPlate ) circleArea( rA )

circleArea( rB ) circleArea( rC );

result = 12 + 7;
//print areaPlate not shown
return 0;

result = 19;
[ CS1010E AY1112S1 Lecture 3 ]

}
23

[ CS1010E AY1112S1 Lecture 3 ]

24

Functions: Scoping Rules

Functions: Prototype and Definition

It is important to realise:

Variables declared in a function are only

y visible
within the function

User of a function only needs to know:

int function( int x )

{
int y;
... ...
}

int
i
t main(
i ( )
{
int x, y;
}

These variables are totally

independent of each other.

A common misunderstanding is that by

changing a variable, it can directly affect
another variable of the same name
name. This
is NOT true.

Actual coding
g ((the function body)
y) is not essential
to the user

C Programming Language uses function

prototype

25

Function Prototype: Syntax and Usage

SYNTAX

You can only pass information into a

function through the actual arguments
in a function call.

[ CS1010E AY1112S1 Lecture 3 ]

Exa
ample

rDatatype fname( [parameters datatype] );

Function definition is:

int sum( int, int );

Portability:

27

You only need to show user the prototypes, not the full
coding

Ease of Maintenance:

Ensure the
E
th prototype
t t
is
i declared
d l db
before
f
any actual
t l
function call in the program

[ CS1010E AY1112S1 Lecture 3 ]

the full coding of the function

what we have seen so far

Separation
S
ti off function
f
ti prototype
t t
and
d definition
d fi iti
allows:

Similar to function header

Semicolon at the end
Identifier of parameters optional

Usage:

26

Function Definition

Note:

to provide the essential information of a function

[ CS1010E AY1112S1 Lecture 3 ]

Function name
Number of input parameter and data type
Output data type
Description of function

Function definition can be placed in a separate source

code file
Not covered in this course

[ CS1010E AY1112S1 Lecture 3 ]

28

Function Prototype: Example

Example
p

prototype
int sum( int, int );
// sum() takes two integer X, Y
// and return the sum of X + Y
int main( )
{
.........
output = sum( input1, input2 );
.........

function call

}
int sum( int x, int y )
{

definition

int result;
result = x + y;
return result;

}
[ CS1010E AY1112S1 Lecture 3 ]

29

Function Design: Guidelines

Relyy only
y on its inputs
p
to p
produce the output
p
Perform one task only
be reusable in your program and across programs

You need to represent a complicated but well

defined step in the algorithm

P
Program
Ab
Abstraction
t
ti

Supply prototypes before the main() function

Supply definitions after the main() function

Additionally, you need to give a simple

comment
co
e t to desc
describe
be tthe
e function:
u ct o

You have found a generally useful task that

can/will be reused

In this course, you need to:

Use a function when:

30

Programming Style: Prototypes!

A good function should:

[ CS1010E AY1112S1 Lecture 3 ]

What are the inputs (if any)?

What is the purpose?
p p
What is the output (if any)?
A clear but simple
p description
p
is needed

Reusability and Ease of Maintenance

[ CS1010E AY1112S1 Lecture 3 ]

31

[ CS1010E AY1112S1 Lecture 3 ]

32

Programming Style: Modularity

You need to break your program into

reasonable modules ((i.e. functions))

C Library

known as modularity

Use of functions will be evaluated:

Is everything
y
g in main()
() ?

Useful predefined functions

Is function useful in your program?

Is the design
g of function meaningful?
g

[ CS1010E AY1112S1 Lecture 3 ]

33

C Standard Library

Library:

A collection of functions
P t t
Prototypes
are organized
i d into
i t a header
h d file
fil (XXXX.h)
(
h)
Provides great portability and reusability:

Learning to use C Standard Library

User onlyy needs to include XXXX.h in their p

program
g
to use
those functions

A set of libraries specified by C specification

All compliant compilers must support them
Provides commonly used functionalities:

Our usage of printf(), scanf() are good

examples

C Standard Library:

As a user, we only need to know information

specified
p
by
y the function p
prototype
yp to use it

We highlight a few useful mathematical

functions here

Learn more by browsing the online C reference

http://www.acm.uiuc.edu/webmonkeys/book/c_guide/

Input / Output
Mathematical Functions
others ( more later )

[ CS1010E AY1112S1 Lecture 3 ]

35

[ CS1010E AY1112S1 Lecture 3 ]

36

Comp
pilation

HEA
ADER

Power Function

Prototyp
pe

#include <math.h>

double sqrt( double x);

//return the square root of x

Ex
xample

Ex
xample

Prototyp
pe

HEA
ADER

Square Root Function

double result;
result = sqrt( 4
4.0
0 );

//result = 2
2.0
0

37

A lot more

double result;
result = pow( 2
2.0,
0 4
4.0
0 );

//result = 16
16.0
0

[ CS1010E AY1112S1 Lecture 3 ]

38

Some Math Libraryy Functions

Trigonometry functions:

double pow( double base, double exp );

//return the baseexp

gcc yourFile.c -lm

[ CS1010E AY1112S1 Lecture 3 ]

#include <math.h>

Some Useful Math Library Functions (compiled with lm option)

function abs(x) from <stdlib.h>; the rest from <math.h>

sine, cosine, etc.

Logarithm functions:

log10, loge, exponential, etc.

C ili
Ceiling,
Fl
Floor, Ab
Absolution
l i value
l etc.

Reminder:

Learn to make use of standard library

D t reinvent
Dont
i
t th
the wheel
h l

[ CS1010E AY1112S1 Lecture 3 ]

39

[ CS1010E AY1112S1 Lecture 3 ]

40

C Elementts

Summary

Reference

Function
- Header and Body
- Function call
- Prototype and Definition

Chapter
p 3

Library
- Introduction to Math Library

Pro
ogramming Style

Problem Solving and Program Design in C

Jeri R.Hanly
y & Elliot B.Koffman,, 6th Edition,,
Pearson

Online C reference:
http://www.acm.uiuc.edu/webmonkeys/book/c_guide/

Separate Function Prototype and Definition

Give function description in comment
Modularity
y

[ CS1010E AY1112S1 Lecture 3 ]

41

[ CS1010E AY1112S1 Lecture 3 ]

42