➡Created by H Bharath Bhat

• Contents

1. Algorithm: how to systematically perform a task

2. Programming language describes the step

3. Algorithms that manipulate information:
   • Compute numerical functions - f(x,y)
   • Reorganize data - arrange in ascending order
   • Optimization - find the shortest route

Greatest Common Divisor

gcd(m, n)

Steps

1. List out factors of m

2. List out factors of n

3. Report the largest number that appears in the list

def gcd(m, n):
    m_multiples = []
    n_multiples = []
    for i in range(1, m+1):
        if m%i == 0:
            m_multiples.append(i)
    for i in range(1, n+1):
        if n%i == 0:
            n_multiples.append(i)
    
    for i in range (0, len(m_multiples)):
        for j in range(0, len(n_multiples)):
            if m_multiples[i] == n_multiples[j]:
                gcd = m_multiples[i]
    return gcd

print(gcd(8,12))
print(gcd(18,25))


'''
Outputs
4
1
'''

• Program is a sequence of steps

• Some steps are repeated

• And some steps are executed conditionally

An algorithm for gcd(m, n)

1. Use fm, fn for list of m, n respectively

2. For each i from 1 to m, add(append) i to fm if i divides m

3. For each j from 1 to n, add(append) j to fm if j divides n

4. Use cf for list of common factors

5. For each f in fm, add f to cf if f also appears in fn

6. Return rightmost value in cf (largest value)

Better code

1. We scan from 1 to m to compute fm and again from 1 to n to compute fn

2. Instead we can scan only once
   1. For each i in 1 to max(m,n) add i to fm if i divides m and add i to fn if i divides n

Best code

1. Compare them to compute common factors cf, at one shot
   1. For each i in 1 to max(m,n), if i divides m and i also divides n, then add i to cf

2. Actually, any common factor must be less than min(m,n)
   1. For each i in 1 to min(m,n), if i divides m and i also divides n, then add i to cf

def gcd(m,n):
    multiples = []
    for i in range (1, min(m,n)+1):
        if m%i == 0 and n%i == 0:
            multiples.append(i)
    return max(multiples)

print(gcd(8,12))
print(gcd(18,25))

'''
Outputs
4
1
'''

Even more better

1. We do not require any list at all, a value can be stored in a variable

def gcd(m,n):
    for i in range (1, min(m,n)+1):
        if m%i == 0 and n%i == 0:
            gcd = i
    return gcd

print(gcd(8,12))
print(gcd(18,25))

'''
Outputs
4
1
'''

Better code than before

Can be made even more efficient by scanning backwards instead of from 1

Let i run from min(m,n) to 1

def gcd(m,n):
    i = min(m,n)
    while i > 0:
        if m%i == 0 and n%i == 0:
            return i
        else:
            i = i-1
print(gcd(8,12))
print(gcd(18,25))

'''
Outputs
4
1
'''

Euclid’s Algorithm

1. Suppose d divides both m and n, and m>n

2. Then m = a*d, n = b*d

3. So m-n = ad - bd = (a-b)*d

4. d divides m-n as well

5. So gcd(m,n) = gcd(n,m-n)

Consider gcd(m,n) with m>n
If n divides m, return n
Otherwise, compute gcd(n, m-n) and return that value

def gcd(m,n):
		# Assume m>=n [comment]
    if m<n:
        (m,n)=(n,m)
    if m%n == 0:
        return n
    else:
        diff = m-n
        return(gcd(max(n,diff),min(n,diff))) # Recursion
print(gcd(8,12))
print(gcd(18,25))

'''
Outputs
4
1
'''

• m-n must be at least 1, if it is 0 then m%n = 0, hence it returns the smaller value i.e n

Euclid’s Algorithm using while condition

def gcd(m,n):
    if m<n:
        (m,n)=(n,m)
    while m%n != 0:
        diff = m-n
        (m,n) = (max(n,diff),min(n,diff))
    return n
print(gcd(8,12))
print(gcd(18,25))

'''
Outputs
4
1
'''

Euclid’s Extended Version

Consider gcd(m,n) with m>n
If n divides m, return n
Otherwise, let r = m%n
Return gcd(n,r)

def gcd(m,n):
    if m<n:
        (m,n)=(n,m)
    if m%n == 0:
        return n
    else:
        return gcd(n,m%n)  # m%n <n, always
print(gcd(8,12))
print(gcd(18,25))

'''
Outputs
4
1
'''

While Condition

while condition:
	step 1
	step 2
	step 3

1. Don't know in advance how many times we will repeat the steps

2. Should be careful to ensure the loop terminates, eventually the condition should become false

Python and its Environment

Compiler

Translates high level programming language to machine level instructions, generates “executable” code.

Interpreter

Itself is a program that runs and directly “understands” high level programming language.

Python is basically an interpreted language

Running a Python program

Resources

• https://docs.python.org/3/tutorial/index.html

• Dive into Python3, Mark Pilgrim: https://www.diveintopython3.net

• Think Python, 2nd Edition, Allen B. Downey: https://greenteapress.com/wp/think-python-2e/

Typical Python Program

1. Interpreter executes statements from top to bottom

2. Function definitions are “digested” for future use

def function01(x,y):
		return x*y
def function02(m,n):
		return m-n
def function03(a,b):
		return a+b

statement_01
statement_02
	:
	:
	:
statement_n

3. Actual program starts from statement_01

4. Python allows free mixing of function definitions and statements

Basics of Python

Assignment Statement

• Assign a value to a name (variable)

i = 5
j = 2*i
j = j + 5 # statement that updates a value

• Left hand side is a name

• Right hand side is an expression
  • Operations in expression depend on type of value

Names, values and types

• Values have types
  • Type determines what operations are legal

• Names inherit their type from their current value
  • Type of a name is not fixed
  • Unlike C/C++/Java where each name is declared in advance with its type.

• Names can be assigned values of different values as the program evolves

i = 5 # i is int
i = 7*1 # i is still int
j = i/3 # j is float, creates float
...
i = 2*j # i is now float

• type(e) returns type of e

i = 5
j = 5.55
print(type(i))
print(type(j))

'''
Outputs
<class 'int'>
<class 'float'>
'''

• Not good style to assign values of mixed types to same names

Numeric Values

Numbers come in two flavors:

1. int - integers

   Ex: 178, -87, 0, 76

2. float - fractional numbers

   Ex: 0.1, 3.14, -0.01

• Internally, a value is stored as a finite sequence of 0’s and 1’s (binary digits, or bits)

• For an int, this sequence is read off as a binary number

• For a float, this sequence breaks up into a mantissa and exponent
  • Like “scientific” notation: 0.602 x 10^(24)

Operations on Numbers

• Normal arithmetic operations: +, -, *, /
  • Divide (/) always produces a float
  • Quotient and remainder: // and %
    • 9//5 is 1; 9%5 is 4

• Exponentiation: **
  • 3**4 is 81

• Other operations on Numbers
  • log(), sqrt(), sin(), ….
  • Built on Python, but not available by default
  • Must include math library
    • from math import *

Boolean Values: bool

• True, False

• Logical Operators: not, and, or
  • not True is False, not False is True
  • x and y is True if both of x, y are True
  • x or y is True if at least one of x, y is True

• Frequent ways: Comparisons
  • x == y, a ≠ b, z < 17*5, n>m, 19 ≥ 44*d

x = 5
y = 5
z = 8
print(x == y)
print(x == z)
print(x != z)

'''
Outputs
True
False
True
'''

x = 5
y = 5
z = 8
print(x == y and x == z)
print(x == y or x == z)
print(x == y and x != z)
print(x == y or x != z)

'''
Outputs
False
True
True
True
'''

• Example

def divides(m, n):
    if m%n == 0:
        return True
    else:
        return False

def even(n):
    return divides(n,2)

def odd(n):
    return not divides(n,2)

print(divides(12,4))
print(divides(12,5))
print(even(4))
print(even(5))
print(odd(4))
print(odd(5))

'''
Outputs
True
False
True
False
False
True
'''

Strings

• Type string, str, a sequence of characters
  • A single character is a string of length 1
  • No separate type char

• Enclose in quotes - single, double, or even triple

• Backslash can also be used to print a single quote inside a string enclosed within a single quote

print("Bharath's")
print('Bharath\'s')
print("'Bharath'")
name = '''Bharath is a "gangster's brother"'''
print(name)

'''
Outputs
Bharath's
Bharath's
'Bharath'
Bharath is a "gangster's brother"
'''

• Positions 0, 1, 2, 3,….n-1 for a string of length n
  • Eg: s = ”hello”

  0	1	2	3	4
  h	e	l	l	o
  -5	-4	-3	-2	-1

name = "bharath's"
for i in range (0,len(name)):
    print(i, name[i])
print('\n')
for i in range (-len(name), 0):
    print(i, name[i])
    
'''
Outputs
0 b
1 h
2 a
3 r
4 a
5 t
6 h
7 '
8 s


-9 b
-8 h
-7 a
-6 r
-5 a
-4 t
-3 h
-2 '
-1 s
'''

Operations on Strings

• Combine two strings: concatenation, operator +

• Concatenation (+) does not put any spaces in between by default

print('Bharath'+'is my name')
print('Bharath '+'is my name')
print('Bharath','is my name')
print(len("bharath"))

'''
Outputs
Bharathis my name
Bharath is my name
Bharath is my name
7
'''

Extracting a Substring

• A slice is a “segment” of a string

s = "hello"
print(s[1:4])
print(s[1:5])
print(s[2:])
print(s[:4])
print(s[-5:])
print(s[-4:-1])
print(s[:-1])

'''
Outputs
ell
ello
llo
hell
hello
ell
hell
'''

Modifying Strings

• Cannot update a string “in place”
  • s = “hello”, want to change to “help!”
  • s[3] = p - throws error

• Instead, use slices and concatenation
  • s = s[0:3] + “p!”

• Strings are immutable values

s = s[:3]+"p!"
print(s)

'''
Output
help!
'''

Lists

• Sequences of values
  • factors = [1, 2, 3, 4]
  • names = [’bharath’, ‘bhavya’, ‘sharath’]
  • Type need not be uniform
    • mixed = [1, 'bharath', 2, 'sharath’]
  • Extract values by position, slice, like str
    • factors[3] is 4, mixed[0:2] is [2, ‘sharath’]
  • Length is given by len()
    • len(names) is 3

• For str, both a single position and a slice return strings

s = "hello"
print(s[0]) # returns a string itself
print(s[0:1]) # returns a string itself

'''
h
h
'''

• For lists, a single position returns a value, a slice returns a list

mixed = [1, 'bharath', 2, "sharath"]
for i in range(0, len(mixed)):
    print(mixed[i])
print(mixed[1:])
print(mixed[:])

'''
Outputs
1
bharath
2
sharath
['bharath', 2, 'sharath']
[1, 'bharath', 2, 'sharath']
'''

Nested List

• Lists can contain other lists too

mixed.append([2,3])
print(mixed)
mixed.insert(2, ['hrushik', 'ramya']) # list.insert(index, element)
print(mixed)

'''
Outputs
[1, 'bharath', 2, 'sharath', [2, 3]]
[1, 'bharath', ['hrushik', 'ramya'], 2, 'sharath', [2, 3]]
'''

for i in range(0, len(mixed)):
    print(mixed[i])

'''
Outputs
1
bharath
['hrushik', 'ramya']
2
sharath
[2, 3]
'''

print(mixed[2][0])
print(mixed[2][0][1])
print(mixed[2][0][3:])

'''
Outputs
hrushik
r
shik
'''

• Unlike strings, lists can be updated in place

mixed[2][0] = 'hrasika'
print(mixed)
mixed[2] = ['bengaluru', 'chennai', 'mumbai']
print(mixed)

'''
Outputs
[1, 'bharath', ['hrasika', 'ramya'], 2, 'sharath', [2, 3]]
[1, 'bharath', ['bengaluru', 'chennai', 'mumbai'], 2, 'sharath', [2, 3]]
'''

• Lists are mutable, unlike strings

sample = [0, 1, 2, 3]
sample[1] = 2
print(sample)

'''
Outputs
[0, 2, 2, 3]
'''

List Operations

• We can add elements to a list using append() and extend()

• Remove elements using remove() or pop()

• Sort and reverse lists using sort() and reverse()

sample = [3, 1, 4, 1, 5, 9]
sample.append(2)
sample.extend([6, 5])
sample.remove(3) # removes the first occurence in the list
sample.pop()
sample.sort()
sample.reverse()
sample[2] = 'n'
sample.extend([3,4,5]) # list must always be passed in case of extend method
print(sample)

'''
Outputs
sample:			             [3, 1, 4, 1, 5, 9]
sample.append(2):	       [3, 1, 4, 1, 5, 9, 2]
sample.extend([6, 5]):	 [3, 1, 4, 1, 5, 9, 2, 6, 5]
sample.remove(3):	       [1, 4, 1, 5, 9, 2, 6, 5]
sample.pop():		         [1, 4, 1, 5, 9, 2, 6]
sample.sort():		       [1, 1, 2, 4, 5, 6, 9]
sample.reverse():	       [9, 6, 5, 4, 2, 1, 1]
sample[2] = 'n'		       [9, 6, 'n', 4, 2, 1, 1]
sample.extend([3,4,5])   [9, 6, 'n', 4, 2, 1, 1, 3, 4, 5]
'''

• list1.append(value) - extends the list by a single element passed in the parantheses

• list1.extend([list]) - extends list by a list of values

• remove() removes only the first occurrence in the list

• Safely removes ‘n’ from list - sample

if 'n' in sample:
    sample.remove('n')
print(sample)

'''
Output
[9, 6, 4, 2, 1, 1, 3, 4, 5]
'''

• Remove all occurrences of elements in the list

while 4 in sample:
    sample.remove(4)
print(sample)

'''
Output
[9, 6, 2, 1, 1, 3, 5]
'''

• What happens when we assign names?

x = 5
y = x
x = 7
print("x: ",x)
print("y: ",y)

'''
Outputs
x:  7
y:  5
'''

• Does assignment copy the value or make both names point to the same value.

• For immutable value, we can assume that assignment makes a fresh copy of a value.
  • Values apply for all types

• Updating one value does not effect the copy

• For mutable values, assignment does not make a fresh copy.

list1 = [1,2,3,4]
list2 = list1
list1[2] = 'n'
print(list1)
print(list2)

'''
Outputs
[1, 2, 'n', 4]
[1, 2, 'n', 4]
'''

• What is list2[2] now?
  • list2[2] is also ‘n’

• list1 and list2 are the same names for the same list.

Copying list

• How can we make a copy of a list?

• A slice creates a new (sub) list from the old one

l[:k] is l[0:k], l[k:] is l[k:len(l)]
l[:] == l[0:len(l)]

• Omitting both end points gives a full slice

lista = [5, 6, 7, 8, 9]
listb = lista[:]
lista[2] = 'm'
print(lista)
print(listb)

'''
Outputs
[5, 6, 'm', 8, 9]
[5, 6, 7, 8, 9]
'''

• Concatenation produces a new list

list1 = [1,3,5,7]
list2 = list1
list1 = list1[0:2] + [7] + list1[3:]
print(list1, list2)

'''
Output
[1, 3, 7, 7] [1, 3, 5, 7]
'''

Digression on equality

lista = [5, 6, 7, 8, 9]
listb = lista
listc = listb
listc[2] = 'n'
print(lista,listb, listc)

'''
Outputs
[5, 6, 'n', 8, 9] [5, 6, 'n', 8, 9] [5, 6, 'n', 8, 9]
'''

lista = [5, 6, 7, 8, 9]
listb = [5, 6, 7, 8, 9]
listc = listb
print(lista == listb)
print(lista == listc)
print(listc == listb)
print(lista is listb)
print(lista is listc)
print(listc is listb)
listc[2] = 'n'
print(lista,listb, listc)

'''
Outputs
True
True
True
False
False
True
[5, 6, 7, 8, 9] [5, 6, 'n', 8, 9] [5, 6, 'n', 8, 9]
'''

Concatenation of strings

listd = lista + listb
listd + [8]
print(listd)

'''
Outputs
[5, 6, 7, 8, 9, 5, 6, 'n', 8, 9]
'''

• Concatenation ‘+’ always produces a new list

list1 = [1, 2, 3, 4]
list2 = list1
list1 = list1 + [9]
print(list1, list2)

'''
Outputs
[1, 2, 3, 4, 9] [1, 2, 3, 4]
'''

Execution of typical python program

def function01(x,y):
		return x*y
def function02(m,n):
		return m-n
def function03(a,b):
		return a+b

statement_01
statement_02
	:
	:
	:
statement_n

• Interpreter executes the program from top to bottom

• Function definitions are ‘digested’ for future use only.

• Actual computation starts from statement_01.

Control Flow

• Need to vary computation steps as values change

• Control flow determines order in which statements are executed
  • Conditional Executions
  • Repeated Executions - loops
  • Functional Definitions

Conditional Execution

1. If Statement

if m%n != 0:
	(m, n) = (n, m%n)

• Second statement is executed only if the condition m%n ≠ 0 is True

• Indentation demarcates body of if - must be uniform

if condition:
	statement_01 # executes conditionally
	statement_02 # executes conditionally
statement_03   # executes unconditionally

2. Alternative Execution

if m%n != 0:
	(m, n) = (n, m%n)
else:
	gcd = n

• else is optional

Shortcuts for conditions

• Numeric value 0 is treated as false

• Empty sequence “”, [] is treated as false

• Everything else is True

3. Multiway Branching, elif

if x == 1:
    y = f1(x)
else:
    if x == 2:
        y = f2(x)
    else:
        if x == 3:
            y = f3(x)
        else:
            y = f4(x)

• To avoid this we use else if

if x == 1:
    y = f1(x)
elif x == 2:
    y = f2(x)
elif x == 3:
    y = f3(x)
else:
    y = f4(x)

Loops: Repeated actions

1. for loop

• Repeat something a fixed number of times

list = [1, 2, 3, 4]
for i in list:
	y = y*i
	z = z+1 

• Repeating n times:
  • range(0, n) generates sequence 0, 1, 2,….., n-1
  • range(i, j) generates sequence i, i+1, i+2,…, j-1

def flist(n):
    flist = []
    for i in range(1, n+1):
        if n%i == 0:
            flist = flist + [i]
    return flist

print(flist(9))

'''
Outputs
[1, 3, 9]
'''

• More about range
  • range(i, j) produces a sequence from i, i+1, i+2, ..., j-1
  • ranje(j) automatically ranges from 0; 0, 1, 2, …, j-1
  • range(i, j, k) increments from k; i, i+k, …, i+nk
    • Stops with n such that i+nk < j ≤ i+(n+1)k
  • Count Down: Make n negative
    • range(i, j, -1), i>j, produces i, i-1, i-2, …, j+1
  • If k is positive and i≥j, it will generate empty sequence
  • If k is negative and i≤j
  • If k is negative, stop before j
    • range(12, 1, -3) produces 12, 9, 6, 3
  • Compare the following
    • for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
    • for i in range(0, 10):
  • Can convert range() into list using list()

  list(range(0,5))
  
  '''
  Output
  [0, 1, 2, 3, 4]
  '''

2. while conditional loop

• Often we don’t know the number of repetitions in advance

• while is executed if the condition evaluates to True

• After each iteration check the condition again

• Repeat based on condition

while condition:
	statement_01
	...
	statement_02

• for and while:
  • primeUptoNo()
    • Know we have to scan from 1 to n, use for
  • nprimes()
    • Range to scan not known in advance, use while

Function Definition

def f(a, b, c):
	statement_01
	statement_02
	...
	return (v)

• Function name(arguments/parameters)

• Body is intended

• return() statement exists and returns a value

Passing values to functions

• Argument value is substituted for name

def power(x, n):
    ans = 1
    for i in range(0, n):
        ans = ans*x
    return ans
print(power(3, 5))

'''
Outputs
243
'''

• Same rules apply for mutable, immutable values
  • Immutable values will not be affected at calling point
  • Mutable values will be affected

def update(l, i, v):
    if i >= 0 and i < len(l):
        l[i] = v
        return True
    else:
        return False

ns = [3,11,12]
z = 8
print(update(ns,2,z),ns) # ns is [3, 11, 8]
print(update(ns,4,z),ns) # z remains 8

'''
Outputs
True [3, 11, 8]
False [3, 11, 8]
'''

• Return value may be ignored

• If there is no return(), function ends when last statement is reached

Scope of names in a function

• Names within a function have local scope

def name(x):
    n = 17
    return x

n = 7
v = name(28)
print(n, v) # Name x inside the function is seperate from x outside

'''
Outputs
7 28
'''

Defining Functions

• A function must be defined before it is invoked

• A python program is executed from top to bottom

Recursive Functions

• A function can call itself - recursion

def factorial(n):
    if n<=0:
        return 1
    else:
        val = n*factorial(n-1)
        return val

print(factorial(5))

'''
Outputs
120
'''

Examples

• Prime Finder: Finds whether the number is prime or not.

def primeFinder(n):
    if n == 1:
        return 'non-prime'
    else:
        factorlist = []
        for i in range(1,n+1):
            if n%i == 0:
                factorlist.append(i)
        if len(factorlist) > 2:
            return 'non-prime'
        else:
            return 'prime'
    
print(primeFinder(9))
print(primeFinder(31))
print(primeFinder(69)) 
print(primeFinder(11))
print(primeFinder(121))
print(primeFinder(1))

'''
Output
non-prime
prime
non-prime
prime
non-prime
non-prime
'''

• Prime upto n: List all primes below a given number

def primeUptoNo(n):
    primelist = []
    for i in range(1,n+1):
        if primeFinder(i) == 'prime':
            primelist.append(i)
    return primelist

print(primeUptoNo(13))
print(primeUptoNo(8))
print(primeUptoNo(30))

'''
Outputs
[2, 3, 5, 7, 11, 13]
[2, 3, 5, 7]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
'''

• First n prime numbers: List the first n prime numbers

def nprimes(n):
    primelist = []
    count = 0
    i = 1
    while count < n:
        if primeFinder(i) == 'prime':
            count += 1
            primelist.append(i)
        i=i+1
    return primelist
                
print(nprimes(9),len(nprimes(9)))
print(nprimes(20),len(nprimes(20)))

'''
Outputs
[2, 3, 5, 7, 11, 13, 17, 19, 23] 9
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] 20
'''