Lesson 5 Analysis Tools for Data Structures and Algorithm & queue

Analysis Tools for Data Structures and Algorithm

Properties of Good Programs

• meet requirements, correctness: basic
• clear usage document (external), readability (internal), etc.

-Resource Usage (Performance)
- efficient use of computation resources(CPU, FPU, GPU, etc.)?
time complexity
- efficient use of storage resources (memory, disk, etc.)?
space complexity

need: “language” for describing the complexity

Space Complexity of List Summing

• LIST-SUM(float array list, integer length n)

total<-0
for i<-0 to n-1 do
total<-end for
return total

• array list: size of pointer, often 8
• integer n: often 4
• float total: 4
• integer i: commonly 4
• float return place: 4
• total space 24 (constant) within algorithm execution does not depend on n

Space Complexity of Recursive List Summing

• RECURSIVE-LIST-SUM(float array list, integer length n)

if n=0
return 0
else
return list[n] + RECURSIVE-LIST-SUM(list, n-1)
end if

recursion: recursive formula + terminating condition

• array list: size of pointer, often 8
• integer n: often 4
• float return place: 4

only 16, better than previous one?

• while doing task 10, waiting for the task 9 ——> occupy other space
• task n: need 16n bytes space

Time Complexity of Matrix Addition

• MATRIX-ADD(integer matrix a, b, result integer matrix c, integer rows, cols)

for i<-0 to rows-1 do
for j<-0 to cols-1 do
c[i][j] <- a[i][j] + b[i][j]
end for
end for

• inner for:
• total: (S + R ) \cdot rows + T

total time needed: %20%5Ccdot%20rows%20%2B%20T#card=math&code=P%20%5Ccdot%20rows%20%5Ccdot%20cols%20%2B%20%28Q%2BS%29%20%5Ccdot%20rows%20%2B%20T)

Rough Time Complexity of Matrix Addition

%20%5Ccdot%20rows%20%2B%20T#card=math&code=P%20%5Ccdot%20rows%20%5Ccdot%20cols%20%2B%20%28Q%2BS%29%20%5Ccdot%20rows%20%2B%20T)
P, Q, R, S, T hard to keep track and not matter much

• inner for: #card=math&code=R%20%3D%20rough%28cols%29)
• total: %20%5Ccdot%20rows)#card=math&code=rough%28rough%28cols%29%20%5Ccdot%20rows%29)
• rough time needed: #card=math&code=rough%20%28rows%5Ccdot%20cols%29)

Key problem: How to express “rough” ?

Representing “Rough” by Asymptotic Notation

• goal: rough rather than exact steps
• why rough? constant not matter much—- when input size large

compare two complexity functions f(n) and g(n)

growth of functions matters
——when n large, eventually bigger than

rough <=> asymptotic behavior (n is large enough)

Asymptotic Notations: Rough Upper Bound

• #card=math&code=f%28n%29) grows slower than or similar to #card=math&code=g%28n%29): %20%3D%20%5Cmathcal%7BO%7D(g(n))#card=math&code=f%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g%28n%29%29)
  • grows slower than :
  • grows similar to :
• asymptotic intuition (rigorous math later):

%7D%7Bg(n)%7D%5Cleq%20c#card=math&code=%5Clim%5Climits_%7Bn%5Cto%5Cinfty%7D%5Cfrac%7Bf%28n%29%7D%7Bg%28n%29%7D%5Cleq%20c)

: arguably the most used “language” for complexity

More Intutions on Big-O

%20%3D%20%5Cmathcal%7BO%7D(g(n))%20%5CLeftarrow%20%5Clim%5Climits%7Bn%5Cto%5Cinfty%7D%5Cfrac%7Bf(n)%7D%7Bg(n)%7D%20%5Cleq%20c#card=math&code=f%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g%28n%29%29%20%5CLeftarrow%20%5Clim%5Climits%7Bn%5Cto%5Cinfty%7D%5Cfrac%7Bf%28n%29%7D%7Bg%28n%29%7D%20%5Cleq%20c)

• “$ = \mathcal{O}(\cdot)\in$”
  • #card=math&code=n%20%3D%20%5Cmathcal%7BO%7D%28n%29)
  • #card=math&code=n%20%3D%20%5Cmathcal%7BO%7D%2810n%29)
  • #card=math&code=n%20%3D%20%5Cmathcal%7BO%7D%280.3n%29)
  • #card=math&code=n%20%3D%20%5Cmathcal%7BO%7D%28n%5E5%29)
• “$ = \mathcal{O}(\cdot)\leq$”
  • #card=math&code=n%20%3D%20%5Cmathcal%7BO%7D%28n%5E2%29)
  • #card=math&code=n%5E2%20%3D%20%5Cmathcal%7BO%7D%28n%5E%7B2.5%7D%29)
  • #card=math&code=n%20%3D%20%5Cmathcal%7BO%7D%28n%5E%7B2.5%7D%29)
• #card=math&code=1126n%20%3D%20%5Cmathcal%7BO%7D%28n%29): coefficient not matter
• #card=math&code=n%20%2B%20%5Csqrt%7Bn%7D%2Blogn%20%3D%20%5Cmathcal%7BO%7D%28n%29): lower-order term not matter

Formal Definition of Big-O

Consider positive function #card=math&code=f%28n%29) and #card=math&code=g%28n%29),
%20%3D%20%5Cmathcal%7BO%7D(g(n))#card=math&code=f%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g%28n%29%29), if exist such that %5Cleq%20c%20%5Ccdot%20g(n)#card=math&code=f%28n%29%5Cleq%20c%20%5Ccdot%20g%28n%29) for all

• covers the lim intuition if limit exists
• covers other situations without “limits” e.g. %7C%20%3D%20%5Cmathcal%7BO%7D(1)#card=math&code=%7Csin%28n%29%7C%20%3D%20%5Cmathcal%7BO%7D%281%29)

next: prove the lim intuition formal definition

lim Intuition Formal Definition

For positive functions f and g, if %7Bg(n)%7D%7D%5Cleq%20c#card=math&code=%5Clim%5Climits_%7Bn%5Cto%5Cinfty%7D%5Cfrac%7Bf%28n%29%7Bg%28n%29%7D%7D%5Cleq%20c), then$ f(n) = \mathcal{O}(g(n))$

• with definition of limit, there exists such that for all $ n \geq n_0$, $ | \frac{f(n)}{g(n)}-c |< \epsilon$
• That is, for all , $ \frac{f(n)}{g(n)}<c+\epsilon$
• Let , big-O definition satisfied with #card=math&code=%28c%27%2Cn_0%27%29). QED

Asymptotic Notations: Definitions

• #card=math&code=f%28n%29) grow slower than or similar to #card=math&code=g%28n%29): (““)
  %20%3D%20%5Cmathcal%7BO%7D(g(n))#card=math&code=f%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g%28n%29%29), iff exist such that %5Cleq%20c%20%5Ccdot%20g(n)#card=math&code=f%28n%29%5Cleq%20c%20%5Ccdot%20g%28n%29) for all
• #card=math&code=f%28n%29) grow faster than or similar to #card=math&code=g%28n%29): (““)
  %20%3D%20%5COmega%20(g(n))#card=math&code=f%28n%29%20%3D%20%5COmega%20%28g%28n%29%29), iff exist such that %5Cgeq%20c%20%5Ccdot%20g(n)#card=math&code=f%28n%29%5Cgeq%20c%20%5Ccdot%20g%28n%29) for all
• #card=math&code=f%28n%29) grows similar to #card=math&code=g%28n%29): (““)
  %20%3D%20%5CTheta%20(g(n))#card=math&code=f%28n%29%20%3D%20%5CTheta%20%28g%28n%29%29), iff $f(n) = \mathcal{O}(g(n)) $ and %20%3D%20%5COmega%20(g(n))#card=math&code=f%28n%29%20%3D%20%5COmega%20%28g%28n%29%29)

The Seven Functions as g

%20%3D%20%3F#card=math&code=g%28n%29%20%3D%20%3F)

• 1: const
• : logarithmic
• : linear
• 
• 
• 
• : exponential

Analysis of Sequential Search

• best case(e.g. num at 0): time #card=math&code=%5CTheta%20%281%29)
• worst case (e.g. num at last or not found): time #card=math&code=%5CTheta%20%28n%29)
  often just say O(n)-algorithm (linear complexity)

Analysis of Binary Search

• best case(e.g. num at mid) : time #card=math&code=%5CTheta%20%281%29)
• worst case(e.g. num not found):
  because range (right - left) halved in each WHILE, needs time #card=math&code=%5CTheta%20%28log%20n%29) iterations to decrease range to 0.

Sequential and Binary Search

• Direct-SEQ-Search: #card=math&code=O%28n%29) time
• SORT-AND- BIN-SEARCH: #card=math&code=O%28n%5E2%29) time for SEL-SORT and #card=math&code=O%28log%20n%29) time for BIN-SEARCH

Some Properties of Big-O

• Theorem (Law of closure)
  if %20%3D%20%5Cmathcal%7BO%7D(g_2(n))%2C%20f_2(n)%20%3D%20%5Cmathcal%7BO%7D(g_2(n))#card=math&code=f_1%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29%2C%20f_2%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29), then %2Bf_2(n)%20%3D%20%5Cmathcal%7BO%7D(g_2(n))#card=math&code=f_1%28n%29%2Bf_2%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29)
  proof:
  • When %20%5Cleq%20c_1%20g_2(n)#card=math&code=n%20%5Cgeq%20n_1%2C%20f_1%28n%29%20%5Cleq%20c_1%20g_2%28n%29)
  • When %20%5Cleq%20c_2%20g_2(n)#card=math&code=n%20%5Cgeq%20n_2%2C%20f_2%28n%29%20%5Cleq%20c_2%20g_2%28n%29)
  • So, when %2C%20f_1(n)%2Bf_2(n)%20%5Cleq%20(c_1%2Bc_2)g_2(n)#card=math&code=n%20%5Cgeq%20max%28n_1%2Cn_2%29%2C%20f_1%28n%29%2Bf_2%28n%29%20%5Cleq%20%28c_1%2Bc_2%29g_2%28n%29)
• Theorem (Transitivity law)
  if %20%3D%20%5Cmathcal%7BO%7D(g_1(n))%2C%20g_1(n)%20%3D%20%5Cmathcal%7BO%7D(g_2(n))#card=math&code=f_1%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_1%28n%29%29%2C%20g_1%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29), then %20%3D%20%5Cmathcal%7BO%7D(g_2(n))#card=math&code=f_1%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29)
• Theorem(Commutative law)
  if %20%3D%20%5Cmathcal%7BO%7D(g_1(n))%2C%20f_2(n)%20%3D%20%5Cmathcal%7BO%7D(g_2(n))%20and%20g_1(n)%20%3D%20%5Cmathcal%7BO%7D(g_2(n))#card=math&code=f_1%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_1%28n%29%29%2C%20f_2%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29%20and%20g_1%28n%29%20%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29), then %20%2B%20f_2(n)%3D%20%5Cmathcal%7BO%7D(g_2(n))#card=math&code=f_1%28n%29%20%2B%20f_2%28n%29%3D%20%5Cmathcal%7BO%7D%28g_2%28n%29%29)

proof: use two theorems above.

• Theorem
  if %20%3D%20a_m%20n%5Em%20%2B%20…%20%2B%20a_1n%20%2B%20a_0#card=math&code=f%28n%29%20%3D%20a_m%20n%5Em%20%2B%20…%20%2B%20a_1n%20%2B%20a_0), then %20%3D%20%5Cmathcal%7BO%7D(n%5Em)#card=math&code=f%28n%29%20%3D%20%5Cmathcal%7BO%7D%28n%5Em%29)
  proof: use the three theorems above.

Some More on Big-O

RECURSIVE-BIN-SEARCH is #card=math&code=%5Cmathcal%7BO%7D%20%28log%20n%29) time and #card=math&code=%5Cmathcal%7BO%7D%28log%20n%29) space
We prefer the tightest Big-O

Stack

mimic: “pile of documents” on your desk

Stack: Last-In-First-Out (LIFO)

Stack
(constant-time) operations:
- insertTop(data), often called push(data)
- removeTop(), often called pop()
- getTop(), often called peek()
LIFO: elevator, wash dishes.
very restricted data structure, but important for computers

A Simple Application: Parentheses Balancing

• in C, the following charaters show up in pairs:(),[],{},””
  good: {xxx(xxxxxx)xxxxx”xxxx”x}
  bad: {xxx(xxxxxx}xxxxx”xxxx”x}
• the LISP programming language
  (append (pow(*(+3 5)2)4)3)

Stack Solution to Parentheses Balancing

• inner-most parentheses pair top-most plate
• Parentheses Balancing Algorithm

    for each c in the input do
        if c is a left character
            push c to the stack
        else if c is a right character
            pop d from the stack and check if match
        end if
    end for

System Stack

• recall: function call take a new scrap paper
• old (original) scrap paper: temporarily not used

System Stack: A stack of scrap paper, each paper (stack frame) contains

• return address: where to return to the previous scrap paper
• local variables(including parameters): to be used for calculating within this function
• previous frame pointer: to be used when escaping from this function

Implementation

Stacks implemented on Array

usually:(growable) consecutive array and push/pop at end-of-array

Stacks Implemented on Linked List

usually: singly linked list and push/pop at head

Stack in STL

stack<int, vector<int>> s_on_array
stack<int, list<int>> s_on_list

implemented as container adapter