What can computers do?
Count:
Add: Numerical Analysis
Compare:
Search
Order
What is a Data Type?
Machine representation of numbers
What is Data Structure?
Abstract Data Type:
Data
Operations
Data
Structure: Implementation
Typical Uses: Data files etc.
What you need to remember about data structure:
ADT: name and methods
List of DS associated with ADT
idea of implementation
important algorithms
running time or complexity
storage
Different machine different running time
Different loads different time
Different programmers different times
As CS programmers we are hired to solve big problems.
What is problem size? Data size or number of basic elements.
Counting operations
Counting primitive operations
Counting loop iterations
Example:
int arrayFind(x, A)
// input: element, x and array A
// output: index i such that x == A[i]
i=0
while i < n // length of A
if x =A[i] then return i
else i++
return -1 // fail to find
Average and worst case are different.
What about something even more general?
Definition of Big O:
f is O(g) <=> Exist integer N and real constant c so that f(n) < cg(n) for all n>N
Intuitively: g is an upper bound for f
This gives times in terms of Order: logarithmic, linear,
quadratic, exponential.
Comparison of different families
Practical examples:
5n + 5 is O(n) because 5n + 5 < 6n for all n > 6.
5n2 + 10 is O(n2) because 5n2 + 10 < 6n2 for all n > 2.
3 lg n + 5 is O(lg n) because 3 lg n + 5 < 4 lg n for all n > 106.
Others asymptotic bounds:
big Omega: g is a lower bound of f <=> g is O(f)
big Theta: g is a strict bound of f <=> f is O(g) & g is O(f)
Are the examples above also big Theta?
Asymptotic Analysis:
Consider prefix average: A[i] = Average of { X[0] to X[i] } = Sum up to i of X[j]/i+1
Algorithm: prefixAvg1(X)
Let A be an array
for i = 0 to n -1 do
a = 0
for j = 0 to i do
a = a + X[j]
A[i] = a/(i+1)
return A
What is the asymptotic running time?
Algorithm: prefixAvg2(X)
Let A be an array
s = 0
for i = 0 to n -1 do
s = s + X[j]
A[i] = s/(i+1)
return A
What is the asymptotic running time of this one?