Transcript Insert(S,x)

ADS 1
Algorithms and Data Structures 1
 Syllabus
 Asymptotical notation
 (Binary trees,) AVL trees, Red-Black trees
 B-trees
 Hashing
 Graph alg: searching, topological sorting,
strongly connected components
 Minimal spaning tree (d.s. Union-Find)
 Divide et Impera method
 Sorting: low approximation of sorting problem,
average case of Quicksort, randomization of
Quicksort, linear sorting alg.
 Algebraic alg. (LUP decomposition)


Literature
T.H. Cormen, Ch.E. Leiserson, R.L. Rivest,
Introduction to Algorithms, MIT Press, 1991

Organization

Lecture

Seminar
Comparing of algorithms



Measures:

Time complexity, in (elementary) steps

Space complexity, in words/cells

Communication complexity, in packets/bytes
How it is measured:

Worst case, average case (wrt probability distribution)

Usually approximation: upper bound
Using functions depending on size of input data

We abstract from particular data to data size

We compare functions
Size of data

Q: How to measure the size of (input) data?

Formally: number of bits of data



Ex: Input are (natural) numbers
size D of input data is
,
Time complexity: a function f: N->N, such that
f(|D|) gives number of algorithm steps
depending on data of the size |D|
Intuitively: Asymptotical behaviour: exact graph
of function f does not matter (ignoring additive
and multiplicative constants), a class of f
matters (linear, quadratic, exponential)
Step of algorithm

In theory: Based on a abstract machine:
Random Access Machine (RAM), Turing m.


Informally: algorithm step = operation executable in
constant time (independent of data size)
RAM, operations:

Arithmetical: +, -, *, mod, <<, && …

Comparision of two numbers

Assignment of basic data types (not for arrays)

Numbers have fixed maximal size

Ex: sorting of n numbers: |D| = n

(Contra)Ex: test for zero vector
Why to measure time comlexity

Why sometimes more quickly machine doesn't help

Difference between polynomial and worse algs.
Asymptotical complexity

Measures a behaviour of the algorithm on „big“
data


It supress additive and multiplicative constants


It ignores a finite number of exceptions
Abstracts from processor, language, (Moore law)
Classifies algs to categories: linear, quadratic,
logarithmic, exponential, constant ...

Compares functions
(Big) O notation, definitions

f(n) is asymptotically less or equal g(n),
notation
iff

f(n) is asymptotically greater or equal g(n),
notation
, „big Omega“
iff

f(n) is asymptotically equal g(n),
notation
iff
, „big Theta“
O-notation, def. II

f(n) is asymptotically strictly less than g(n),
notation
, „small o“
iff

f(n) is asymptotically strictly greater than g(n),
notation
, „small omega“
iff

Examples of classes: O(1), log log n, log n, n,
n log n, n^2, n^3, 2^n, 2^2n, n!, n^n, 2^(2^n),...

Some functions are incomparable
Exercise

Notation: sometimes is used f=O(g)

Prove: max(f,g) ɛ Θ(f+g)

Prove: if c,d>0, g(n)=c.f(n)+d then g ɛ O(f)

Ex.: if f ɛ O(h), g ɛ O(h) then f+g ɛ O(h)


Appl: A bound to sequence of commands
Compare n+100 to n^2, 2^10 n to n^2

Simple algorithms (with low overhead) are
sometimes better for small data
Dynamic sets

Data structures for remembering some data

Dynamic structure: changes in time

An element of a dynamic d.s. is accesible
through a pointer and has
1. A key, usually from some (lineary) ordered set
2. Pointer(s) to other elements, or parts of d.s.
3. Other (user) data (!)
Operations


S is a dynamic set, k is a key, x is a pointer to a
element
Operations

Find(S,k) – returns a pointer to a element with the
key k or NIL

Insert(S,x) – Inserts to S an element x

Delete(S, x) – Deletes from S an element x

Min(S) – returns a pointer to an element with
minimal key in S

Succ(S,x) – returms a pointer to an element next to
x (wrt. linear ordering)

Max(S), Predec(S,x) – analogy to Min, Succ
Binary search trees

Dynamic d.s. which supports all operations