程序代写代做代考 algorithm data structure 1 Data Structures and Algorithm Analysis

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)
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
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 ij 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
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