Datos estructurados

CSCI 362 : Data Structure
Fall, 2007

Part I: Data Structures & Algorithm Analysis

CSCI 362: Data Structure (Fall, 2007 )

Dept. of Computer and Information Science, IUPUI

Chap. 1Introduction
1.1 Introduction – Data Structures: methods of organizing large amount of data (input data, output data, run-time data)

– Algorithm analysis: estimation of running time of algorithms – Goals• Various data structures, their properties, operations, implementations, & applications • Data structure design skills for problem solving • Algorithm design and analysis skill
CSCI 362: DataStructure (Fall, 2007 )
Dept. of Computer and Information Science, IUPUI

1

– Algorithm analysis examples
• Finding the kth largest number among a group of N numbers
Bubble sort vs. k elementspartition

N2 k

k2+(N-k)(i+k-i) < N2 i • Traveling salesman problem • Street scanning problem

CSCI 362: Data Structure (Fall, 2007 )

Dept. of Computer and Information Science, IUPUI

1.2Mathematics review – Exponents
X A X B  X A B X A / X B  X A B
( X A ) B  X AB

– Logarithms
X A  B  log X B  A log A B  log C B / log C A log AB  log A  log B log l A/ B  l Al B loglog
log( A B )  B log A log X  X (for all X  0) log 1  0, log 2  1, log 1024  10,...
CSCI 362: Data Structure (Fall, 2007 )
Dept. of Computer and Information Science, IUPUI

( B, X  0, X 1)
log 2 A  log A log10 A  lg A log e A  ln A

2

– Series

A
i 0 

N

i



A N 1  1 , A 1
N 0

2
0

N

i

 2 N 1  1 1 1 A

If 0  A  1 

A

i

A
i 0 N 1

i



1 (0  A  1) : geometric series 1 A

i  i
1 N 2

N ( N  1)  N2 /2 2 N ( N  1)(2 N  1)  N3 /3 6
ex. 2  5  8  ...  (2k  1)



i
1

N

k

 Nk 1 | k  1 | (k  1)
N 1 H N    log e N  ln N 1 i

Harmonic number Euler’s Constant:

 f ( N )  Nf ( N )
i 1 N i  n0

N

  lim | H N  ln N | 0.57721566
N 

 f ( N ) ...