Algorithm Flowchart

Algorithm Flowchart (Python)

Calculate Median

a = [2, 0, 2, 1] # Input list
a.sort() # Sort list, note in-place modification
a

[0, 1, 2, 2]

n = len(a) # Calculate length of list 'a'
n

4

m = (n + 1)//2 # Calculate mid-point, // is operator for integer division 
m

2

n % 2 == 1 # % (modulo) gives remainder of division

False

sum(a[m-1:m+1])/2 # Calculate median as the mean of the two numbers around the mid-point

1.5

Branching Programs

Simple Conditional Statement

Basic Conditional Statement: if

• if - defines condition under which some code is executed

# Note that addition of a large value (100)
# has no effect on the median.
a = [2, 0, 2, 1, 100] 
a.sort()
n = len(a)
m = (n + 1)//2

if n % 2 == 1:
    a[m-1]

2

if <boolean_expression>:
    <some_code>

Complex Conditional Statements

if - else

• if - else - defines both condition under which some code is executed and alternative code to execute

a = [2, 0, 2, 1]
a.sort()
n = len(a)
m = (n + 1)//2

if n % 2 == 1:
    a[m-1]
else:
    sum(a[m-1:m+1])/2

1.5

if <boolean_expression>:
    <some_code>
else:
    <some_other_code>

if - elif - else

• if - elif - ... - else - defines both condition under which some code is executed and several alternatives

mark = 71

if mark >= 70:
    grade = "I"
elif mark >= 60:
    grade = "II.1"
elif mark >= 50:
    grade = "II.2"
else:
    grade = "F"

if <boolean_expression>:
    <some_code>
elif <boolean_expression>:
    <some_other_code>
...
...
else:
    <some_more_code>

grade

'I'

Indentation

• Indentation is semantically meaningful in Python.
• Visual structure of a program accurately represents its semantic structure.
• Tabs and spaces should not be mixed.
• E.g. Jupyter Notebook converts tabs to spaces by default.

Indentation in Python

x = 43
if x % 2 == 0:
    'Even'
    if x > 0:
        'Positive'
    else:
        'Negative'

x = 43
if x % 2 == 0:
    'Even'
if x > 0:
    'Positive'
else:
    'Negative'

'Positive'

Conditional Expressions

• Python supports conditional expressions as well as conditional statements

<expr1> if <test> else <expr2>

x = 42
y = 'even' if x % 2 == 0 else 'odd'
y

'even'

x = 42
if x % 2 == 0:
    y = 'even'
else:
    y = 'odd'
y

'even'

Loop

while

• while - defines a condition under which some code (loop body) is executed repeatedly

while <boolean_expression>:
    <some_code>

# Calculate a factorial  with decrementing function
# E.g. 5! = 1 * 2 * 3 * 4 * 5 = 120
x = 5
factorial = 1
while x > 0:
    factorial *= x # factorial = factorial * x
    x -= 1 # x = x - 1
factorial

120

Iteration: for

• for - defines elements and sequence over which some code is executed iteratively

for <element> in <sequence>:
    <some_code>

x = range(1, 6)
factorial = 1
for i in x:
    factorial *= i
factorial

120

Iteration with Conditional Statements

# Find maximum value in a list with exhaustive enumeration
l = [3, 27, 9, 42, 10, 2, 5]
max_val = l[0]
for i in l[1:]:
    if i > max_val:
        max_val = i
max_val

42

range() Function: Examples

l = [3, 27, 9, 42, 10, 2, 5]
for i in range(len(l)):
    print(l[i], end = ' ')

3 27 9 42 10 2 5 

l = [3, 27, 9, 42, 10, 2, 5]
s = []
for i in range(1, len(l), 2):
    s.append(str(l[i]))
s

['27', '42', '2']

Iterables

• Iterable is an object that generates one element at a item within iteration.
• Formally, they are objects that have __iter__ method, which return iterator.
• Some iterables are built-in (e.g. list, tuple, range()).
• But they can also be user-created.

Iteration over Multiple Iterables

• zip() function provides a convenient way of iterating over several sequences simultaneously.

l = [3, 27, 9, 42]
s = ['three', 'twenty seven', 'nine', 'forty-two']
for i, j in zip(l, s):
    print(str(i) + ' - ' + j)

3 - three
27 - twenty seven
9 - nine
42 - forty-two

Iteration: break and continue

• break - terminates the loop in which it is contained
• continue - exits the iteration of a loop in which it is contained

for i in range(1,6):
    if i % 2 == 0:
        break
    print(i)

1

for i in range(1,6):
    if i % 2 == 0:
        continue
    print(i)

1
3
5

Set and Dictionary Comprehensions

• Analogous to lists, sets and dictionaries have their own concise ways of iterating over them:

{<expr> for <elem> in <iterable> if <test>}
{<key>: <value> for <elem1>, <elem2> in <iterable> if <test>}

o = {'apple', 'banana', 'watermelon'}
{e[0].title() + ' - ' + e for e in o}

{'A - apple', 'B - banana', 'W - watermelon'}

d = {'apple': 150.0, 'banana': 120.0, 'watermelon': 3000.0}
{k.upper(): int(v) for k, v in d.items()}

{'APPLE': 150, 'BANANA': 120, 'WATERMELON': 3000}

More on Iterations

• Always make sure that the terminating condition for a loop is properly specified.
• Nested loops can substantially slow down your program, try to avoid them.
• Use break and continue to shorten iterations.
• Consolidate several loops into one whenever possible.

Function Definition: Example

def calculate_median(lst):
    """Calculates median
    
    Takes list as input
    Assumes all elements of list are numeric
    """
    lst.sort()
    n = len(lst)
    m = (n + 1)//2
    if n % 2 == 1:
        median = lst[m-1]
    else:
        median = sum(lst[m-1:m+1])/2
    return median

Function Call: Example

def is_positive(num):
    if num > 0:
        return True
    elif num < 0:
        return False

res1 = is_positive(5)
res2 = is_positive(-7)
res3 = is_positive(0)

print(res1)

True

print(res2)

False

print(res3)

None

Function Arguments: Example

def format_date(day, month, year, reverse = True):
    if reverse:
        return str(year) + '-' + str(month) + '-' + str(day)
    else:
        return str(day) + '-' + str(month) + '-' + str(year)

format_date(4, 11, 2024)

'2024-11-4'

format_date(day = 4, month = 11, year = 2024)

'2024-11-4'

format_date(4, 11, 2024, False)

'4-11-2024'

format_date(day = 4, month = 11, year = 2024, False)

positional argument follows keyword argument (<string>, line 1)

Variable Number of Arguments

• * in function definition collects unmatched position arguments into a tuple.
• ** collects keyword arguments into a dictionary.

def foo(*args):
    print(args)

foo(1, 'x', [5,6,10])

(1, 'x', [5, 6, 10])

def foo(**kwargs):
    print(kwargs)

foo(first = 1, second = 'x', third = [5,6,10])

{'first': 1, 'second': 'x', 'third': [5, 6, 10]}

Nested Functions

def which_integer(num):
    def even_or_odd(num):
        if num % 2 == 0:
            return 'even'
        else:
            return 'odd'
    if num > 0:
        eo = even_or_odd(num)
        return 'positive ' + eo
    elif num < 0:
        eo = even_or_odd(num)
        return 'negative ' + eo
    else:
        return 'zero'

which_integer(-43)

'negative odd'

even_or_odd(-43)

NameError: name 'even_or_odd' is not defined

Recursion

Reddit

Recursion in Programming

• Functions that call themselves are called recursive functions
• It consists of 2 parts that prevent if from being a circular solution:
  1. Base case, specifies the result of a special case
  2. General case, defines answer in terms of answer om some other input

Recursion: Example

• Factorial function:
  • Base case: 1! = 1
  • General case: n! = n * (n-1)!

def factorial(x):
    """Calculates factorial of x!
    
    Takes one integer as an input
    Returns the factorial of that integer
    """
    if x == 1:
        return x
    else:
        return x * factorial(x-1)

factorial(5)

120

Function Design Principles

• Function should have a single, cohesive purpose
  • Check if you could give it a short descriptive name
• Function should be relatively small
• Use arguments for input and return for output
  • Avoid writing to global variables
• Change mutable objects only if a caller expects it

Module Import: Example

import statistics # Import all objects from module `statistics`
from math import sqrt # Import only function `sqrt` from module `math`

fib = [0, 1, 1, 2, 3, 5]

statistics.mean(fib) # Mean

2

statistics.median(fib) # Median

1.5

sqrt(25) # Square root

5.0

Some Built-in Python Modules

Next

• Tutorial: Control flow and functions
• Assignment 3: Due at 12:00 on Monday, 11th November (submission on Blackboard)
• Next week: Data wrangling in Python