Home Week-2

PDSA - Week 1

PDSA - Week 1For PythonNumber of operation or instruction when program runsComputing gcdComputing gcd - Eliminate the listComputing gcd - Better WayComputing gcd - Euclid’s algorithmComputing PrimeComputing Primes- Other approachComputing Primes- Sufficient to check factors up to √ nException handlingClasses and objectsTimerWhy Efficiency?

For Python

https://pypod.github.io/

Number of operation or instruction when program runs

Count the number of operation or instruction executed when program runs.


1
def total(a,b):
2
    s = a + b
3
    return s


xxxxxxxxxx
5
1
n = int(input())
2
s = 0
3
for i in range(n):
4
    s = s + i
5
print(s)


xxxxxxxxxx
6
1
def total(n):
2
  s = 0
3
  for i in range(n):
4
    for j in range(n):
5
      s = s + 1
6
  return s

Identify the relationship between number of instructions and input size.

Our Goal - Want to reduce these numbers of instructions when program runs

Computing `gcd`

gcd(m, n) — greatest common divisor
- Largest k that divides both m and n
- gcd(8, 12) = 4
- gcd(18, 25) = 1
Also hcf — highest common factor
- gcd(m, n) always exists
- 1 divides both m and n
Computing gcd(m, n)
- gcd(m, n) ≤ min(m, n)
- Compute list of common factors from 1 to min(m, n)
- Return the last such common factor


xxxxxxxxxx
6
1
def gcd(m,n):
2
    cf = [] # List of common factors
3
    for i in range(1,min(m,n)+1):
4
        if (m%i) == 0 and (n%i) == 0:
5
            cf.append(i)
6
    return(cf[-1])

Computing `gcd` - Eliminate the list


xxxxxxxxxx
5
1
def gcd(m,n):
2
    for i in range(1,min(m,n)+1):
3
        if (m%i) == 0 and (n%i) == 0:
4
            mrcf = i
5
    return(mrcf)

Efficiency :- Both versions of gcd take time proportional to min(m, n)

Computing `gcd` - Better Way

Suppose d divides m and n
m = ad, n = bd
m − n = (a − b)d
d also divides m − n


xxxxxxxxxx
6
1
def gcd(m,n):
2
    (a,b) = (max(m,n), min(m,n))
3
    if a%b == 0:
4
        return(b)
5
    else
6
        return(gcd(b,a-b))

Still not efficient, for example gcd(1,1000) takes 1000 steps.

Computing `gcd` - Euclid’s algorithm

If n divides m, gcd(m, n) = n
Otherwise, compute gcd(n, m mod n)


xxxxxxxxxx
6
1
def gcd(m,n):
2
    (a,b) = (max(m,n), min(m,n))
3
    if a%b == 0:
4
        return(b)
5
    else
6
        return(gcd(b,a%b))

Can show that this takes time proportional to number of digits in max(m, n)

Computing `Prime`

A prime number n has exactly two factors, 1 and n
Note that 1 is not a prime
Compute the list of factors of n
n is a prime if the list of factors is precisely [1,n]


xxxxxxxxxx
8
1
def factors(n):
2
    fl = [] # factor list
3
    for i in range(1,n+1):
4
        if (n%i) == 0:
5
            fl.append(i)
6
    return(fl)
7
def prime(n):
8
    return(factors(n) == [1,n])

Counting primes


xxxxxxxxxx
6
1
def primesupto(m):
2
    pl = [] # prime list
3
    for i in range(1,m+1):
4
        if prime(i):
5
            pl.append(i)
6
    return(pl)

Computing Primes- Other approach

Directly check if n has a factor between 2 and n − 1


xxxxxxxxxx
6
1
def prime(n):
2
    result = True
3
    for i in range(2,n):
4
        if (n%i) == 0:
5
            result = False
6
    return(result)

Directly check if n has a factor between 2 and n//2


xxxxxxxxxx
6
1
def prime(n):
2
    result = True
3
    for i in range(2,n//2):
4
        if (n%i) == 0:
5
            result = False
6
    return(result)

Terminate after we find first factor


xxxxxxxxxx
7
1
def prime(n):
2
    result = True
3
    for i in range(2,n):
4
        if (n%i) == 0:
5
            result = False
6
            break # Abort loop
7
return(result)

Computing Primes- Sufficient to check factors up to √ n


xxxxxxxxxx
8
1
import math
2
def prime(n):
3
    (result,i) = (True,2)
4
    while (result and (i <= math.sqrt(n))):
5
        if (n%i) == 0:
6
            result = False
7
        i = i+1
8
    return(result)

Exception handling

Our code could generate many types of errors

y = x/z, but z has value 0
y = int(s), but string s does not represent a valid integer
y = 5*x, but x does not have a value
y = l[i], but i is not a valid index for list l
Try to read from a file, but the file does not exist
Try to write to a file, but the disk is full

Types of some common errors

SyntaxError: invalid syntax
Name used before value is defined - NameError: name ’x’ is not defined
Division by zero in arithmetic expression - ZeroDivisionError: division by zero
Invalid list index IndexError: list assignment index out of range

Handling exceptions


xxxxxxxxxx
10
1
try:
2
    #... ← Code where error may occur
3
except (IndexError):
4
    #... ← Handle IndexError 
5
except (NameError,KeyError):
6
    #... ← Handle multiple exception types 
7
except:
8
    #... ← Handle all other exceptions 
9
else:
10
    #... ← Execute if try runs without errors

Classes and objects

Abstract datatype

Stores some information
Designated functions to manipulate the information
For instance, stack: last-in, first-out, push(), pop()
Separate the (private) implementation from the (public) specification

Class

Template for a data type
How data is stored
How public functions manipulate data

Object

Concrete instance of template

Example


x
1
class Point:
2
  def __init__(self,a=0,b=0):
3
    self.x = a
4
    self.y = b
5

6
  def translate(self,deltax,deltay):
7
    self.x += deltax
8
    self.y += deltay
9

10
  def odistance(self):
11
    import math
12
    d = math.sqrt(self.x*self.x +
13
                  self.y*self.y)
14
    return(d)
15

16
  def __str__(self):
17
    return('('+str(self.x)+','
18
            +str(self.y)+')')
19

20
  def __add__(self,p):
21
    return(Point(self.x + p.x, 
22
                 self.y + p.y))
23

24
p = Point(3,4)
25
q = Point(5,8)
26
print(p)
27
print(p+q)

Output


xxxxxxxxxx
2
1
(3,4)
2
(8,12)

Timer


xxxxxxxxxx
32
1
import time
2

3
class TimerError(Exception):
4
    """A custom exception used to report errors in use of Timer class"""
5

6
class Timer:
7
    def __init__(self):
8
        self._start_time = None
9
        self._elapsed_time = None
10

11
    def start(self):
12
        """Start a new timer"""
13
        if self._start_time is not None:
14
            raise TimerError("Timer is running. Use .stop()")
15
        self._start_time = time.perf_counter()
16

17
    def stop(self):
18
        """Save the elapsed time and re-initialize timer"""
19
        if self._start_time is None:
20
           raise TimerError("Timer is not running. Use .start()")
21
        self._elapsed_time = time.perf_counter() - self._start_time
22
        self._start_time = None
23

24
    def elapsed(self):
25
        """Report elapsed time"""
26
        if self._elapsed_time is None:
27
           raise TimerError("Timer has not been run yet. Use .start()")
28
        return(self_elapsed_time)
29

30
    def __str__(self):
31
        """print() prints elapsed time"""
32
        return(str(self._elapsed_time))

Set recursion limit


xxxxxxxxxx
3
1
import sys
2
sys.setrecursionlimit(100000)
3
gcd(2,99999)

Calculate time for large value


xxxxxxxxxx
5
1
# 10^16
2
t.start()
3
print(678912345678912345,987654321987654321,gcd(678912345678912345,987654321987654321))
4
t.stop()
5
print(t)

Why Efficiency?

Example-

Sort all Aadhaar number
Search data from big database
Real time Gamming Problem