Towards computational problem solving

Why do we need computers to solve problems?

Because humans are not very efficient in dealing with complex problems, since
there are limits to the humans mental capabilities.

Miller's law
The Miller's law says that the average that a person can keeè in working memory is
seven +-2

Why are computers good to solve problems?

Computers are much faster in solving many problems
Computers power has increased over the past decades

From problems to programs

What is a problem?
A problem can be subdivided in 2 parts:
The problem input: can include some restrictions
The problem output: emphasizes the relation between input and output

Imperative knowledge
Imperative knowledge is a sequence of instructions, called a program, where
these instructions are understandable by a computer.

What is an algorithm?
An algorithm is a finite sequence of well-defined computer-implementable
instructions, typically to solve a class of problems or to perform a
computation.

What is a program?
A program consists in a sequence of instructions.

What is abstraction?
Abstraction is the process of removing physical, spatial, or temporal details
in the study of objects or systems to focus attention on details of greater
importance.

The Turing machine

The Turing machine represents an abstraction of a fixed-program computer. This
machine consists of an infinite tape containig symbols, also called the storage,
of which are a set of states.
Can every problem be computed?
No! An example of a problem that can not be computed is the halting machine.

What is the machine code?

Machine code, also known as binary code, is what computers understand.

The Python programming language

Basic facts of Python

it emphasizes code readability (eg: the indentation)
programs can be expressed in fewer lines of code
widely used in many fields, like Computers Science

Further facts
Python is an interpreted language. This means that the instructions are
executed directly, or in others words it doesn't need to be compiled first.
Python is a dynamically typed language. This means that the correctness of
types can generally onle be checked at runtime. (eg: no need to specify the
type of an integer like in java)

Python Shell
Python shell is the basic way to use Python, as it runs in the terminal window.
This allows for iteractively execute Python instructions. The disadvante is
that it has no support for saving code.

IDLE
IDLE is an Integrated Developement and Learning Environment which is an IDE
that comes with Python. The IDLE also inlcudes the Python shell.
An IDE, Integrated Developement Environment compacts a buch of tools in a
single software to write programs

What is the simplest program?

It is the empty program.

Data and Objects

Data is represented by objects in Python, where each object has:
an identity
a type
a value

Numeric types in Python

Integeres numbers (eg: 5)
Floating-point numbers (eg: 5.4)
Complex numbers (eg: 5j)
Syntax and semantics

Syntax
The syntax in Python is a set of rules that determine how a Python program will
be written and interpreted.

Is the Python syntax enough to define the Python language?

No, because we also need to define the meaning of Python programs.

Semantics
The semantics of Python associates with each program a meaning. This meaning
can be defined as the behaviour of the interpreter when it executes the
program, which includes the output that is generated.

Errors in Python
There are two types of errors in Python:

The syntax errors: These errors can be caught before the program executes.
The exceptions: These errors occur when the program is running.

Control flow statements

Straight-line programs
Straight-line programs are those where the statements are executed after one
another, in the order they occur, until there are no more statements.

Basic if-statements
The if-statement is used for conditional execution

if expression:
statement(s)
elif expression:
statement(s)
....
else:
statement(s)
#example
if x < 00: print('x is negative')

Identation
The statements following an expression form a block and these statements need
to be idented if on sparate line. Once the block is finished, the identation
level returns to that of the preceding clause.
Strings and sequences

About classes
A class is the type of an object. For example for the string object the class
is str.
The main elements of a class are:
data items called instance variables
function called methods

Immutability of strings

x = 'ABC'
x.lower()

In the example above, x.lower returns a copy of the string x. This is because
strings in Python are immutable, meaning their contents cannot be changed.

Strings are sequences

In fact all objects of a sequence type support the built-in function len which
returns teh lenght of the sequence.
The objects of sequece type also support the following operations:
concatenation

x = 'Hello'
y = 'world'
x+y = 'Hello world'

membership testing

'Hello' in 'Hello world' #returns True

indexing

'Hello world'[0] #returns 'H'

slicing

'Hello world'[0:5] #returns 'Hello'

Lists
For more general sequences, we can use the list datatype. Unlike strings, lists
are mutable, meaning that the values can change.

#Two simple programs

Binary search
 Binary search is an algorithm that compares the target value to the middle of
the array. If they are unequal, the half in which the target cannot lie is
eliminated and the search continues on the remaining half until it succeeds. If
the search ends with the remainder being empty, the tartget is not in the
array.

Loop varient
A loop varient is an integer expression E with the following properties:
for an iteration to execute we must have E >= 0
Each iteration of the loop decreases the value E.

Loop invarient
A loop invarient for a loop is the condition that holds before and after each
iteration of a loop.

Complexity of linear search

Linear search is refered to linear complexity in the worst case.

What would be the complexity of the linear search in the best case?
In the best case the element is found at the first position of the
sequence. Thus the complexity in the best case is independent of the
lenght of the input sequence. We talk about constant complexity.

Complexity of binary search

To be able to anlyse the complexity of binary search we need to consider the
following: in one iteration we divide the lenght of the sequence that need to
be checked by a factor of at least 2. ###^How many iterations will be required?
Suppose we start out with a sequence with n numbers. After one iteration
we are left with at most n/2 numbers. After i iterations we are left
with at most n/2^i numbers. Therefore the complexity of the binary
search is logarithmic complexity.

Number search and binary search algorithm

Number search

#request input sequence

s = input('Please enter the sequence of numbers: '
numberList = s.split()
#request number to search for
n = input('Please enter the number to search for: ')
#look for firts occurrence
pos = -1
for x in numberList:
pos += 1
if x in n: # or numberList[pos] == n
print('number found at position' pos)
quit()
print('Number not found')
Binary search

#request input sequence

s = input('Please enter the sequence of numbers: '
numberList = s.split()
#request number to search for
n = input('Please enter the number to search for: ')
a = 0
b = len(numberList)-1
while a <= b:
m = (a+b)//2
if numberList[m] == n:
print('Number at position:', m)
break
elif n < numberList[m]:
b = m-1
else:
a = m+1
if a>b: print(-1)
Towards functions

Golden rule of programming

Say each thing once!

##How to resuse code without reproducing it again?

By packing the code as a function.

#Functions in Python

Example of a function in Python

def myMin(x, y):

# x and y are the "parameters" of the function
# they constitute the "input"
if x<y:
return x
else:
return y
# output is either x or y

Global vs local variables

The global variable can be used in the entire program (after it was declared).
The local variables are the ones created inside functions and they are only
available inside.

Docstring
Docstring are comments which have the purpose to jelp the programmers and users
to know what the functions do. Usually it contais whar is the input and the
output. The advantage of docstrings id the fact that the user/client don't need
to understand the complexity of the program.

Functions and contrats

A funtion can have a contract associated whic consists of 2 parts:
Assumptions: conditions that must be met by users or clients of the
function
Guarantees that must be met by the function.

Who benefits from contrats?

The programmer, because he knows what he must implement.
The** client** of the function, because ideally the contract is enough
to understand what the function does.

Modules
Definition
A module in Python contains a collection of Python definitions and statements. In
other words, a module is a Python file.

What are the benefits of using modules?

Modules helps to reduce the softeware complexity of a program.
They are helpful for software development: dividing up programming tasks
They are helpful for software testing: allows different functionalities to be
tested separatly
They are helpful for software maintenance: facilities modification of specific
program functionalities.
Problem solving

Top-down approach
This approach consitst in breaking the original problem into subproblems, then
break those subproblems in sub subproblems, until the porblem we end-up with is
easy to solve.

Bottom-up approach
This approach consists in working from what's already known to build solutions
to bigger problems.

What is the best approach?

In practice both approaches are often used together: one does decompose the
problem down to some level and then use existing solutions for solving some
subproblems.

Recursion

Definition
Recursion is the same as the factorial (eg: n!) in mathematics.

What is the practical significance of the factorial

function?
n! represents the number of permutations of n elements.

Recursive program for factorial

def f(n):
""" Assumes that n is an integer >= 0
Returns n! """
if n == 0:
return 1
else:
return n*f(n-1)

Activation records/call chain

Each fuction call is associated with an activation record. An activation record
contains the names and values of all parameters and local variable of the
calling function; it also contains the place from where the function was
called.
The data in the activation record is required for the function call to be
correctly executed.
Stack
A stack is a data structure that manages data in a LIFO (Last In First Out)
manner.
Stacks offers the following operations:
push for pushing a new data item nto the stack
pop for removing the data item added last, called the top item
top returns the top item of the stack.

Recursion depth
If we run the factorial function for large numbers we get an exception called
RecursionError, stating that the maximum recursion depth is exceeded.

The recursion depth is the maximum size of the call stack.

How to overcome the recursion depth?

. There are two options:

- increase the maximum recursion depth (sys.setrecursionlimit(limit)).

develop an iteractive program instead.

Interactive solution
We can view the recursive program as a top-down solution for the factorial
function. It is straightforward to develop a bottom-up solution to this
problem.

Possible implementation:

def f(n):
""" Assumes that n is an integer >= 0
Returns n! """
result = 1
for i in range(1, n+1): # from 1 to n
result *= i
return result

Tower of Hanoi problem

What is the problem?
Input: A configuration with three pegs, the leftmost peg having a stack of
disks sorted in descending size from bottom to top.
Output: A sequence of moves of disks from one peg to another without ever
putting a larger disk on a smaller one so that we end up with the disks in the
same order on the rightmost peg.
Structured types

Structured types vs non-stuctured types

Definition of a structured type

A structured type is an item that has an internal structure. Some examples are:
strings (sequence of characters) and lists (sequence of objects).

Definition of a non-structured type

A non-structured type is an item that has no internal structure, meaning that they
are not further subdivided. Some exmaples are the numeric and boolean types.

Sequences
A sequence is an ordered container of items that can be accessed via an index.

Tuples
A tuple is a sequence type which like a list can contain objects of arbitrary
types. Different from a list, tuples are represented by a comma-separated list of
elemets surrounded by parentheses.

* What is the difference between lists and tuples?*

Tuples are immutable while lists are mutable.

List comprehension
List comprehension provides a way to construct a list out of another list.

Example of a list comprehension

farenheitTemps = [(t*9/5) + 32 for t in celsiusTemps]

The set data type

Definition

A set is a collection of unordered elements without doubles. To define a set we do

as follows: S = {0, 1}

The empty set

The notation for an empty set is NOT {} but instead set()

Dictionaries
A _dictionary is a set of key-values pairs. The key and the value are separated ba
a colon (:) and the key-value pairs are separated by a comma.
Fucntions as objects

Functions as arguments
Since functions are objects, we can pass functions as arguments to another
function.

Example

def g(x,h): # apply function h to parameter x

return h(x)

Lambda expressions
A lambda expression is an expression that defines an "anonymous function". The
general form is : lambda : .

Example

lambda x : x*x
Files

Transient vs persistent data

Transient data exists during the lifetime of the program. In the otherhand,
persistent data exists outside the lifetime of the program.

Current directory
How to find the location of the current directory?
By using the method getCWD() in the module os.

Exceptions

Standards exeptions

ImportError: raised when the import statement fails.

IndexError: raised when a sequence index is out of range.
NameError: raised when a name is not found.
TypeError: raised when an operation of fuction is applied to an object of
inappropriate type.
ValueError:raised when an operation or function is applied to an object of appropriate
type but innapropriate value
IOError: raised when an input/output operation fails.

Try statement

try:
statement(s)
except [expression]:
statement(s)

Exception checking strategies

LBYL (Look Before You Leap) is a method where you check in advance for any
possible problems. The disadvantage is that it diminish the readability of the
main case.
EAFP (It's Easier to Ask Forgiveness than Permission) is the preferred method
in Python.
Testing

Testing vs debugging
Testing consists in checking the correctness of a program by running it on a
set of inputs.
Debugging consists in finding the error in a program that we know not to be
correct.

Test suite
A test suite is as set of possibel inputs to rest the program.

Black-box testing
Black-box test suites are created without looking ar the code.

What are the advatages of this approach?

Testers and implementers can be drawn from separate populations
This approach is robust with respect to implementation changes.
we can write the test cases before writing the code.

Boundary-values technique
This technique consits in examining test cases at the boundary values.

Invalid inputs
There is two approaches when it comes to testing:
contract based testing: only test valid inputs
defensive testing: test all inputs

Equivalence class testing

With this approach, we define subsets of input values that are thought to be
equivalent in the sense that if the code behaves correctly for all inputs of
this subset.

Unit testing vs integration testing

Unit testing test individuals of code like functions or modules.
Integration testing tests whether the program as a whole behaves as expected.
Testing

Testing vs debugging
Testing consists in checking the correctness of a program by running it on a
set of inputs.
Debugging consists in finding the error in a program that we know not to be
correct.

Test suite
A test suite is as set of possibel inputs to rest the program.

Black-box testing
Black-box test suites are created without looking ar the code.

What are the advatages of this approach?

Testers and implementers can be drawn from separate populations
This approach is robust with respect to implementation changes.
we can write the test cases before writing the code.

Boundary-values technique
This technique consits in examining test cases at the boundary values.

Invalid inputs
There is two approaches when it comes to testing:
contract based testing: only test valid inputs
defensive testing: test all inputs

Equivalence class testing

With this approach, we define subsets of input values that are thought to be
equivalent in the sense that if the code behaves correctly for all inputs of
this subset.

Unit testing vs integration testing

Unit testing test individuals of code like functions or modules.
Integration testing tests whether the program as a whole behaves as expected.
Debugging

What is a software bug?

A software bug is an error, failure, flaw or a fault in a computer program or
system that causes it to produce an incorrect or unexpected result, or to behave
in unintended way.

Overt vs covert bugs

An overt bug is one that has an obvious manifestation (eg: an exception raised)
a covert bug is one that has no obvious manifestation (eg: missing parentheses)

Persistent vs inteminent bugs

A persistent bug is one that occurs every time the program is run with the same
inputs.
An intermittent bug is one that occurs only some of the time.

Programming and role playing

When programming, you need to assume different roles:
when designing a program, you need to act like an archictect
when coding, you need to act like an engineer
when testing, you need to act like a vandal
when debugging, you need to act like a detective
When changing roles, you need to adopt different strategies and goals.
Iterators

What kind of expressions can we iterate over?

To answer we need to think in terms of contrats. A contract would be: the
expression should accept next-requests to return the next element.

Form expression to iterators

An iterable is an expression that has an iterator.

What is the advantage of implementing for-loops using

iterables?
Do not need to keep all the items in memory at once. Therefore it is much more
memory-efficient.

Generators

Definition
A generator is a function whos body contains the special keyword yield.
Floating-point numbers

Type float
In Python, ther is no limit to the sizw of integers.
A float can be represented as a pair of integers, where we have:
the significat difits
the exponent

Example
The number 1,949 is represented by 1949 (the significant digits), and -3
(the exponent)

Precision and range

The number of significant digits determines the precision of floats.

From decimal to binary

In a decimal notation, the value of the number can be expressed as a sum of
powers of 10.
In a binary notation, this means its value can be expressed as a sum of powers
of 2.

Floats in binary
Floats are internally not represented in decimal but in binary.
About classes

Introduction
Every data item/value in Python is an object whre the type of an object is a class

Class definition
Classes are defined using the class statement. One thing to note is that a class
must be non-empty, thus a minimal class definition could look like this:

class C:
pass #do noting

Classes vs objects

What is the effect of executing a class statement?

When executing a class statement, this results in the creation of a class where
this class is also an object. The type of this object is the class "type" and
since it is also a class, it is also represented by a class object where the
"type" class object is its own type.

Instances
When an object has type a class C, we also say that the objects is an instance
of class C.
To test if an object x has a type classs object C, we can call the built-in
function **isinstance(x, C).

Encapsulation

Introduction
Encapsulation consists in separating *what needs to be done" from "how its done".
This separation consists of the interface, where the attributs are vusible to
other classes, and the implementation, where the attributes are invisible to the
other classes.

Advantages
More flexibility:
The implementation can be changed without changing the interface

Interface easier to understand than implementation

Access to data can be controlled

Encapsulation in Python
 In Python attributes in the interface are public and those in the implemention
are private
To set an attribute in private, prefix it with double underscore (__x).

Inheritance

Introduction
In Pyton, we can define subclasses of other classes. The syntax is the following:
class C(D): ....; where C is a subclass of D and D is a superclass of C.

Inheritance and attributes

If B is a subclass of class A, then B inherits all public attributes from A.

Polymorphism

Introduction
Polymorphism relies on two fundamentals mechanims. The method overriding and the
dynamic binding, where the version of the function that is called is only
determined at runtime.

Abstract classes
Abstract classes is a class that has one or more methods that are not
implemented (or is implemented to raise an exception)
Matplotlib

What is malplotlib?
Matplotlib is a library for making 2D plots of arrays in Python

What is Pylab?
Pylab is a module (part of matplotlib) that provides facilities for data
visualization, data analysis and numeric computations-

Example

import pylab
pylab.figure(1) #create figure 1
pylab.plot([1, 2, 2], [1,7,9,5]) #draw on figure 1
pylab.show()

Is there any point in plotting figures without showing

them?
Yes, we can create different figures and save them to files (eg: for viewing tham
later)

NumPy

What is NumPy
NumPy provides an efficient way to store and manipulate multi-dimensional arrays
in Python.

#Pandas

What is Pandas?
Pandas is built on top of NumPy and it provides a labellled interface to multi-
dimensional data using a DataFrame object.

Waht is CSV format?*

CSV (Comma-Separated values) allows to store tabular data in plain text, where
each line is separated by commas.

Pivot table
A pivot table is a table that summarizes data in another table, and is made by
applying an operation such as sorting, averaging, or summing to data in the first
table, typically including grouping of data.