Introduction to Algorithms &

Programming
Steve James
Lecture 3
RECAP
 Algorithms
• Individual, well-defined, predictable
instructions (finite).
• Procedure in terms of:
– Actions to be executed
– The order to execute these actions in
 Variables
• Name and values
• Assign name to a value
meaning_of_life = 42
y = 2.45824406892

• Data types:
– Integer, Float, Boolean, etc
 Arithmetic Operators
• Addition, subtraction, multiplication, division,
modulus

• NB: Integer division!!

• Operators have precedence

 Input/Output
• input() reads in a string from the user.
• If we don’t want a string, we must cast it

name = input()
average_score = float(input())

• print() displays something on the screen

CONDITIONALS
 Control Structures
• We do not want to simply execute statements
one after another
• We want to control this order!
• Execute only if some condition holds
 The if Construct
If student’s grade is greater than or equal to 50
Output “Passed”

• If the condition is true:

– Output statement executed and program goes on
to the next statement
• If the condition is false:
– Output statement is ignored and the program
goes onto the next statement
 The if Construct
PSEUDOCODE FORM
if logical_expression:
statement_1
statement_2
...

PYTHON CODE
grade = int(input()) COLON
if grade >= 50: NECESSARY!
print("Passed")
TAB/4 SPACES
NECESSARY!
 Logical Expressions
• A logical expression is something that
evaluates to either TRUE or FALSE
• FALSE has a numeric value of 0
• TRUE has a numeric value of non-zero integer
 Rules of Precedence
• Logical operators have precedence too
Precedence Operator/ Evaluation
Operation
Level Symbol Direction
0 (first) () parentheses Inner ones
evaluated first
Left-to-right
1 <=, <, >, >=, less than or equal, less Left-to-right
==, != than, greater than,
greater than or equal,
equal to, not equal to
2 not negation (unary NOT) Left-to-right
3 and logical AND Left-to-right
4 or logical OR Left-to-right

https://docs.python.org/3.3/reference/expressions.html#operator-precedence
 Examples

if 2 < 3:
print("2 is less than 3")

if 2 != 3:
print("2 is not equal to 3")
 AND/OR Operators
• Imagine that two logical expressions (A and B)
evaluates to either TRUE (1) or FALSE (0). The
results of (A and B) and (A or B) for all possible
values of A and B are tabulated below (truth
table):
A B A and B A or B A B A and B A or B
FALSE FALSE FALSE FALSE 0 0 0 0
FALSE TRUE FALSE TRUE 0 1 0 1
TRUE FALSE FALSE TRUE 1 0 0 1
TRUE TRUE TRUE TRUE 1 1 1 1
 AND/OR Operators
• Note that and and or are short-circuit
operators:
– If the answer can be proved after evaluating the
first condition, the second condition is not
evaluated!
 Task
• Write a program that accepts two marks as
integers from input.

• Display whether both marks are above 50,

only 1 is above 50, or neither are.
 The if/else Construct
• Specifies an action to be performed both
when the condition is true and when it is false

If student’s grade is greater than or equal to 50

Output “Passed”
Else
Output “Failed” PYTHON CODE
grade = int(input())
if grade >= 50:
Can only be print("Passed")
one else! else:
Also, it’s print("Failed")
optional!
 The if/elif/else Construct
• What if we want to test multiple cases?
– E.g. Given a mark, output a symbol

• elif (short for else if) lets us check multiple

expressions for TRUE and execute a block of code
as soon as one of the conditions evaluates to
TRUE.
• Once condition is met, rest of statements skipped
 Example

grade = int(input())
if grade >= 75:
print("A")
elif grade >= 70:
Can have as
print("B")
many elif’s as
elif grade >= 60:
we want!
print("C")
elif grade >= 50:
print("D")
else:
print("F")

Can only be one else! Also, it’s optional!

 Nested if
• We can put any statements inside an if block
– These are nested ifs

num = int(input())
if num % 2 == 0:
if num % 3 == 0:
print("Divisible by 2 and 3")
else:
print("Divisible by 2; not divisible by 3")
else:
if num % 3 == 0:
print ("Divisible by 3; not divisible by 2")
else:
print ("Not divisible by 2; not divisible by 3")
ALGORITHMS

LOOPS
 The Issue
• So far, our algorithms have been a forward-
flowing sequence of statements
• But what if we want to execute something
repeatedly?
 Iteration
• Types of loops
– The while loop
– The do/while loop (not in Python!)
– The for loop

• Related concept:
– Break/continue statements
 The while loop
• Code executed repeatedly as long as some
condition remains true

While there are more items on my shopping list

Purchase next item and cross it off my list

• while loop repeated until condition

becomes false
 The while loop

PSEUDOCODE
while logical_expression:
statement_1
statement_2 }
Loop body

If the logical_expression is immediately

If logical_expression is always true, false, the loop body is never executed.
loop runs forever → “infinite loop”
 i = 0
while i < 100:
print(i, '\t', i * i)
i = i + 1
print("Done.")

• What it takes
– A control variable; i
– Initialise control variable; i=0
– Termination condition; if i < 100 is false, exit
– Increment control variable; i=i+1
– Some task to do each time; print …
 A problem
• A class of ten students took a test. The grades
(integers in the range 0 to 100) for this test are
available to you. Determine the class average

• Top-level pseudocode:
Determine the class average of the test

• First refinement:
Input and sum 10 test grades
Calculate and print class average
 Pseudocode
Set total to zero
Set counter to one

While counter is less than or equal to 10

Input next grade
Add the grade into the total
Add one to the grade counter

Set the class average to the total divided by 10

Print the class average
 Sentinel-controlled Repetition
• Sometimes we do not know how many times
we want the loop to execute!
• We use a sentinel value or flag to indicate
when we should stop
• Example: modify the class average program to
process an arbitrary number of grades each
time the program is run.
 Pseudocode
Set total to zero
Set counter to zero IS THIS RIGHT?!?!
Input first grade
While the user has not entered the sentinel
Add the grade into the total
Add one to the grade counter
Input next grade (possibly the sentinel)

Set average to the total divided by the counter

Print the average
Set total to zero
Set counter to zero

Input first grade

While the user has not entered the sentinel
Add the grade into the total
Add one to the grade counter
Input next grade (possibly the sentinel)

If the counter is not equal to zero

Set average to the total divided by the
counter
Print the average
Else
Output “No grades entered!”
 Homework
• Write a program that accepts a positive
𝑁
σ
integer 𝑁 and computes 𝑖=1 𝑖
• Write a program that produces the following
output
1
22
333
4444
55555
666666
7777777
88888888
999999999