[programming-0] Quick Python

Short tutorial on Python programming language. The contents are taken from these sources MIT OCW[2] and the book Introduction to Computation and Programming using Python[1] by John V. Guttag. To understand this document you are expected to know a programming language well.

Comment
#single line comment
"""
multi line comment """

Basic Operations
+, -, / %, *
2 ** 3 // 2 to the power 3

Variable assignment
a = 3

Global variable

global variable_name //creates entry for this identifier in outermost stack frame

Conditionals
a or b
a and b
not a
a == b
a != b

Program flow
if condition:
code block
elif condition:
code block
else:
code block

Loop
while condition:
code block

for var in range(0, 10):
code block

Break execution of loop
break

Continue to next iteration
continue

Function 
Declaration
def functionName(arg1, arg2):
code block

Call
functionName(param1, param2)

Tuple
tuples are immutable
t1 = (1, 2, 3)
t2 = (4, 5, 6)

access element
t1[2]
t1[2:3]

joining tuples
t3 = t1 + t2 //t1 and t2 are immutable so there is no side effect, meaning t1 and t2 will be unmodified

assign multiple variables using tuple
x, y, z = (0, 1, 2) //x <- 0, y <- 1, z <- 2

List
Mutable, meaning an element can be added or removed

Initialize
lst = [1, "saif", 2.3] //can hold different type of elements
lst = [x for x in range(0, 10)]

Element Access
lst[i]

Insert
l.append(element)

Traverse
for i in range(len(L)):
print(L[i])

Useful methods
append(e) //adds e at the end of the list
count(e) //occurances of e
insert(index, element)
extend(list2) //inserts all elements of list2 to this list
remove(e)
index(e)
pop(i)
sort()
reverse()

cloning list
list(l)
copy.deepcopy()


String 
strings are immutable

Initialize
str = "abc"

Methods
str.count(s2)
str.find(s2)
str.rfind(s2) //find the first occurance from backward
str.index(s2)
str.rindex(s2)
str.lower()
str.replace(old, new)
str.rstrip() //remove white space from right
str.split(delimeter)

Dictionary
Initialize
dict = {k1:v1, k2:v2, k3:v3}

Insert
dict[key] = value

Access
value = dict[key]


Delete
del dict[key]

Iterate
for key in dict:

Useful methods
length : len(dict)
keys: dict.keys()
values: dict.values()
element exists: key in dict
default value to return: d.get(key, default_value)  //returns default value if key is not present

Common methods for String, List, Tuple
access i th element: seq[i]
length: len(seq)
merge: seq1 + seq2
create multiple: n * seq //"abc"*3 -> "abcabcabc"
subsequence: seq[start:end]
element exists: e in seq
element does not exist: e not in seq
traverse: for e in seq:

Useful methods for objects
append(e) //adds e at the end of the list
count(e) //occurances of e
insert(index, element)
extend(list2) //inserts all elements of list2 to this list
remove(e)
index(e)
pop(i)
sort()
type()
isInstance(object, ClassName)

File

Writing
file = open("filename", "w") // for append "a", for reading "r"
file.write(line)
file.close()

Reading
file = open("filename", "r")
for line in file:
print(line)
file.close()

Writing code in modules
file name: file1.py
var1 = 2
var2 = 3
def method1:
print "hello"

file name: b.py
import file1

print file1.var1
file1.method1()

Exception Handling

Handle exception
try:
    result = a / b

except ErrorName0:
    codeBlock
except (ErrorName1, ErrorName2):
    codeBlock
except: # default case
    codeBlock

Raise Exception
raise ExceptionName(argument)
raise ValueError('Bad Value You Provided!')

Assertion
assert booleanExpression
assert booleanExpression, arguments

assert temperature > 80, "too hot" #if temperature gets more than 80, the message will be printed with error message

Class
class ClassName(ExtendClass):
    classVariable = 0
    def __init__(self):
        self.instanceVariable = 8
    def __lt__(self, other):
        #compare with another object
    def __str__(self):

    def otherMethods(self, arg0, arg1):

Instantitate
a = ClassName()

Yield
list = [1, 2, 3 ,4]

def yield_one_by_one():
     for elem in list:
         yield s
for elem in yield_one_by_one():
         print(elem)

[1] https://www.amazon.com/exec/obidos/ASIN/0262529629/ref=nosim/mitopencourse-20

[2] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/index.htm

[np-hardness-0] P, NP, NP-Complete and NP-Hard

This post depicts what I have learnt from my favorite teachers. All the idea I have borrowed from their classes. I gratefully thank Dr. Demaine and Dr. Fuentes for their great course materials [1], [2].

Polynomial
If you raise a non-negative positive number to the power of a variable, you get a polynomial. So x ^ 0, x^1, x^3 are all polynomials but x ^ -1 or x ^ 3.4 is not polynomials.

P
If an algorithm solves a problem of input size n in n ^ c steps where c is a non-negative integer, then that is is polynomial time algorithm.
Example:
bubble sort algorithm O(n^2)
merge sort algorithm O(nlogn) [it is less than a polynomial n^2]
Djkastra's algorithm to find single-source shortest path O(V+E) [V = vertices, E = Edges]

NP (Non Deterministic Polynomials)
An algorithm exponential problem if for input size n, it takes constant ^ n time solve the algorithm. The whole universe has 10 ^ 80 fundamental particles. So, for an exponential algorithm, with input size 80, it might not be possible to solve the problem if you turn all the fundamental particles into a computer.
An exponential algorithm would search all the possible solutions to find a problem. Lets talk about the knap-sack problem. Basically, you are given a bag and a list of items. The bag has a maximum capacity. You know the weight and values of different items. Here is a sample example input

Item Weight Value

    1          6        2

      2          2         4  

      3          3         5

Bag Capacity 6

 Your task is to fill the bag with maximum value items. A usual computer would iterate through all the possible subsets that can be generated from n items which is 2^n. The following picture gives idea how a usual computer would solve the problem.

001 at the end of the recursion means, it is checking the possibility where it will not take item1 and 2 but will take item3.

If somehow we have a non-deterministic computer, that knows what do with each item, we can solve the problem in linear time. As you can see in the picture. As soon as it looks at the item1, the algorithm just knows it will not take it, as soon as it looks at item 2 and 3, it knows it should take these items. Those problems that a non-deterministic computer can solve in polynomial time are called NP problem.

NP Complete
NP Complete algorithms are those that checks exponential number of solutions. Each solution should be solved in polynomial time. These are considered the hardest NP problems. Example can be knapsack problem, traveling salesman problem.

NP Hard
NP hard problems consists of problems from NP Complete problems and contains all other problems. Most of NP Hard problems are unsolvable. For example Alan Touring's Halting problem.

The Diagram of computational hardness is shown in below.

References

[1] Dr. Erik Demaine's Lecture from MIT

[2] Dr. Olac Fuentes's Lecture at UTEP CS-2302

[algorithms-1] An application of divide and conquer: Find square root

Problem: Find square root of positive integer, k

Naive:

1. step = 0.001
2. epsilon = 0.01
3. guess = 0.0
4. 
   
5. while abs(guess ** 2 - k) > epsilon:
1. guess += step
6. print("square root of ", k, " is ", guess)

The naive approach described above takes a lot of time to complete. the bigger k is, the more time it takes to compute the square root.

Divide search space each time:

1. epsilon = 0.001
2. min = 0
3. max = k
4. guess = (max + min) / 2
5. while abs(guess ** 2 - k) > epsilon:
1. if guess ** 2 > k:
1. max = guess
2. else:
1. min = guess
6. print("square root of ", k, " is ", guess)

this time we are attempting to find the square root of k with a help of a boundary. with each iteration we are cutting the boundary in half. For k = 100, it took the program 57 iterations to find a good guess.

Divide error at each iteration:

We will be using Newton-Raphson method for finding the square root. We will need bit of math to do the magic. lets define a function f(x) = x ^ 2 - k, we want to find a value of x where f(x) = 0.

1. f(x) = x ^ 2 - k
2. x ^ 2 = k
3. x = sqrt(k)

 We will begin finding the square root of k with a guess, and in the next iteration, we will try to improve our guess. f'(x) is the first derivative, in our case, f'(x) = 2x.
lets say our next guess is x1 and we want f(x1) = 0. we know that,

1. f'(x) = (f(x1) - f(x)) / (x1 - x)
2. f'(x) = -f(x) / (x1- x)     [since f(x1) = 0]
3. x1 - x = - (f(x) / 2x)      [f'(x) = 2x]
4. x1 = x - (f(x) / 2x) 

we can say error = x1 - x, and from line 3, at each iteration we are dividing the error by 2 with each iteration. At line 4, we get the equation to update next guess x1, from previous guess x.

Lets write the program and run it.

1. epsilon = 0.01
2. guess = k/2.0
3. 
   
4. while abs(guess ** 2 - k) >= epsilon:
5.     guess = guess - (((guess**2) - k)/(2*guess))
6. 
   
7. print("square root of ", k, " is ", guess)

 for k = 10,000 the program takes only 9 iterations. 

Compare this logic to divide and conquer of the search space, 57 iterations and naive 100,000,000 iterations.

Source :
[1] mit lecture on square root using newton raphson
[2] intro to computation using python, mit ocw
[3] intro to computation using python. amazon