Transcript check digit - Directory Listing

Programming for Engineers in Python
Recitation 13
Plan
 Error detection
 Luhn Algorithm
 RAID
 Data structures
 Queue
 Stack
 Nested lists
 Matrices
 Recursion
 Even and Odd
 Recursive directory tree walk
2
Teaching Survey
 Please answer the teaching survey:
https://www.ims.tau.ac.il/Tal/
 This will help us to improve the course
 Deadline: 4.2.12
3
Checksums: Check Digit
 A check digit is a form of redundancy check used




4
for error detection
It consists of a single digit computed from the other
digits in the message.
Detect simple errors in the input of a series of digits
Detect a single mistyped digit or some permutations of two
successive digits.
http://en.wikipedia.org/wiki/Check_digit
Luhn Algorithm – “mod 10” Algorithm
 Simple algorithm
 Used to validate:
 Credit Card numbers
 IMEI numbers (GSM SIM card identifiers)
 Israeli ID Cards
 Checks for mistyping errors – not for forgery!
 Designed by Hans Peter Luhn while working in IBM during
the 1950s
 http://en.wikipedia.org/wiki/Luhn_algorithm
5
Luhn: Calculating the check digit
 Double every second digit, starting from the last
 Sum the digits of the doubling product
 Sum the other digits as well
 Multiply results by 9 (67*9=603)
 Return results mod 10 (603%10=3)
6
Luhn: Checking number validity
 Do the same process, add the check digit, and the result
should be 0 mod 10
 Code: Luhn.py
7
XOR – Exclusive Or
 Logic operator on 2 arguments
 “One or the other but not both“
 Results in True:
 If one of the arguments is True and one if False
 Returns False:
 If both arguments are True or both arguments are False
 Examples:
 I’m happy XOR I’m sad
 It’s raining XOR it’s not raining
 http://en.wikipedia.org/wiki/Exclusive_or
8
XOR – Exclusive Or
 “One or the other but not both“
 Bitwise operation (Python ^):
 Returns 1 if the bits are different, 0 if bits are identical
 1 XOR 1 = 0
 1 XOR 0 = 1
 0 XOR 1 = 1
 0 XOR 0 = 0
 1110 XOR 1001 = 0111
 Equivalent to addition without carry
 Useful to calculate parity bit:
 1 XOR 1 XOR 0 XOR 1 XOR 0 = 1
9
RAID Parity
 RAID = redundant array of independent/inexpensive disks
 Storage unit combining multiple drives
 One drive serves as the parity drives and allows the recovery
of lost data
 http://en.wikipedia.org/wiki/RAID#RAID_Parity
10
RAID Parity
Data is written to drives #1-4
Drive #6 is updated to store the parity of drives
#1-4:
00101010 XOR 10001110 XOR 11110111 XOR 10110101 = 11100110
11
RAID Parity
When drive #3 fails, the data can be
recovered by using the same parity
operation with drives #1,2,4,6
00101010 XOR 10001110 XOR 11100110 XOR 10110101 = 11110111
Recovered data is stored in drive #5, the
Hot Spare
When drive #3 is fixed or replaced, it will
be the new Hot Spare
12
RAID in Python
 We will see a simplistic implementation
 Our ‘RAID’ is a matrix of integers
 We will be able to declare a matrix row as ‘faulty’ without
losing its data
 Code: RAID.py
13
Data Structure: Queue
 A Queue is a FIFO data structure
 Items enter in the bottom of the queue and are served from
the top of the queue
 Like standing in line at the bank
 Useful for many applications:
 Phone calls queue in call center or helpdesk
 Passing “tasks” from GUI to computing process
 Code: Queue.py
14
Queue Class
class Queue:
def __init__(self):
self.data = [ ]
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop(0)
15
Data Structure: Stack
 A Stack is a LIFO data structure
 Items enter in the top of the queue and are served from the
top of the queue
 Like a pile of dirt clothes…
 Useful for many applications:
 Parsing hierarchical data structures like XML or HTML
 Towers of Hanoi
 Quicksort
 All we do is change the pop method of Queue!
16
Stack Class
class Stack:
…
def pop(self):
return self.data.pop(-1)
17
Flatten Lists
 Assume that we have a hierarchal categorization of objects.
For example:
Fruit
Food
Red
Yellow
Cherry
Strawberry
Banana
Milk
Milki
Milkshake
18
Flatten Lists
 This hierarchy is represented in nested lists as:
['Food',
['fruit', ['Red','[Cherry','Strawberry']],
['Yellow',['Banana']],
['Milk', ['Milki','Milkshake']]
]
 We want to flatten this structure so that all items appear in
one list
['Food', 'fruit', 'Red', 'Cherry', 'Strawberry', 'Yellow', 'Banana',
'Milk', 'Milki', 'Milkshake']
19
Flatten Lists - Code
def flatten(lst):
print lst
flat_lst = [ ]
for x in lst:
if isinstance(x, list):
flat_lst.extend(flatten(x))
else:
flat_lst.append(x)
return flat_lst
20
Nested Lists
 A list of lists
 Example – matrix
 Matrix multiplication: 𝐴 ⋅ 𝐵 𝑖,𝑗 =
𝑘 𝐴𝑖,𝑘
⋅ 𝐵𝑘,𝑗
def mult(A,B):
n = len(A)
k = len(B)
m = len(B[0])
if len(A[0]) != k:
raise ValueError("Matrices must be of appopriate sizes")
C = [ [None]*m for x in range(n)]
for i in range(n):
for j in range(m):
C[i][j] = sum( [ A[i][x]*B[x][j] for x in range(k) ] )
return C
21
Nested Lists
22
>>> A = [ [1,1], [1,0] ]
>>> B = [ [0,1], [1,1] ]
>>> print_matrix(A)
11
10
>>> print_matrix(B)
01
11
>>> print_matrix(mult(A,B))
12
01
def print_matrix(M):
for row in M:
for entry in row:
print entry,
print
print
Simple Recursion Example
 Check if a number is even or odd
23
def even(x):
if x == 0:
return True
else:
return odd(x - 1)
def odd(x):
if x == 0:
return False
else:
return even(x - 1)
http://en.wikipedia.org/wiki/File:Screenshot_Recursion_via_vlc.png
http://paulbutler.org/archives/tail-recursion-in-python/
Simple Recursion Example
>>> even(100)
True
>>> even(101)
False
>>> even(1000)
RuntimeError: maximum recursion depth exceeded
 This was expected…
24
Recursion – find files
 We want to find all mp3 files on the disk
 We’ll do a recursive search on the disk for such files
 First some os commands:
 os.listdir(dir): returns all files and directories in the directory dir
 os.path.isdir(dir): returns True is dir is a name of a directory, False
otherwise
 os.path.join: joins a list of directory names and a file name to a path,
separating the names with a separator suitable for this OS
Windows: c:\examples\python
Unix: /examples/python
25
Recursive search on directory tree
 Recursion base: files
 If it’s an mp3 file, we return its name
 Otherwise we don’t
 Recursion step: directories
 We call the function for each subdirectory and merge the
results
26
http://www.mediacollege.com/internet/images/tree.gif
Recursive search on directory tree
 Recursion base
def find_files(location, postfix=‘.mp3’):
if not isdir(location): # not a directory – a file
if location.endswith(postfix):
return [location]
else:
return [ ]
27
Recursive search on directory tree
 Recursion step
else:
results = []
for name in listdir(location):
new_path = join(location, name)
results += find_files(new_path, postfix)
return results
 We’ll now run the function on this computer
 Code: find_files.py
28
Exam Stuff
 Preparation class
 Yoav: Wed. 22.2, 13-15, Room 102 TOCHNA
 Noga: Thu. 23.2, 10-12, Room 020 Auditorium
 Send questions via email before 20.2
 We will go over the sample exam
 Exam material – everything from lectures, recitations, exercises
 You may bring a double sided A4 page, hand-written by yourself,
no photo-copying – write on it whatever you want
 This will be your very own Python reference in the future
29