Data Structure
What is the "Data Structure" ?
Ways to represent data
Why data structure ?
To design and implement large-scale computer system
Have proven correct algorithms
The art of programming
How to master in data structure ?
Practice, Discuss, and Think (PDT)
Data Structures Classification
System Life Cycle
Summary
RADRCV
Requirements, Analysis, Design, Refinement, Coding, and
Verification.
Requirements
What inputs, functions, and outputs
Analysis
Break the problem down into manageable pieces
Top-down approach
Bottom-up approach
Design
Create abstract data types and the algorithm
specifications, language independent
Refinement
Determining data structures and algorithms
Coding
Implementation
Verification
Developing correctness proofs, testing the program, and
removing errors
Verification
Correctness proofs
Prove program mathematically
time-consuming and difficult to develop for large system
Testing
Verify that every piece of code runs correctly
provide data including all possible scenarios
Error removal
Guarantee no new errors generated
Notes
Select a proven correct algorithm is important
Initial tests focus on verifying that a program runs correctly, then
reduce the running time
Algorithm Specification
Describing Algorithms
Natural language
English, Russian
Instructions must be definite and effectiveness
Graphic representation
Flowchart
work well only if the algorithm is small and simple
Pseudo language
Readable
Instructions must be definite and effectiveness
Combining English and C
In this text
Translating a Problem into an
Algorithm
Problem
Devise a program that sorts a set of n>= 1 integers
Step I - Concept
From those integers that are currently unsorted, find the
smallest and place it next in the sorted list
Step II - Algorithm
for (i= 0; i< n; i++)
{
Examine list[i] to list[n-1] and suppose that the smallest
integer is list[min];
Interchange list[i] and list[min];
}
Step III - Coding
void sort(int *a, int n)
{
for (i= 0; i< n; i++)
{
int j= i;
for (int k= i+1; k< n; k++)
{
if (a[k ]< a[ j]) j= k;
int temp=a[i]; a[i]=a[ j]; a[ j]=temp;
}
}
Correctness Proof
Theorem
Function sort(a, n) correctly sorts a set of n>= 1 integers.
The result remains in a[0], ..., a[n-1] such that a[0]<=
a[1]<=...<=a[n-1].
Proof:
For i= q, following the execution of line 6-11, we have
a[q]<= a[r], q< r< =n-1.
For i> q, observing, a[0], ..., a[q] are unchanged.
Hence, increasing i, for i= n-2, we have
a[0]<= a[1]<= ...<=a[n-1]
Data Abstraction
Types of data
All programming language provide at least minimal set
of predefined data type, plus user defined types
Data types of C
Char, int, float, and double
may be modified by short, long, and unsigned
Array, struct, and pointer
Data Type
Types of data
All programming language provide at least minimal set
of predefined data type, plus user defined types
Data types of C
Char, int, float, and double
may be modified by short, long, and unsigned
Array, struct, and pointer
Abstract
Definition
Data Type
An abstract data type(ADT) is a data type that is
organized in such a way that the specification of the objects
and the specification of the operations on the objects is
separated from the representation of the objects and the
implementation of the operation.#
Why abstract data type ?
implementation-independent
Classifying the Functions of a Data
Type
Creator/constructor:
Create a new instance of the designated type
Transformers
Also create an instance of the designated type by using
one or more other instances
Observers/reporters
Provide information about an instance of the type, but
they do not change the instance
Notes
An ADT definition will include at least one function
from each of these three categories
An Example of the ADT
structure Natural_Number is
objects: an ordered subrange of the integers starting at zero and '
ending at the maximum integer (INT_MAX) on the computer
functions:
for all x, y is Nat_Number, TRUE, FALSE is Boolean and where . +, -, <,
and == are the usual integer operations
Nat_NoZero() ::= 0
Boolean Is_Zero(x) ::= if (x) return FALSE
Nat_No Add(x, y) ::= if ((x+y)<= INT_MAX) return x+ y
else return INT_MAX
Boolean Equal(x, y) ::= if (x== y) return TRUE
else return FALSE
Nat_No Successor(x) ::= if (x== INT_MAX) return x
else return x+ 1
Nat_No Subtract(x, y) ::= if (x< y) return 0
else return x-y
end Natural_Number
Performance Analysis
Evaluate a program
MWGWRERE
Meet specifications, Work correctly,
Good user-interface, Well-documentation,
Readable, Effectively use functions,
Running time acceptable, Efficiently use space
How to achieve them?
Good programming style, experience, and practice
Discuss and think
Space Complexity
Time Complexity
Asymptotic analysis of an algorithm refers to defining
the mathematical boundation/framing of its run-time
performance.
Using asymptotic analysis, we can very well conclude
the best case, average case, and worst case scenario of
an algorithm.
Three types −
Best Case − Minimum time required for program
execution.
Average Case − Average time required for program
execution.
Worst Case − Maximum time required for program
execution.
Asymptotic Notation
Big “Oh” Notation
The notation Ο(n) is the formal way to express the upper bound of an
algorithm's running time. It measures the worst case time complexity or the
longest amount of time an algorithm can possibly take to complete.
Big “Omega” Notation
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's
running time. It measures the best case time complexity or the best amount of
time an algorithm can possibly take to complete.
Comparison
Following is a list of some common
asymptotic notations −
Big “Theta” Notation
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper
bound of an algorithm's running time. It is represented as follows −
Asymptotic Analysis
Simple Example
An Recursive Example
Example: Binary Search
Idea
Iterative Binary Search
Performance Analysis of Iterative
Binary Search
Recursive Binary Search
Performance Analysis of Recursive
Binary Search
Thank You