1 Data Structures and Algorithm Analysis
* Data Structures and Algorithm Analysis
(based on slides )
Algorithm:
A finite sequence of operations that solves a given task
Good characteristics:
correctness
efficiency
robustness
Data Structures:
A way to organize data so that common operations (e.g. insert a new item, search, etc.) are performed efficiently
Examples: linked lists, queues, stacks, trees, graphs
* The maximum contiguous subsequence sum problem
Given integers A1 A2 .. An.
Find the sequence that produces the max value j k=i Ak
The sum is a zero if all integers < 0
Example:
-2 11 -4 13 -5 2
The sum of the sequence from the 2nd to the 4th number is 20, which is the largest possible value
1 -3 4 -2 -1 6
The sum of the sequence from the 3rd number to the 6th number (4 -2 -1 6)
is the largest possible value: 7
* Algorithm 1: conduct an exhaustive search(a brute force algorithm)
max = 0
for(i=0; i
max = sum
start = i
end = j
Time complexity: O(n3)
Example: The following numbers are in the array a:
-2 11 -4 13 -5
Trace:
(1) i=0
j=0 sum = -2
j=1 sum = -2+11
j=2 sum = -2+11-4
j=3 sum = -2+11-4+13
j=4 sum = -2+11-4+13-5
max = 18
i=0
j=3
It calculates all subsequences, such as the sequence of 1 number, the sequence of 2 numbers, and so on, starting at the first position, then at the 2nd position, until the last position
* Cont. trace
(2) i=1
j=1 sum = 11
j=2 sum = 11-4
j=3 sum = 11-4+13
j=4 sum=11-4+13-5
max = 20
i=1
j=3
(3) i=2
j=2 sum = -4
j=3 sum = -4+13
j=4 sum = -4+13-5
max, i and j remain unchanged
(4) i =3
j=3 sum = 13
j=4 sum = 13-5
max, i and j remain unchanged
(5) i=4
j=4 sum = -5
max, i an j remain unchanged
* Algorithm 2
Observation: j k=i Ak = Aj + j-1 k=i Ak
Sequence: -2 11 -4 13 -5
Example: once we calculate -2+11-4+13=18, we need to perform only one addition to calculate the entire sequence
that is: 18-5 = 13
The algorithm
max=0
for(i=0; i
max = sum;start=i;end=j;
Time complexity: O(n2)
The statement sum +=a[j] adds one additional number to the sum reducing redundant work
* Algorithm 3
Let Ai,j be the sequence from ij and Si,j be its sum.
Observation: let d[j] be the max sum of a sequence that ends at A_j.
Then: d[j] = d[j-1] + A_j if d[j-1] >= 0, and d[j] = A_j, if d[j-1] < 0.
So the d[j]’s can be computed in one left-to-right scan of the sequence A_1 …A_n.
Example: 2 -1 -3 6
d[0]=2, d[1]=1, d[2]=-2,d[3]=6
Improvement: Since d[j] depends only on d[j-1], we do not need an array to keep the d[] values. In the pseudocode (next slide), we keep the relevant value in the variable sum.
* Cont. algorithm 3
i=0; max =0; sum = 0;
for(j=0; j
max = sum
start=i; end = j;
else
if(sum <0)
i=j+1
sum=0
Time complexity: O(n)
sequence: -2 11 -4 13 -5
(1) j=0 a[j] = -2
i=0 sum -2 max =0
i=1 (reset)
(2) j=1 a[j] = 11
i=1 sum=11 max=11
start=1 end =1
(3) j=2 a[j]= -4 sum = 7 max =11
(4) j=3 a[j] =13 sum =20 max = 20
start =1 end = 3
(5) j=4 a[j]=-5 sum = 15 max =20
start =1 end =3
Basic idea: as long as the sum >0, add another number to it. If not, start over again
* Summary:
Algorithm 1 is O(n3)
Algorithm 2 is O(n2)
Algorithm 3 is O(n)
and all of them are correct algorithms
One importance issue in the design of algorithm is efficiency
* Steps in designing software
Specification
input, output, expected performance, features and
sample of execution
System Analysis
chose top-down design or OOD (sort of bottom-up)
Design (OUR FOCUS IN THIS COURSE)
* choose data representation: create ADTs
* algorithm design
Refinement and Coding
implementation
Verification
correctness analysis and testing
Documentation
manual and program comments
* Algorithm Definition
Definition:
A specification of (1) the sequence of steps required to perform a task, and (2) the data objects used in performing each step
Properties:
(1) finite number of steps
(2) must terminate
(3) each step should be precise in meaning
(4) has generality
Representations:
(1) flow chart
(2) pseudocode: between English and a programming language