Transcript Largest Contiguous Sum

Midterm Review
CSC 172
SPRING 2002
LECTURE 15
Diversity
The Faculty of the College affirms that diversity, pluralism, and respect for difference
are fundamental values in our community. Learning cannot advance in an
atmosphere of prejudice or intimidation. All members of our community -regardless of culture, religion, gender, or sexual orientation -- are entitled to learn
and work in an environment of civility, dignity, fairness, and mutual respect.
As a faculty, we condemn recent events on campus that exhibit bigotry, insensitivity
to life, and hostility toward people on the basis of their ethnicity, religion, or
sexual orientation. These malevolent behaviors and attitudes undermine our
collective work and have no place in our community of learning.
As scholars, we encourage one another -- and as teachers we encourage our students - to reject these expressions of intolerance and work together to build the kind of
open community that makes authentic learning possible. We cannot afford to be
indifferent. We must speak out against these deplorable expressions. We must
expect better of ourselves and of one another.
Thank you,
Sanford L. Segal
Chair of the Faculty Council
Steering Committee
Freedom of thought
Do people have the right to hold wrong opinions?
Do we tolerate intolerance?
Treating people decently does not imply approval.
Professionalism
People have both public and private lives
Sort of like public and private interfaces
public life provides a context for social interaction
public life is to some degree regulated (laws, cultures)
We often deal with people with whom we disagree because
we can share purposes with people
Professionalism allows us to maintain a workable public
interface with diverse people
Tolerance (public) does not imply that you agree (private)
So, it is possible to maintain both workable social
relationships and individual freedom of thought
Scholarship
Being a member of the university community implies
a shared objective – a public society
The tradition of scholarship is a tradition of openness
This implies having the courage to take credit for
your statements
Having to take credit for your statements tends to
“raise the level of discussion”
General Recurrence Relations
The solution to
T(n) = aT(n/b) + O(nk)
O(n
) if a  b
k
k
T (n)  O (n log n) if a  b
k
k
O (n ) if a  b
logb a
k
Proof
Assume T(1) = 1
Assume n is a power of b
n = bm
n/b = bm-1
nk = (bm)k = bmk = bkm = (bk)m
So,
T(bm) = aT(bm-1) + (bk)m
T (b )  aT (b
m
m 1
)  (b )
k m
Divide by am
T (b ) T (b )  b 




m
m 1


a
a
 a 
m
m 1
k
m
T (b ) T (b )  b 




m 1
m2


a
a
 a 
m 1
m2
k
m 1
T (b ) T (b )  b 




m 1
m2


a
a
 a 
m 1
m2
k
T (b ) T (b )  b 




m2
m 3


a
a
 a 
m2
m 3
k
…
1
T (b ) T (b )  b 




1
0


a
a
 a 
1
0
k
m 1
m2
Telescoping
b
T (b )


1


m

a
i 1  a
m
k
m



i
b
T (n)  T (b )  a  
i 0  a
m
m
m
k



i
k
a>b
b
T (n)  T (b )  a  
i 0  a
m
m
m
k



i
The sum is a geometric series with ratio < 1
Since the sum of such an infinite series would
converge to a constant, the finite sum is also bound
by a constant
T (n)  O(a )  O(a
m
logb n
)  O( n
logb a
)
k
a=b
b
T (n)  T (b )  a  
i 0  a
k
m
m
m



i
Each term of the sum is 1
The sum contains 1+logbn terms
a=bk implies logba = k
T (n)  O(a log b n)
m
 O(n
logb a
log b n)  O(n log b n)
k
k
a<b
b
T (n)  T (b )  a  
i 0  a
m
m
m
k



i
The sum is a geometric series with ratio > 1
(Aside)
Prove by induction on n:
n 1
A 1
A


A 1
i 0
n
i
m 1
b 
   1
m  a 
T ( n)  a
k
b 
   1
 a 
k
b
 O(a 
 a
k
m
m

k m
k
 )  O((b ) )  O(n )

Chuck-a-Luck
Show that in Chuck-a-Luck, the probability of any
event in which all three dice have different values
is twice the probability of any event where one
number appears exactly twice and six times the
probability of any event in which all three dice
show the same number.
Chuck-a-Luck
Show that in Chuck-a-Luck, the probability of any
event in which all three dice have different values
is twice the probability of any event where one
number appears exactly twice and six times the
probability of any event in which all three dice
show the same number.
Chuck-a-Luck
An event is a unique throw of the dice
There are 6 different events of all the same number
P(all 1s) = 1/216
P(all 2s) = 1/216
…
P(all 6s) = 1/216
Chuck-a-Luck
There are 120 events where all the numbers are
distinct 6*5*4
But some are indistinguishable
There are 6 ways to arrange 3 items
P(any event where all numbers different) = 6/216
So,
6
3
1
2
6
216
216
216
Chuck-a-Luck
There are 30 different ways of getting the same
number exactly twice 6*5
For each event (say 2 “1s”, and one “2”) there are 3
ways to get it ((1,1,2),(1,2,1),(2,1,1))
P(any event where one number appears twice) =
3/216
Error Correcting Codes
If no two strings in a code differ in fewer than three
positions, then we can actually correct a single
error, by finding the unique string in the code that
differes from the received string in only one
position. It turns out that there is a code of 7 bit
string that corrects single errors and contains 16
strings. Find such a code.
Error Correcting Codes
0000 and 0001 differ by 1
0000 and 0011 differ by 2
0000 and 0111 differ by 3
So, if I only allowed 0000 and 0111 and there was
only one “error”, then I could always recover
0001,0010,0100,1000 -> 0000
1111,0011,0101,0110 -> 0111
Error Correcting Codes
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Error Correcting codes – d 1
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
0
0
0
1
1
0
0
Error Correcting codes – d 1
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
0
0
1
0
0
1
0
Error Correcting codes – d 1
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
0
1
0
0
0
0
0
Error Correcting codes – d 1
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
1
0
0
0
0
0
1
Error Correcting codes – d 2
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
1
1
0
0
1
1
0
Error Correcting codes – d 2
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
1
0
1
0
1
0
0
Error Correcting codes – d 2
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
1
0
0
1
0
1
0
Error Correcting codes – d 2
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
0
1
1
0
0
0
1
Error Correcting codes – d 2
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
0
1
0
1
0
1
1
Error Correcting codes – d 2
a
b
c
d
P(abc) P(abd) P(bcd)
0
0
0
0
1
1
1
0
0
1
1
0
0
1
So, what’s on the exam? (180 min)
Linked Lists (code)
Stacks (algs)
Queues (algs)
Proof by induction (section)
Recurrence Relations (math)
Big-Oh (section)
Run time of code segments
Combinatorics (section)
Probability
Recursion (QS,MS, etc)
Homework Solutions
http://www.cs.rochester.edu/~pawlicki/lectures/CSC172
When and where is the exam
Friday March 8th
8AM-11AM, 632 CSB – 4 students
2PM-5PM, 115 Harkness