Transcript Data Structures and Algorithms

TCSS 342
Data Structures &
Algorithms
Autumn 2004
Ed Hong
TCSS 342 Autumn 2004
Version 1.1
1
Course Objectives
• (Broad) Prepare you to be a
good software engineer
• (Specific) Learn basic data
structures and algorithms
– Data structures – how data is
organized
– Algorithms – unambiguous
sequence of steps to compute
something
TCSS 342 Autumn 2004
Version 1.1
2
Software Design Goals
TCSS 342 Autumn 2004
Version 1.1
3
Course Content
Data Structures
Algorithms
Data Structures + Algorithms =
Programs
Algorithm analysis – determining how
long an algorithm will take to solve a
problem
Who cares? Aren’t computers fast
enough and getting faster?
TCSS 342 Autumn 2004
Version 1.1
4
An Example
Given an array of 1,000,000 integers,
find the maximum integer in the array.
…
0
1
2
999,999
Now suppose we are asked to find the
kth largest element. (The Selection
Problem)
TCSS 342 Autumn 2004
Version 1.1
5
Candidate Solutions
+ Candidate solution 1
Sort the entire array (from small to
large), using Java’s Arrays.sort()
Pick out the (1,000,000 – k)th
element.
+ Candidate solution 2
Sort the first k elements.
For each of the remaining
(1,000,000 – k) elements,
keep the k largest in an array.
Pick out the smallest of the k
survivors.
TCSS 342 Autumn 2004
Version 1.1
6
Is either solution good?
• Is there a better solution?
• How would you go about
determining the answer to these
questions?
TCSS 342 Autumn 2004
Version 1.1
7
Method 1
Code each algorithm and run them to
see how long they take.
Problem: How will you know if there
is a better program or whether there
is no better program?
What will happen when the number of
inputs is twice as many? Three? A
hundred?
TCSS 342 Autumn 2004
Version 1.1
8
Method 2
Develop a model of the way computers
work and compare how the
algorithms behave in the model.
Goal: To be able to predict
performance at a coarse level. That
is, to be able to distinguish between
good and bad algorithms.
Another benefit: when assumptions
change, we can predict the effects of
those changes.
TCSS 342 Autumn 2004
Version 1.1
9
Why algorithm analysis?
As computers get faster and problem
sizes get bigger, analysis will
become more important.
Why? The difference between good
and bad algorithms will get bigger.
TCSS 342 Autumn 2004
Version 1.1
10
Why data structures?
When programming, you are an
engineer.
Engineers have a bag of tools and
tricks – and the knowledge of which
tool is the right one for a given
problem.
Arrays, lists, stacks, queues, trees, hash
tables, graphs.
TCSS 342 Autumn 2004
Version 1.1
11
Software Development
Practices
• Modular code
• Appropriate commenting of code
– Each method needs a comment
explaining its parameters and its
behavior.
• Debugging with integrated
development environment (IDE)
• Incremental development
• Unified modeling language (UML)
TCSS 342 Autumn 2004
Version 1.1
12
Mathematical Background
• Exponents
XA XB = XA+B
XA / XB = XA-B
(XA)B = XAB
XN+XN = 2XN
2N+2N = 2N+1
• Logarithms
Definition: XA = B if and only if
logX B = A.
TCSS 342 Autumn 2004
Version 1.1
13
Logarithms, continued
• log AB = log A + log B
• Proof:
log C B
log A B 
A, B, C  0, A  1
log C A
TCSS 342 Autumn 2004
Version 1.1
14
Logarithms, Series
• log A/B = log A – log B
• log (AB) = B log A
Series
N
i
N 1
•
2

2
1

i 0
• binary representation of
numbers
N ( N  1)
i

2
i 1
N
TCSS 342 Autumn 2004
Version 1.1
15
Series
• Geometric progression: for a>0,
a ≠1
a
N
i
N 1
a

(
1

a
) /(1  a)

i 0
TCSS 342 Autumn 2004
Version 1.1
16
Boolean Logic
• Let P and Q be statements.
• “not P” is true if P is false.  P
• “P and Q” is true if both P and
Q are true. P  Q
• “P or Q” is true if one of or both
PQ
P or Q are true.
• “P implies Q” is true if P is false
or Q is true (or both).
PQ
 P  Q
TCSS 342 Autumn 2004
Version 1.1
17