Transcript CSE 220 (Data Structures and Analysis of Algorithms)

CSE 220 (Data Structures and
Analysis of Algorithms)
Instructor: Saswati Sarkar ([email protected])
T.A. Dimosthenes Anthomelidis
([email protected])
Course Web Page:
http://www.seas.upenn.edu/~swati/cse220.html
Timings
Class MWF: 12-1, 224 Moore
Instructor Office Hours: 11-12, Friday, 360 Moore (correction)
1-2 Wednesday 360 Moore
T.A. Office Hours: Monday 11-12, Friday 1-2, 329 Pender
Recital: Wednesday 5-6 (Moore 216)
Text Books
Data Structures and Algorithm Analysis in C
Mark Allen Weiss
Data Structures Using C
Yedidyah Langsam
Prerequisites
Knowledge of C
CSE 260?
Grading
Weekly Homeworks (30%)
Posted every Monday
Due Next Monday before class (solution posted after
class)
First Homework will be posted on 29th January
No consultation allowed
No late submission accepted
1 Midterm: 30% (last class before spring break)
Cumulative Final: 40%
Course Content
Course Motivation
Mathematical Foundation:
Complexity Analysis:
Data Structures: List, Stacks, Queues
Algorithm: Searching and Trees
Sorting and Heaps
Graph Algorithms (Depth first Search,
Breadth First Search, Topological sort,
Shortest path algorithm, Spanning Tree
Algorithm)
Computability and Complexity
2 review lectures
No class on April 25
No class on either April 23 or April 27 (will confirm
later)
Course Motivattion
Need to run computer programs efficiently!
Computer program:
Accepts Input (Data)
Performs a Sequence of action with the
input
Generates Output (Data)
Efficient Management of Data
(Data Structures)
Efficient Sequence of Actions
Algorithms
Algorithms
Sequence of actions a ``dumb’’ machine can follow
For j=1 to N
print j
Efficient versus Inefficient algorithm
Linear Search Vs Binary Search
Design of Algorithms
You have a problem to solve
Design an efficient algorithm
Use good data structures
Show that your algorithm works!
Prove its correctness
Study the efficiency of your algorithm
Formal Study of Algorithms
Design of Algorithms
Proving Correctness of Algorithms
Formal study of efficiency of algorithms
Run time
Storage required
Mathematical Foundation
Series and summation:
1 + 2 + 3 + ……. N = N(N+1)/2
(arithmetic series)
1 + r2 + r3 +………rN-1 = (1- rN)/(1-r),
 1/(1-r) ,
(geometric series)
r < 1, large N
Sum of squares:
1 + 22 + 32 +………N2 = N(N + 1)(2N + 1)/6
Properties of a log Function
logxa = b if xb = a
(we will use base 2 mostly, but may use
other bases occasionally)
Will encounter log functions again and again!
log n bits needed to encode n messages.
log (ab ) = log a + log b
log (a/b ) = log a - log b
log ab = b log a
logba = logca/ logcb
alog n = nlog a
amn = (am )n = (an)m
am+n = am an
(2n)0.5 (n/e)n 
n  (2n)0.5 (n/e)n + (1/12n)
We will deduce the value of the descending geometric
series:
N + Nr + Nr2 + Nr3 +………1
Example: N + N/2 + N/4 + …… + 1
The summation equals (N-r)/(1-r)
For r = 2, this is 2N - 1
Proof By Induction
Prove that a property holds for input size 1
Assume that the property holds for input size
1,2,…n. Show that the property holds for input
size n+1.
Then, the property holds for all input sizes, n.
Prove that the sum of 1+2+…..+n = n(n+1)/2
Holds for n = 1
Let it hold for 1,2…..n
1+2+….+n = n(n+1)/2
1+2+….+n+(n+1) = n(n+1)/2 + (n+1)
= (n+1)(n+2)/2.
Fibonacci Numbers
Sequence of numbers, F0 F1 , F2 , F3 ,…….
F0 = 1, F1 = 1, F2 = 2, F3 = 3,…….
Fi = Fi-1 + Fi-2 ,
Will prove that FN
i=1N-2 Fi
< N
= FN - 2
Holds for N = 1
Let it hold for 1,2,….N
FN+1 = FN
< N
=
+ FN-1
+
N-1
N-1 (1 +  )
= N-1 2
= N+1
 = (1+sqrt(5))/2
N > 2 (Correction)
Proof By Counter Example
Want to prove something is not true!
Give an example to show that it does not hold!
Is FN  N2 ?
No, F11 = 144
However, if you were to show that FN  N2 then you
need to show for all N, and not just one number.
Proof By Contradiction
Suppose, you want to prove something.
Assume that what you want to prove does not hold.
Then show that you arrive at an impossiblity.
Example: The number of prime numbers is not finite!
Suppose there are finite number of primes, k primes.
(we do not include 1 in primes here)
We know k2.
Let the primes be P1, P2 ,
Z
= P1 P2
………
………
Pk
Pk + 1
Z is not divisible by P1, P2 ,
Z is greater than P1, P2 ,
………
………
Pk
Pk Thus Z is not a prime.
We know that a number is either prime or divisible by primes.
Hence contradiction.
So our assumption that there are finite number of primes is
not true.