Python

Computers perform calculations - makes guesses and new guesses based off distance to answer

Knowledge

declarative of knowledge is a statement of fact
Imperative knowledge - recipe/steps (how)

Recipe

Sequence of simple steps
Flow of control process that specifies when each step is executed
A means of determining when to stop

Fixed program computer - old calculator

Stored program - machine stores and executes instructions

-special program (interpreter) executes each instruction in order (moving data, test, arithmetic and logic)

Turing showed you can compute anything with 6 primitives (move left, right, read, write, scan, do nothing) - programming languages add more primitives

Anything computable in one language is computable in any other

Creating

Expressions - complex but legal combinations of primitives in a programming language
Expressions and computations have values and meanings in a programming language

Primitive constructs

English - words

Programming languages - numbers, strings, simple operators

Semantics

Static semantics is which syntactically valid string have meaning
Proper grammar - syntax placement

Objects

Programs manipulate data objects
Objects have a TYPE that defines the kind of things programs can do to them (scalar - can’t be subdivided (number) and non scalar - internal structure (list))

Scalar

Int - integers
Float - real numbers - decimals
Bool - boolean values true and false
Nonetype - special and has one value , none
type() to see the type of an object

float(3) will convert int to float

Expressions

Combine objects and operators to form expressions
An expression has a value, which has a type
Syntax for a simple expression <object> <operator> <object>

= or ==

= is used to assign value to string but == is used for actual = in terms of math

While loops - don't know iterations (user input)

Can use counter but must initialize

For loops - know number of iterations, counter, can rewrite for while loop but harder other way round

Can break loops by using break statement

If - else - elseif

Range (start,stop,step) - has to be integers

Indexing to find certain value in code

Strings are immutable - cannot be modified

Algorithms

Guess and check -

Bisection - eliminating search space with every guess for example guessing a number between 1-100 guess 50 and then eliminate higher or lower

Approximation -

Lecture 4: Decomposition, Abstraction, and Functions

Abstraction idea example - don’t need to know how a projector works to use it can connect with laptop easily

Achieve through function specifications or docstrings

Decomposition - breaking down to focus on specific inputs. - different devices work together to achieve same goal

Creating structure in code - in programming divide code into modules to keep code organized and to break up - can then also be reused easier

Functions

reusable pieces of code
Name, parameters, docstring, body, returns something ]

Scope

environment/ frame/ scope created when enter a function

None is not a string - special type

Nested functions

When there is a function call make new scope

Lecture 5: Tuples, Lists, Aliasing, Mutability, and Cloning

Tuples - sequences of anything - collection of any type of data (any data type)

Once created, can not modify
Parentheses
Can use to interpret data and spit out answer
With a comma its a tuple but without its a string

Lists

Can modify
Square brackets
Iterating over a list- compute the sum of elements of a list - common pattern - list elements indexed 0 to len(L)-1, range (n) goes from 0 to n-1
Append - function must be defined (e.g cant be integer)
To combine lists together use concatenation. + operator, to give you a new list
Mutate list with L.extend(some_list) - some mutations make changes
Can delete at specific index
Can convert to strings and vice versa - similar to casting a float to int
Create a new list and copy every element using chill = {cool:}
Can have nested lists

Aliases

Hot is an alias for warm and point to same object - changing one changes the other
append() has a side effect - printing out same thing when change^

Lecture 6 Recursion and Dictionaries

Recursion - repeating idea multiple times in a similar way

Algorithmically - divide and conquer - trying to simplify a problem repeatedly = recursive step
Base case - reduced problem that can be solved directly
Each recursion call creates its own scope/environment
Bindings of variables in a scope are not changed by recursive call
Flow of control passes back to previous scope once function call returns value

Dictionaries

Stores pairs of data - keys,values
My_dict = {}
To look up its similar to indexing a list
Looks up key and returns value associated (think of grading in a hs class)
Can add entry, test if key is present, delete entry
Can get an iterable that acts like a tuple of all keys or values
Can be any immutable type (can be anything)
No order guaranteed
Valuable for procedure calls when intermediate values don’t change

Lecture 7: Testing, Debugging, Exceptions, and Assertions

Unit testing

Validate each piece of program
Testing each function separately

Regression testing

Add test for bugs as you find them
Catch reintroduced errors that were previously fixed

Integration testing

Does the overall program work people rush to do this

Testing approaches

Intuition - natural partitions - e.g def is_bigger(x,y) - you would know that some parameters would include =, <, >, etc.

Random testing

Black box testing

explores paths through specifications

Glass box testing

Explores paths through code

Explain code to someone who doesn’t know as it will get you to include everything and might catch bug

enumerate() = allows you to keep track of number of loops

Lecture 8 object oriented programming

Every object has a type, internal data representation(primitive), a set of procedures for interaction with the object,
1234 is an instance of an int(type)
Everything in python is an object and has a type
Objects are data abstractions that captures an internal representation (data attributes) and an interface to interact with it (procedures, functions)
Think of data as other objects that make up the class(attributes)

Creating class verse creating instances of class

Coordinate object - defining a point in an x,y plane

Define your own types by using class variable

Class Coordinate(object):

#define attributes here

(the word object means that Coordinate is a python object and inherits all its attributes - subclass)

Instances are the structure of the class but you must create the class first

Methods - functions that only work with this class

Using dot operator

Use _init_ to initialize data attributes

Self is a placeholder for an instance (instance of object you will perform the operation on)

_str_ tells python to print informatively

Have to use special operators to tell python exactly what to do as it can’t perform everything

Lecture 9 - Python Classes and Inheritance

Implementing the class

Defining class
Define data attributes
Define methods
Class name is the type and defines data and methods common across all instances

Using the class

Creating instances of the object type and doing operations with them
Instance has the structure of a class but is one specific object

Data attributes

What it is
How can you represent your object with data?
For a coordinate: x,y values, for an animal its age, name

Procedural attributes (behaviour/operations/methods)

How can someone interact with the object?
What it does
Coordinate finding distance, animal making sound

Getter and setter methods

Should be used outside of the class to access data attributes

An instance and dot notation

Dot notation is used to access attributes though it is better to use getters and setters

Information Hiding

Author of class definition may change data attribute variable names
If accessing data attributes outside the class and class def changes can get errors
Python is not great at this as allows you to access, write and create data and data attributes outside of the class definition however it is not good style to do this

Default arguments

Used for formal parameters if no actual argument given

Hierarchies

Parent class (superclass)
Child class (subclass) - inherits all data and behaviours of parent class but can add more info, behavior, override behavior

Class variables and their values are shared between all instances of a class

Object oriented programming

Create your own collections of data
Organize info
Division of work
Access info in a consistent manner
Add layers of complexity
Like functions, classes are a mechanism for decomposition and abstraction in programming

Lecture 10 - Understanding program efficiency part 1

Seperate time and space efficiency of a program

CHallenges in understanding computational effiiciency problems

Program can be implemented in multiple diff ways
Can solve only using a handfulof different algorithms

Evaluation

Timer - time module (runnting time can vary between implementations, computers, not predictable based on small inputs
Counting operations - assume steps take constant time and count operations executed
Abstract notion of order of growth (best) -

We want to express efficiency in terms of size of input, so need to decide what your input is - can be integer, list , and you decide when multiple parameters to a function

Best case - minimum running time over all possible inputs of a given size

Constant for search_for_elmt, 1st element in any list

Average case - average running time over all possible inputs of a given size

Worst case - max running time over all inputs

Linear in length of list for search_for_elmt

Orders of growth Goals:

Evaluate program efficiency when input is very big
Express growth of program’s run time as input size grows
Want to put an upper bound on growth - as tight as possible
Do not need to be precise - order of not exact growth
We will look at largest factors in run time
We want tight upper bound on growth as a function of size of input, in worst case

Measuring order of growth - big Oh or O() notation

Measures an upper bound on te asymptotic growth

Big Oh is used to describe the worst case

Occurs often as is the bottleneck when a program runs
Express rate of growth of program relative to the input size
Evaluate the algorithm not machine or implementations
Want to know asymptotic behavior as problem gets large so will focus on term that grows most rapidly in a sum of terms and will ignore multiplactive constants since we want to know how rapidly time required increases as increase of output

FOCUS ON DOMINANT TERMS JUST LIKE IN CHEM EQUILIBRIUM

Analyzing programs and their complexity

Combine complexity classes

- analyze statements inside functions

- apply some rules, focus on dominant term

Law of addition for O()

Used with sequential statements

****Need to add example code

COMBINE COMPLEXITY CLASSES

Analyze statements inside functions
Apply some rules, focus on dominant term

Law of multiplication

Used with nested statements/loops

Complexity classes

O(1) = constant running time
O(log n) denotes log running time
O(n) denotes linear
O(n log n) denotes log-linear running time
O(n^c) denotes polynomial running time where c is a constant
O(cⁿ) denotes exponential running time (c is a constant being raised to a power based on size of input)

Simple iterative loop algorithms are typically linear in complexity

Linear search or unsorted list

Must look through all elements to decide it’s not there
O(len(L)) for the loop - O(1) to test if e ==:[i]
Overall complexity is O(n) - where is n is len(L)

Constant Time List Access

If list is all ints - I^th element at
If list is heterogeneous - indirection and references to other objects

Linear search on sorted list

Worst case will need to look at whole list - must only look until reaches a number greater than e
Overall complexity is O(n) - where n is len(L)
Order of growth is same but run time may differ

Linear Complexity

Depends on number of iterations
Number of times around loop is n

Nested loops

Simple loops are linear in complexity

Quadratic complexity

Find intersection of 2 lists, return a list with each element appearing only once

Def intersect(L1,L2):

Tmp = [ ]

For el in L1:

For e2 in l2:

If el == e2

tmp.append(el)

Res = [ ]

For e in tmp:

If not(e in res):

res.append(e)

Return res

O(len(L!)^2)

O() for nested loops

Computes n² very inefficiently
When dealing with nested loops, LOOK AT THE RANGES
Nested loops, EACH ITERATING N TIMES
O(n²)

LECTURE 12; UNDERSTANDING PROGRAM EFFICIENCY PART 2

Constant complexity

Independent of inputs
Very few interesting algorithms
Can have loops or recursive calls but only if number of iterations or calls independent of size of input

Logarithmic complexity

Complexity grows as log of size one of its inputs e.g. bisection search or binary search of a list

Bisection search

Pick an index, i, that divides list in half
Ask if L[i] is larger or smaller than e
Depending on answer search left or right half of L for e
Depending on answer search left or right half of L for e

Complexity of recursion is O(log n) - where n is len(L)

O(log n( bisection search calls

If original range is of size n, in worst case down to range of size 1 when n/2^k)= 1; or when k = log n

O(n) for each bisection search call to copy list

This is the cost to set up each call for each lvl of recursion

If you multiply both above you get log linear

Turns out that total cost to copy is O(n) and this dominates the log due to the recursive calls

Bisection Search Alternative

**** add one of the bisection search implementations

Logarithmic Complexity

Only have to look at loop as no function calls
Within while loop, constant number of steps

O() for iterative factorial

Complexity can depend on number of iterative calls
Overall O(n) - n times round loop, constant cost each time

O() for recursive factorial

May run a bit slower
Still O(n) because the number of function calls is linear is n, and constant effort to set up call
Iterative and recursive factorial implementations are the same order of growth

Log- linear complexity

Many practical algorithms like merge sort
Will return to this next lecture

Polynomial complexity

Most common polynomials algorithms are quadratic, complexity grows with square size of input
Commonly occurs when we have nested loop os recursive function calls

Exponential complexity

Recursive functions where more than one recursive call for each size of problem like TOWERS OF HANOI
Many important problems are inherently exponential so unfortunate, as cost is high and will lead us to consider approximate solutions as may provide reasonable answer quicker

O(2ⁿ)

*add snippet of slide

*complexity of python functions slide

Big Oh summary

Compares efficiency of algorithms

Using big Oh

Describe order of growth
Asymptotic notation
Upper bound
Worst case analysis

Searching and Sorting Algorithms

Search algorithm - method for finding an item or group of items wiht specific properties within a collection of items

Linear search

Brute force search (aka british museum algorithm)
List does not have to be sorted

Bisection search

List must be sorted to give correct answer

Searching a sorted list

Using linear search, search for an element is O(n)
Using binary search, can search for an element in O(log n)
To sort a collection of n elements nust look at each one at least once

Amortized cost

In some cases, may sort a list once then do many searches
Amortize cost of the sort over many searches

Monkey sort

Aka bogosort, stupidsort, slowsort, permutation sort, shotgun sort
To sort a deck of cards - throw in air and if not sorted repeat
Best case is O(n) where n is len(L) to check if sorted
Worst case : O(?) it is unbounded if really unlucky

Bubble sort

Compare consecutive pairs of elements
Swap elements in pair such that smaller is first
When reach end of list, start over again
Stop when no more swaps have been made
Largest unsorted element always at end after pass, so at most n passes
O(n²)

Selection sort

O(n²)

1st step

Extract min element
Swap it with element at index 0

Subsequent step

In remaining sublist extract min element
Swap it with the element at index 1

Keep the left portion of the list sorted

At i’th step, first i elements in list are sorted
All other elements are bigger than first i elements

Merge sort **NEED SNIPPET

Use a divide and conquer approach

If list is of length 0 or 1, alreayd sorted
If list has more than one element, split into 2 lists , and sort each
Merge sorted sublists

Split list in half until have sublists of only 1 element
Merge such that sublists will be sorted after merge
O(n log(n)) - this is the fastest a sort can be