csi 33

Function Specification

Tells WHAT a function does (its purpose), but not HOW it does it.

Precondition

What must be TRUE BEFORE the function is called. The "rules" for using it.

Postcondition

What is TRUE AFTER the function finishes. The "promise" it keeps.

Side Effects

Functions should not produce undocumented side effects

Function specification

tells what a function does but not how that is done

Function precondition

tells what is true before the function is called

Function postcondition

tells what is true after the function finishes executing

functions should not

produce undocumented side effects

Enforcing preconditions

raise an exception or use an assert statement

assert

for finding bugs in your code

exception

is for handling expected errors from the user or environment.

t(n)

the number of "steps" a computer needs to take to finish an algorithm, where n is the "size" of the problem.

n can be number of items to sort, number of items in the list, number of users.

abstract data type (ADT)

type (or class) for objects with behavior defined by a set of values and a set of operations.

ADT

tells what operations are to be performed, but not how operations will be implemented. does not

specify how data will be represented or and

what algorithms will be used for operations

ADT examples

dataset, rational, card

Class invariant

is a set of properties that allobjects in the class must satisfy.

Class invariant

It gives a criterion for the object to be valid, must be fulfilled by the constructor, must be maintained by the public methods.

python list methods

deck of cards, hand of cards using python list as container

python list

a manager for a dynamic array of references

Dynamic Array

A contiguous block of memory that holds memory addresses (references to the actual objects).

dynamic

The array can grow by allocating a new, larger array and copying the references over when it runs out of space.

Arrays

homogeneous, size determinedstatically (unless additional programming fordynamic array class), efficient random memoryaccess

stack ADT

last in, first out ADT, methods -push to place data, pop to remove data, top to examine data

Stack applications

managing function calls,evaluating Reverse Polish expressions, changing infix expressions to reverse Polish expressions

queue ADT

first in, first out ADT, methods -enqueue to add data, dequeue to remove and return data, front to examine data

Recursive function

a function that is defined using a call to the function itself in the definition. The definition must have one or more base cases where the function can be computed without a recursive call.

every chain of recursive calls must what

terminate at a base case

examples of recursive functions

factorial, string reversal,permutations, exponentiations by repeated squaring, binary search, Fibonacci

append()

adds to the end

Time Complexity Analysis

the methods for analyzing the amount of time that it takes for an algorithm to run

Big-O (f(n)) bound

an upper bound by a multiple of f(n) of how much the number of steps ofan algorithm grows as the problem instance gets larger. Common functions f(n) are c, n, n2,log(n), and n log(n)

Big-Theta(f(n))

an upper and lower bound by a multiple of f(n) of how much the number of steps of an algorithm grows as the problem instance gets larger

Object-oriented programming

programming paradigm (way to conceptually organize the implementation of a program) that emphasizes creating a model of the problem environment that links data and methods that work on the data into a unit, called an object.

Class

a category of objects defined by program code that gives the data members and defines function members that operate on the data

Instance Variables

a variable that belongs to an object or instance of a class.

Instance method

A method that belongs to an object in a class that can be used to access or modify the data of a class, or do computations related to that data.

Class invariant

a condition that all objects of a class must satisfy to be valid, established by the constructor and maintained by class methods

Operator overloading

giving an existing operator an additional definition to allow it to work with user-defined data types

Container class

a class whose objects hold a collection of objects, such as lists, tuples,dictionaries, and sets

ADT or abstract data type

A type for an object whose behavior is defined by a set of values and what operations are to be performed but does describe how the operations are implemented

ADT specification

The description of the possible values and behavior of the operations for that ADT

Dictionary or mapping

an ADT that holds data as key-value pairs. Keys must be unique and are used to retrieve the corresponding value.

Hash table

the structure that is used to implement a dictionary of key-value pairs, combining a large array with a hash function to compute an integer to be used as an index in the array at which to store a key-value pair

Linked list

A sequential data structure that consists of a collection of nodes, each with some data and a link or reference to the next node in the list

Node

an individual element of a linked list, containing data and a link to the next node,

Stack or LIFO ADT

an ADT that stores a linear collection of data elements and follows a"Last In, First Out" principle. A data element is added or pushed onto the stack, and the last or most recent element added is the element that is removed or popped from the stack

Queue or FIFO ADT

an ADT that stores a linear collection of data elements and follows a"First In, First Out" principle. A data element is added or enqueued onto the end or tail of the queue, and the first element enqueued is the element that is removed or dequeued from head of the queue

Functional abstraction

a programming technique of separating the task to be performed by a function from the implementation details of the function, allowing a programmer to use a function without knowing its implementation

Base case

A non-recursive part of a recursive function definition, that computes the function value or carries out the function task without a recursive call.

Recursive case

the part of a recursive function definition that calls the same function on a simpler or smaller version of the problem

Unit testing

a software testing method that validates that each unit, such as a function, class, or method, works as intended in isolation

o(1)

constant time - instant

o(log n)

logarithmic - very slow growth

o(n)

linear - doubles when n doubles

o(n²)

quadratic - 4x time when n doubles

o(2^n)

exponential - time doubles when n increases by 1

Container Class

Class that holds collections of objects

LIFO operations

• push(): Add to top

• pop(): Remove from top

• top(): Examine top element

Applications: Function calls, expression evaluation

FIFO operations

enqueue(): Add to back

dequeue(): Remove from front

front(): Examine front element

Applications: Resource sharing, simulations