Transcript f (n)

Data Structures
A program solves a problem.
 A solution consists of:
 a way to organize the data
 sequence of steps to solve the problem.
 In other words:
 programs = algorithms + data structures

1
Data Structures

From A to Z


Problem specification
Analysis and Design
 Break up the solution in well-defined
modules
 Specify pre/post-conditions
 Specify how modules interact
 IDEA: separate the purpose of a module
from its implementation
2
Data Structures
Decide how the data will be organized
 Decide what operations can be performed on
data
 IDEA: separate the data organization and
operations from the implementation
 Implementation
 Testing
 Maintenance
 Program must be easy to understand/modify

3
Data Structures

Key ideas:
 Modularity
 break problem into subproblems
 Abstraction
 hide non-relevant information from the user
 Information hiding
 hide data not needed by a module
 Software reuse
 do not reinvent the wheel
4
Data Structures

Abstract Data Type (ADT) =



The user does not know



a collection of data, and
a set of operations on the data. (typical ops?)
the internal representation
the implementations of the operations
The user does know

a conceptual picture of the organization of the data

how to perform operations on it
5
Data Structures

Goals:
 Program must be easy to understand and
modify.
 Design a data structure that can be reused in
other programs.
 Design (or select) the right data structure.
 The program must be correct and efficient
(memory/time).
6
Mathematics Review


Basic formulas for derive and reviews basic proof
techniques
Exponents
X A X B  X A B
XA
A B

X
XB
( X A ) B  X AB
X N  X N  2 X N  X 2N
2 N  2 N  2 N 1
7
Mathematics Review



Logarithms
All logarithms are to the base 2 unless specified otherwise.
Definition:
X A  B if and only if log X B  A, X  0, B  0
 Useful equalities
log c B
log A B 
;C  0
log c A
log AB  log A  log B
log A  log A  log B
B
log x  x, x  0
log 1  0, log 2  1, log 1024  10, log 65536  16
 
8
Mathematics Review
b=2
b=e
b=10
9
Mathematics Review

Series: Geometric
series
N 1
A 1
A 

A 1
i 0
If 0  A  1, then
N
i
N
1
A 

1 A
i 0
i
Derivation
Let S = 1+A+A2+……
(1)
where, 0<A<1
then AS =
A+A2+A3+…(2)
Subtracting (1) and (2),
1
we S
getS-AS = 1, i.e.

1 A
10
Mathematics Review

Series: Arithmetic
series
N ( N  1)
i

2
i 0
N
Example: To find the
sum
2+5+8+….+ (3k-1)
= 3(1+2+3+…+k)
- (1+1+1+….+1)
3k (k  1)

k
2
11
Mathematics Review
The P word
- to proof a false
statement:
proof by counter
example

- to proof a correct
statement
- proof by induction
(1) proving a base case
(2) inductive hypothesis
- proof by contradiction
(1) assume it is false
(2) show that this assumption
is false
12
Algorithms
A problem is a specification of an inputoutput relationship.
 Algorithm =
 a well-defined computational
procedure that takes a set of values as
input and produces a set of values as
output.
 a tool for solving a well-specified
computational problem.

13
Algorithm characteristics
Correctness
 algorithm halts with correct output for
every legal instance of the problem.
 proof of correctness
 Generality
 must work for all legal data (eg. a
sorting algorithm should work on both
numbers and names)

14
Algorithm characteristics
Finiteness
 won’t take forever to run
 Efficiency
 making efficient use of resources (time
and space)

15
Algorithm characteristics


Pseudocode = an English-like language with limited
vocabulary that we use to describe algorithms in an easy
to understand manner.
Example: Linear Search
Input : array A, key x
Output: index of array element equal to x, -1 if x is not in A
for i = 1 to length[A]
if A[i]==x
then return i
endif
endfor
return -1
16
Algorithm characteristics

Is the Linear Search algorithm...
 correct?
 efficient?
 general?
 finite?
17
Algorithm analysis



Analyzing an algorithm = estimating the
resources it requires
Time
 Number of steps/operations executed
 Each operation has a cost
 A function of problem (input) size
Space
 Amount of temporary storage required.
 We usually don’t count the input.
18
Algorithm analysis


Best case analysis
 Given the algorithm and input of size n that
makes it run fastest (compared to all other
possible inputs of size n), what is the running
time?
Worst case analysis
 Given the algorithm and input of size n that
makes it run slowest (compared to all other
possible inputs of size n), what is the running
time?
19
Algorithm analysis

Average case analysis
 Given the algorithm and a typical,
average input of size n, what is the
running time?
20
Insertion Sort


One of the simplest methods to sort an array is an insertion sort. An
example of an insertion sort occurs in everyday life while playing cards.
To sort the cards in your hand you extract a card, shift the remaining
cards, and then insert the extracted card in the correct place. This
process is repeated until all the cards are in the correct sequence. Both
average and worst-case time is O(n2).
Assuming there are n elements in the array, we must index through n - 1
entries. For each entry, we may need to examine and shift up to n - 1
other entries, resulting in a O(n2) algorithm. The insertion sort is an inplace sort. That is, we sort the array in-place. No extra memory is
required. The insertion sort is also a stable sort. Stable sorts retain the
original ordering of keys when identical keys are present in the input
data.
21

Starting near the top of the array in Figure (a), we
extract the 3. Then the above elements are shifted
down until we find the correct place to insert the 3.
This process repeats in Figure (b) with the next
number. Finally, in Figure (c), we complete the sort
by inserting 2 in the correct place.
22
Algorithm Analysis
InsertionSort(A)
cost  times executed
for i=2 to length(A)
c1  n
item = A[i]
c2  n-1
j=i-1
c3  n-1
while (j > 0 and A[j] > item)
c4  ti
A[j+1] = A[j]
c5  (ti-1)
j=j-1
c6  (ti-1)
A[j+1] = item
c7  n-1
23
Algorithm Analysis
Observations:
 the constants are “unimportant” details
 some terms “grow” faster than others as
the size of the input increases.
 Let’s simplify this...

24
Algorithm Analysis
Consider:
2
 n + 100n + 1000
 How does this change as n becomes
larger?
 Is this a “good” running time?
 Compare:
 n2/3 to 3n
 Do the constants really make a difference?
25

Algorithm Analysis

Idea:
 comparing algorithms:
 upper bounds
 lower bounds
 tight bounds
 we are interested in the growth rate of an
algorithm: how its running time changes
proportional to the size of the input.
26
Algorithm Analysis: Big Oh



A function f(n) is O(g(n)) if there exist constants
c, n0>0 such that f(n) c·g(n) for all n  n0
What does this mean in English?
 c·g(n) is an upper bound of f(n) for large n
Examples:
2
2
 f(n) = 3n +2n+1 is O(n )
 f(n) = 2n is O(n2) (it is also O(n) )
3
10
 f(n) = 1000n is O(n )
27
Algorithm Analysis: Omega
A function f(n) is (g(n)) if there exist
constants c, n0>0 such that
f(n)  c·g(n) for all nn0
 What does this mean in English?
 c·g(n) is a lower bound of f(n) for large n
 Example:
 f(n) = n2 is (n)

28
Algorithm Analysis: Theta



A function f(n) is (g(n)) if it is both O(g(n)) and
(g(n)) , in other words:
 There exist constants c1,c2,n>0 s.t.
0  c1 g(n)  f(n)  c2g(n) for all nn0
What does this mean in English?
 f(n) and g(n) have the same order of growth
  indicates a tight bound.
Example:
 f(n) = 2n+1 is (n)
29
Algorithm Analysis




O, ,  are transitive and reflexive
 is symmetric
f(n) = O(g(n)) iff g(n) = (f(n))
analogy:
 f(n) = O(g(n))  a  b
 f(n) = (g(n))  a  b
 f(n) = (g(n))  a = b
 Note: this doesn’t mean that all functions are
asymptotically comparable
30
Growth of functions
• A way to describe behavior of functions in the limit
-- asymptotic efficiency.
• Growth of functions.
• Focus on what’s important by abstracting away low-order
terms and constant factors.
• How to indicate running times of algorithms?
• A way to compare “sizes” of functions:
O≤
≥
=
o<
ω>
31
32
Standard notations and common functions

Monotonicity:
 f (n) is monotonically increasing if m ≤ n ⇒ f (m) ≤ f (n).
 f (n) is monotonically decreasing if m  n ⇒ f (m) ≥ f (n).
 f (n) is strictly increasing if m < n ⇒ f (m) < f (n).
 f (n) is strictly decreasing if m  n ⇒ f (m) > f (n).

Floor and Ceilings: x – 1 <  x   x   x  < x+1
Modular arithmetic: a mod n = a - a/n n






-- refer to the textbook (p36-38).
Polynomials:
Exponentials:
Logarithms:
Factorials:
33
Algorithm Analysis

What if a constant is too large?
10
2
 Consider 10 n as compared to n
34
Algorithm analysis
Input: Collection of size n
Output: The smallest difference between any two
different numbers in the collection
Algorithm:
List all pairs of different numbers in the collection
estimate=difference between values in first pair.
for each remaining pair
compute the difference between the two values
if it is less than estimate
set estimate to that difference
return estimate
35
Algorithm analysis
Input: Collection of size n
Output: The smallest difference between any two
different numbers in the collection
Algorithm:
estimate = infinity
for each value v in the collection
for each value u  v
if |u-v| < estimate
estimate = |u-v|
return estimate
36