Computer Science 02

We will now look at Python, as we know previously as an Interpreted Programming Language.

A popular IDE (Integrated Development Environment) for Python is actually IDLE. IDLE consists of:
1) Text Editor - A place where the program can be typed and then sent to the Shell.
2) Shell - The actual environment that the Python code is interpreted.
3) Debugger - Useful for debugging, but most people use print statements.

Everything in Python is considered an Object. The Python code itself can be an Object. Each object has a Type. The Type determines what kind of object it is and what can we do with it.

Types can be two kinds:
1) Scalar - These are the primitive types of the programming language. They are indivisible types.
2) Non-scalar - Things that are divisible, for example, String, which can be divided into smaller 'str' of many chars.

The most common Scalar Types we work with are:
1) int - A real number.
2) float - An approximation of a real number.
3) bool - A true or false value.
4) NoneType - Representing a null.

An example of a Non-Scalar type is:

str - A string of characters.

In Python, we can type the literals (e.g. 3, 'a', '5.6) into the Shell and it would return that value. To check the type of a literal, we can use the type() function as such:
type(3)

This would tell us that 3 is an 'int' type.

Literals by themselves are useless. We cannot do much with it. What we can do, however, is to chain them together using Operands (values) and Operators to form Expressions.

In Python, when we deal with division, it is important to use floating point numbers. If we use "+" between two integers, 5+5, the "+" sign will act as an addition. If we use "+" between 'a' and 'b', we would get 'ab', because the "+" would act as concatenation when dealing with 'str'. This is because "+", like many other Operators, is Overloaded (dependent upon the types and parameters given to it).

We can do manual conversion as such, which is called Type Casting:
1) 'a'+str(3) gives you 'a3'
2) int(2.1) would truncate the float into an integer value of 2.

A Program in the Python sense is a synonym to a Script.

When typing a literal into the Shell, it prints the value directly to the screen. When things are executed in a Program, however, it will not be printed unless we use the print() command.
print 5

In order for things to work, it is important for us to have Variables. A Variable in Python is simply a name for an Object. To bind a Variable to an Object, we use the Assignment:
x=5

This assigns ("=") the int Object of value 5 to the Variable x.

The Function print() allows us to output things. We'll need to get inputs, and there are two types of input:
1) Raw Input (this is the only type that exists in Python 3.0)
2) Input

Raw Input always interprets what the user types as a 'str' type. We would need to do Type Casting:

x=int(input("Please enter an integer: "))
print("You entered "+str(x)+".")

The simplest programs are Straight Line Programs. Straight Line Programs are Programs where every line is computed exactly once, with no conditions or loops (which are referred to as "tests").

Conditional Statements are the simplest "tests". A conditional statement comprises of:
1) if
2) else
3) elif

A program where Conditional Statements are implemented is called a Branching Program. In a Branching Program, each statement is executed the most once.

In conditional statements, the indentation is extremely important. This is how a simple conditional statement is implemented:

x=int(input("Enter an integer: "))
if x%2==0:
    print("Even")
else:
    print("Odd")

Programs are intended to be readable, and by enforcing this, Python actually ensures some sort of code home-keeping.

Finally, we look at a Looping Construct which allows us to do Iterations. When we do this, we'll be able to create a Turing Complete Program.

Whenever we write a loop, we should have either an Incrementing or a Decrementing Function. This allows the loop a guarantee to exit.

The properties of a Decrementing Function is as such:
1) It will map a set of program variables to an 'int'.
2) It starts with a non-negative number.
3) The loop terminates when the value of the variable is <= 0.
4) It is decreased each time through the loop.

In a loop as seen here, there is in fact a Decrementing Function:

while a<25:
    a+=1

Even though all we can see is an Increment here, we can derive the Decrementing Function of:
25-a

Loops allow us to do something known as Exhaustive Enumeration, which we usually refer to as Bruteforce.

The for loop in Python is as such:

for x in range(0,25):
    instructions

In this case, range(0,25) actually creates a tuple with a sequence starting from 0 to 24.

Approximation in computing is finding a number that is accurate enough. It does not need to be perfect, but it must be close enough for our use. For example:

y^2=x+-epsilon

Where epsilon is the degree of error acceptable.

We would then be able to come up with a slow converging approximation algorithm as such:

x = 123
epsilon = 0.01
ans = 0
while abs(ans**2-x)>=epsilon and ans<=x:
    ans+=0.00001
print(ans," is close to sqrt of ",x)

The program is extremely dependent on size of the number given to test, and the maximum number of times it can loop can be calculated by x/0.00001.

A more effective algorithm exists to solve this problem. It is called the Bisection Search. It can be implemented by cutting the search space in half after each iteration. The worst case would be log(x) where x is the number of possible value of answers.

In this method, we first define the possible range of answers. We then try to guess the answer from the middle of the range. We then check if the answer when put through the formula gives us an answer near enough to what we want. If it's higher, then we search for a lower number. If it's lower, we search for a higher number. It is implemented as such:

x=5;
epsilon=0.00000001;
upperBound=x;
lowerBound=0.0;
ans=(lowerBound+upperBound)/2.0;
while abs(ans**2-x)>epsilon:
    if ans**2 > x:
        upperBound=ans;
    else:
        lowerBound=ans;
    if ans==(lowerBound+upperBound)/2.0:
        break
    else:
        ans=(lowerBound+upperBound)/2.0
    print(ans)
if abs(ans**2-x)>epsilon:
    print("Converged at",ans,"without meeting epsilon specifications of",epsilon)
    print("Resultant error is",ans**3-x)
else:
    print("Converged at",ans)

This Program does smart guesses at a range of values you give it. It terminates when it has converged to an answer or it's failed. However, this assumes that the answer lies between 0 to x, which means that for problems where the answer is outside this range, this could not solve it. That is a flaw of this method.

An example to observe this problem is when we try to search for numbers less than 1.0. For example, 0.5's square root is 0.707107, and if we look at the search space of 0 to 0.5, we'll never find it! We then observe this pattern that for every number that is less than 1, the highest answer is 1.0. Therefore, we can see that for the upper bound, we cannot have it less than 1. We can change our upperBound statement as such:

upperBound=max(x,1.0)

This could take the value of x, or 1.0, whichever is higher.

We typically want programs to do things with minimal coding. A smaller program is more efficient than a larger program who can do the same thing.

We can use Functions to help shorten code. A Function is something that provides:
1) Decomposition - It allows us to break our program up into modules. An example of a module is a Function and a Class. Modules should be self-contained and reusable.
2) Abstraction - Suppresses details that the programmer does not need to see. This allows the programmer to focus on what it does.

A simple function could be as such:

def accurateEnough(x, y, epsilon):
    return abs(x-y)<=epsilon

In order to use this Function, we invoke it as such:

print(accurateEnough(1,2,1))

Note that you must invoke this function below where it's been defined or it would not work.

A Function can contain:
1) Formal Parameters - are the names x, y and epsilon. You can use x in the main code and it would have nothing to do with the parameters used in the function, because it is self-contained. This is because upon entry of a function, a new Scope is created. A Scope is a mapping of names to objects. The parameter passed into the function during its call is called the Actual Parameter.
2) Return - It is a statement that causes the Function to return a value to wherever it is called. If no Return is specified, then the NoneType is returned.
3) Assert - The assert statement takes a bool value (resulting from a bool, expression or function) and stops the function if it evaluates to False, otherwise it continues.

We can create a more robust function with assert as such:

def accurateEnough(x, y, epsilon):
    assert epsilon>=0
    return abs(x-y)<=epsilon

This ensures that epsilon is a non-negative value before it continues.

What happens when we run a program:
1) The Interpreter will build a Scope, and it would find Object it sees in sequence and assigns the value of it to the Name (the Object can be a Function or a Variable, etc.).
2) If a Function is invoked, then the Interpreter would create a new Scope for it and begin executing it as in Step 1.
3) This will continue till the program reaches the end.

Each Scope is also called a Stack Frame. When we start the Program, we begin with the Main Scope. Then as we progress into Functions, we'll have Scopes adding to the top of the Stack. When we're done with the Function, its Scope gets popped from the top, and we return to the Scope of the previous Function or the Main Scope. We would eventually end up again with the Main Scope. This is because a Stack is FILO (Frst-In-Last-Out). We can use Variables defined in a Scope below its own Scope (e.g. a Function uses a Variable in the Main Scope). When a Function exits, its Variables and everything else in its scope are lost.

We now look at the 'str' type, which is the most common Non-Scalar type. A 'str' can be used as such:

sum=0
for x in str(1234):
    sum+=int(c)
print(sum)

What we get here is that the numbers 1234 is first converted into a 'str' of '1234'. For each item in the String, starting from 1, they are added to the total sum. In the end, we'll have the answer of 10.

We can deal with 'str' as if it's an array. Suppose that we have the following 'str':

helloStr = 'hello'

We can access the first character of the 'str' using:

print(helloStr[0])

The above code would give us a 'h'. We can also access a range of characters, as such:

print(helloStr[0:2])

This would print out the first (0) and second (1) char in the 'str'. This is a method known as a Slicing. It makes a new copy of the original 'str' (known as a Substring). There are also different operations that you can do with 'str' types, for example, to find patterns (and get the location of the provided pattern), we can use:

helloStr.find('lo')

We would get the output 3.

We'll now look at the following piece of code, which enables us to find patterns in a provided text:

#Finds patterns in Strings
providedString = input('Enter the text: ')
findString = input('Enter the pattern: ')
low = providedString.find(findString)
while providedString.find(findString,low)!=-1:
    print(providedString.find(findString,low),"to",low+len(findString))
    print(providedString[0:low]+'['+providedString[low:low+len(findString)]+']'+providedString[low+len(findString):])
    low=providedString.find(findString,low+1)

In this Program, we first get a String, and a Substring to search for. We have a 'low' value to indicate the last position from the last search. We find the first occurrence of the searched text, and print its start and end slice index of the providedString. Next, we print out the text, adding brackets between the found text. This repeats till no more occurrence is found.