Mythili Vutukuru
IIT Bombay
Reference: “C How to Program”, Deitel and Deitel, 8th Edition, Chapter 3
Algorithm = solution to a computing problem, consisting of
a sequence of actions executed in a particular order
Structure of an algorithm or computer program:
Statements to be executed sequentially
Statements that control which statements to execute next
(condition/selection, iterations)
Algorithm for morning routine
Wake up Sequential structure
Brush teeth
If time >= 8 am, run to class Condition/selection structure
Else if time < 8 am
Repeat ten times: run around gymkhana ground Iteration structure
Take bath, eat breakfast, go to class
Pseudocode: English-like statements to “think out” an algorithm
Actual program code that computer can run
Has more details than pseudocode, e.g., variable definition
Flow charts: graphical representation of an algorithm
Rectangles: action statements
Diamonds: decision statements to decide what to run next
Small circles: entry and exit points
Flow lines with arrows: connect all the shapes
Control statements connected one after another to build a large
algorithm
Sequence statements: block of statements execute one after
the other in a sequence
Enclosed in a set of braces { }
Condition statements: program flow branches out into one or
more paths, and which path is selected depends on whether
some condition satisfied
If time is past 8 am, do something. Else, do something else
Iteration statements: program flow repeats over a set of
statements, for a specified number of times or under some
condition is satisfied
Repeat ten times: run around gymkhana ground
Repeat until tired: run around gymkhana ground
Iteration for fixed number of times: counter-controlled iteration
Iteration until some end condition occurs: sentinel-controlled
iteration
Sentinel = signal to stop iteration
If a condition is met, program control shifts to a block of
statements written under the if condition
puts prints a string like printf
If a condition is met, program control shifts to a block of
statements written under the if condition
If a condition is met, a block of statements under “if” are
executed, otherwise, the block of statements under “else”
are executed
If a condition is met, a block of statements under “if” are
executed, otherwise, the block of statements under “else”
are executed
If you want to write a block of code and execute multiple
statements under if and else, then code block must be
enclosed in { }
Ternary operator: succinct way of writing if-else statement
Maybe confusing to read (personal opinion)
Can check multiple cases by placing one if-else block
inside another if/else block
Two equivalent ways of
writing nested if-else
statements
Method 1: if-else inside
previous else block
Two equivalent ways of
writing nested if-else
statements
Method 2: Series of else-if
blocks
If multiple if-else statements are present, and no
braces are used, compiler understands as follows:
Every else is matched to the closest if
Every if/else block is considered to have a single statement
Compiler ignores code indentation
Good idea to use braces always, to avoid ambiguity
In the code shown here, if x = 5 and y = 8, output is?
How would you change the code to get these outputs?
Repeat an action as long as a condition holds true
Body of the while statement should do something to cause
the condition to eventually become false, else results in
infinite loop
While loop exits when product reaches 243
Counter controlled iteration:
counter variable tracks how
many iterations to run
Code inside while block
must update counter
New keyword:
unsigned
Remember to initialize total
and counter, else garbage
values
Sentinel controlled iteration:
special variable (“sentinel”)
to indicate when to complete
iteration
Number of iterations not
known beforehand
New data type:
float (floating
point numbers) to
store average
Loop until sentinel
Avoid division by 0
Casting
(converting) result
of division to float
Format to print floating
point numbers
(number of digits after
decimal is specified)
Counter controlled iteration
Nesting control structures:
If-else block inside while block
Given two numbers a and b int a, b; //suitably initialized
(a > b), Euclid’s algorithm is int remainder;
an efficient algorithm to
compute GCD, based on the while (b > 0) {
idea that GCD(a, b) =
remainder = a % b;
GCD(a-b, b)
a = b;
Can you think of other b = remainder;
algorithms to compute GCD? }
printf(“GCD = %d\n”, a);
int a, b; //suitably initialized Example: GCD of a = 33 and b = 18
int remainder;
First iteration:
while (b > 0) { rem = 15, a = 18, b = 15
remainder = a % b;
a = b; Second iteration:
b = remainder; rem = 3, a = 15, b = 3
}
Third iteration:
printf(“GCD = %d\n”, a); rem = 0, a = 3, b = 0
Exit while loop
Print GCD = 3
Outer loop runs ten times
For every outer loop, inner
loop runs from 1 to value of
outer loop
If outer loop is 5, inner loop
runs from 1 to 5
Every iteration of inner
loop prints one asterisk
At end of inner loop, outer
loop prints new line
What is printed finally?
