Modelling Objects in the real world must be modelled as abstract mathematical
entities and basic data types.
Operations How one stores, accesses and manipulates these entities and the
formal meaning of these operations.
Representation How these entities are actually represented in a computer’s memory.
Algorithms Methods used to perform these operations
It’s an abstract/mathematical formalisation about:
o How to store a collection of objects in memory
o Operations that are performed on the data
o Algorithms for those operations
o How time and space efficient those algorithms are
Data storage and operations can be encapsulated by an ADT.
ADT specifies permitted operations as well as guaranteeing time and space.
The user is unconcerned with how it’s implemented.
ADTs are a concept or a convention:
o Not something that directly appears in your code
o Programming language may provide support for ADTs to users
The Dictionary ADT is the most basic and useful of ADTs
Dynamic programming is a method for solving a complex problem by breaking it down into a
collection of sub-problems.
Choice of data structures can make a big difference in speed.
ADTs encapsulate and hide implementation of a data structure, while presenting a clean interface
to other programmers.
Using naïve methods, many sub-problems can be solved only once and used many times over.
, Ordering Put keys into some order so that we know something about how the keys relate to
each other.
Linking Add pointer to each record to find related records quickly.
Pointers let us express relationships between pieces of information.
Pointers of a particular element show the previous and the next element in the list.
Insertion and deletion is easier.
Don’t have to know the size of the data at the start.
Partitioning Divide the records into two or more groups, each group sharing a particular property.
Partitioning usually combines with linking to point to either of the two halves.
Examples:
o Binary space partitioning (BST)
o Bounding volume hierarchies
o Quad-trees
o KD-trees
o Bins. ??
There are many techniques to ensure balance in some form or another.
Binary search guarantees balance b always picking the median.
When using a linked structure, it is not so easy to find the median.
, The running time of an algorithm varies with the input and typically grow with the input size.
Average case is difficult to determine so instead we focus on fining the worst case run time.
How to Measure Running Time?
Method How? Why not?
Experimentally Measure the actual running time of the Actual running time also depends on a
program that implements the algorithm number of other exterior factors that
cannot be accounted for in the test.
The test inputs could not entirely test
the algorithm.
Theoretically By inspecting the pseudo-code, we can Nope. Totes use it actuals.
determine the run time. This uses a high-
level description of the algorithm and
takes in all possible accounts
Running time of any program on a given computer depends on the number of inputs to process:
o Running Time = 𝑇(𝑛) where 𝑛 is the number of data elements.
Linear 𝑇(𝑛) has dominant term 𝑛
Logarithmic 𝑇(𝑛) has dominant term log 2 𝑛
Quadratic 𝑇(𝑛) has dominant term 𝑛2
Cubic 𝑇(𝑛) has dominant term 𝑛3
Run times for small inputs are not very useful:
o We want run time indications for large to extremely large 𝑛.
Algorithmic Analysis must compare functions and emphasise differences for large 𝑛 values.
We use big-O notation to compare function based on their rate of growth.
Properties:
o Dominant term determines the growth rate
o Values of constants are irrelevant
o Small values of 𝑛 are irrelevant.
o Example if 𝑓(𝑛) = 𝑛3 + 100𝑛2 then 𝑂(𝑛 3 ) thus the time complexity is of cubic time
It focuses on the largest term and ignores constants
o The largest term will eventually dominate for large enough 𝑛.
o Constants depend on irrelevant things like clock speed, Operating System, etc.
Definition:
o 𝑇(𝑛) is 𝑂(𝑓(𝑛)) if:
𝑇(𝑛)
lim =𝑐
𝑛→∞ 𝑓(𝑛)
Where 𝑐 is a constant.
entities and basic data types.
Operations How one stores, accesses and manipulates these entities and the
formal meaning of these operations.
Representation How these entities are actually represented in a computer’s memory.
Algorithms Methods used to perform these operations
It’s an abstract/mathematical formalisation about:
o How to store a collection of objects in memory
o Operations that are performed on the data
o Algorithms for those operations
o How time and space efficient those algorithms are
Data storage and operations can be encapsulated by an ADT.
ADT specifies permitted operations as well as guaranteeing time and space.
The user is unconcerned with how it’s implemented.
ADTs are a concept or a convention:
o Not something that directly appears in your code
o Programming language may provide support for ADTs to users
The Dictionary ADT is the most basic and useful of ADTs
Dynamic programming is a method for solving a complex problem by breaking it down into a
collection of sub-problems.
Choice of data structures can make a big difference in speed.
ADTs encapsulate and hide implementation of a data structure, while presenting a clean interface
to other programmers.
Using naïve methods, many sub-problems can be solved only once and used many times over.
, Ordering Put keys into some order so that we know something about how the keys relate to
each other.
Linking Add pointer to each record to find related records quickly.
Pointers let us express relationships between pieces of information.
Pointers of a particular element show the previous and the next element in the list.
Insertion and deletion is easier.
Don’t have to know the size of the data at the start.
Partitioning Divide the records into two or more groups, each group sharing a particular property.
Partitioning usually combines with linking to point to either of the two halves.
Examples:
o Binary space partitioning (BST)
o Bounding volume hierarchies
o Quad-trees
o KD-trees
o Bins. ??
There are many techniques to ensure balance in some form or another.
Binary search guarantees balance b always picking the median.
When using a linked structure, it is not so easy to find the median.
, The running time of an algorithm varies with the input and typically grow with the input size.
Average case is difficult to determine so instead we focus on fining the worst case run time.
How to Measure Running Time?
Method How? Why not?
Experimentally Measure the actual running time of the Actual running time also depends on a
program that implements the algorithm number of other exterior factors that
cannot be accounted for in the test.
The test inputs could not entirely test
the algorithm.
Theoretically By inspecting the pseudo-code, we can Nope. Totes use it actuals.
determine the run time. This uses a high-
level description of the algorithm and
takes in all possible accounts
Running time of any program on a given computer depends on the number of inputs to process:
o Running Time = 𝑇(𝑛) where 𝑛 is the number of data elements.
Linear 𝑇(𝑛) has dominant term 𝑛
Logarithmic 𝑇(𝑛) has dominant term log 2 𝑛
Quadratic 𝑇(𝑛) has dominant term 𝑛2
Cubic 𝑇(𝑛) has dominant term 𝑛3
Run times for small inputs are not very useful:
o We want run time indications for large to extremely large 𝑛.
Algorithmic Analysis must compare functions and emphasise differences for large 𝑛 values.
We use big-O notation to compare function based on their rate of growth.
Properties:
o Dominant term determines the growth rate
o Values of constants are irrelevant
o Small values of 𝑛 are irrelevant.
o Example if 𝑓(𝑛) = 𝑛3 + 100𝑛2 then 𝑂(𝑛 3 ) thus the time complexity is of cubic time
It focuses on the largest term and ignores constants
o The largest term will eventually dominate for large enough 𝑛.
o Constants depend on irrelevant things like clock speed, Operating System, etc.
Definition:
o 𝑇(𝑛) is 𝑂(𝑓(𝑛)) if:
𝑇(𝑛)
lim =𝑐
𝑛→∞ 𝑓(𝑛)
Where 𝑐 is a constant.
