Introduction to Algorithms &

Programming
Steve James
Lecture 4
 Admin
• Practical test:
– COMS1018A: 13 March
– COMS1022A: 12 March
– See Moodle announcement/email for scope
– Past papers up on Moodle

• Assignment:
– To be released next week
RECAP
 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!
 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")
 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 …
MORE LOOPS
 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!”
Write a program produces the following output
1
22
333
4444
55555
666666
7777777
88888888
999999999

row = 1
while row <= 9:
column = 0
while column < row:
print(row, end='')
column = column + 1
print()
row = row + 1
 Nested Control Statements
• Can put anything inside loop body
– Another loop (nested loop)
– If statements
– Etc.

• Develop a program that would count and display

the number of students that have passed and the
number of students that have failed from a list of
exam results for 10 students. If more than 8
students have passed, display "Bonus to
lecturer!"
 Pseudocode
• Top-level pseudocode:
Analyse exam results and decide if instructor should
receive a bonus

• First refinement:
Initialise variables
Input the 10 exam grades and count passes and
failures
Display a summary of the exam results and decide if
instructor should receive
a bonus
 Pseudocode
Initialise passes to 0
Initialise failures to 0
Initialise student counter to 0
While student counter is less than 10
Input the next exam result
If the student passed
Add 1 to passes
else
Add 1 to failures
Add 1 to student counter
End while
Display the number of passes
Display the number of failures
If more than 8 students passed
Display "Bonus!"
 Python
passes = 0
failures = 0
n_students = 0
while n_students < 10:
mark = int(input())
if mark >= 50:
passes = passes + 1
else:
failures = failures + 1
n_students = n_students + 1
print("Passes", passes)
print("Failures", failures)
if passes > 8:
print("Bonus!")
 Counting Loops
• In previous example, we knew we wanted to
count to some number
• Counting requires:
– initialisation of a counter,
– termination condition
– modification of counter

• For loops are convenient way of doing so!

 Python
passes = 0 passes = 0
failures = 0 failures = 0
n_students = 0 for n_students in range(0, 10, 1):
while n_students < 10: mark = int(input())
mark = int(input()) if mark >= 50:
if mark >= 50: passes = passes + 1
passes = passes + 1 else:
else: failures = failures + 1
failures = failures + 1 print("Passes", passes)
n_students = n_students + 1 print("Failures", failures)
print("Passes", passes) if passes > 8:
print("Failures", failures) print("Bonus!")
if passes > 8:
print("Bonus!")
 For loop
• for x in range(start, stop, step):

• range gives us a sequence of integers from start to stop

(excluding stop)
• step is how much to increment each time
• By default, start is 0 and step is 1

• range(0, 3, 1) → [0, 1, 2]
• range(5) → [0, 1, 2, 3, 4]
• range(0, 10, 2) → [0, 2, 4, 6, 8]
• range(20, 25) → [20, 21, 22, 23, 24]
• range(5, 2, -1) → [5, 4, 3] (decrement)
 The break statement
• break exits the loop we’re currently in,
regardless of completion of loop body

Print until … Print until 10

i = 0 i = 0
while True: while True:
print(i) if i > 10:
i = i + 1 break
print(i)
i = i + 1
 The continue statement
• continue stops execution of the loop body
– continue with next iteration

Skip 5
Print from 0 to 9
for i in range(10):
for i in range(10): if i == 5:
print(i) continue
print(i)
 Homework
A person invests R1000.00 in a savings account yielding 5% interest
annually. Assuming that all interest is left on deposit in the account,
calculate and print the amount of money in the account at the end of
each year for 10 years. Use the following formula for determining
these amounts:

𝑎 =𝑝 1+𝑟 𝑛

where
𝑝 is the original amount invested (the principal)
𝑟 is the annual interest rate
𝑛 is the number of years
𝑎 is the amount on deposit at the end of the nth year
LISTS
 What’s the problem?
• Read in 10 integers. The print them out in the
reverse order they were entered.

• Possible?
• What if there were 100 integers? 1000? 109 ?
• We would need many variables to store data

x0, x1, x2, ..., x999

numbers = list()
 Lists
• A list is a built-in type that lets us store a
collection of values
– We can store as many elements as we want
– Each value can be of any type

• Create an empty list using:

my_list = list() # or my_list = []

• Create a list of values with:

another_list = [27, 39, False, "Batman > Superman"]
 Appending/Extending
• We can add items to lists

student_names = list()
student_names.append("Bruce Banner") # add to end
student_names.append("Bruce Wayne")

more_names = ["Nakia", "Okoye", "M'Baku"]

student_names.extend(more_names) # add more_names to list
# Alternative: student_names = student_names + more_names

• We can also remove (look this up!)

 Indexing
• Can get or change items in a list by accessing
them directly
• Specify the location (index)

colours = ['red', 'blue', 'green']

print(colours[0]) # red colours [0] red
print(colours[2]) # green colours [1] blue
print(len(colours)) # 3 colours [2] green
 For with Lists
• We can loop through a list using a for-loop
sum = 0
numbers = [5, 78, 23]
for x in numbers:
# x will be each element of list
sum = sum + x
print(sum)

• We could also use its length to do this

sum = 0
numbers = [5, 78, 23]
for i in range(len(numbers)):
sum = sum + numbers[i]
print(sum)
 Enumerate
• We may want both the index and element at
the same time!

names = ["Sansa", "Arya", "Bran", "Rickon"]

for i, name in enumerate(names):
# enumerate gives us index and value for each element
print("The name at position", i, "is", name)
 In
• The in keyword is used to loop through a list
• But we can also use it to check if a list contains
something
– i.e. is this value in our list?

concert_lineup = ["Cassper", "Imagine Dragons", "Kwesta"]

if 'Imagine Dragons' in concert_lineup:
print("I'm not going")
 Strings
• Strings are similar to a list of characters!
• Can index
– But can’t assign
• No append
• Can add two strings together

name = "Glenn"
print(name[2]) # e
name = name + " Coco"
print(name) # Glenn Coco
 Homework
• Thanos believes that overpopulation will
destroy the universe. He has managed to
collect all the Infinity Stones, and is about to
use their power to remove half of everyone
from existence!
 Homework
• Write a program that reads a series of names into
a list. I suggest using your own name and your
friends’! Loop through each name in the list and
flip a coin. If heads, the person survives. If tails,
the person does not!
• Print out all the people that survived Thanos’
plan! Did you?

• You will need to look up how to generate a

random number/Boolean