09-01-2014, 04:07 PM
DATA STRUCTURES AND ALGORITHMS
DATA STRUCTURES.ppt (Size: 196.5 KB / Downloads: 198)
ROAD MAP
What is an algorithm ?
What is a data structure ?
Analysis of An Algorithm
Asymptotic Notations
Big Oh Notation
Omega Notation
Theta Notation
Little o Notation
Rules about Asymptotic Notations
What is a Data Structure ?
Definition :
An organization and representation of data
representation
data can be stored variously according to their type
signed, unsigned, etc.
example : integer representation in memory
organization
the way of storing data changes according to the organization
ordered, inordered, tree
example : if you have more then one integer ?
Properties of a Data Structure ?
Efficient utilization of medium
Efficient algorithms for
creation
manipulation (insertion/deletion)
data retrieval (Find)
A well-designed data structure allows using little
resources
execution time
memory space
The Process of Algorithm Development
Design
divide&conquer, greedy, dynamic programming
Validation
check whether it is correct
Analysis
determine the properties of algorithm
Implementation
Testing
check whether it works for all possible cases
Advantages of O Notation
It is possible to compare of two algorithms with running times
Constants can be ignored.
Units are not important
O(7n2) = O(n2)
Lower order terms are ignored
O(n3+7n2+3) = O(n3)