EECS 376 Review Session
Randomized Algorithms and Analysis
u Random Variables and Expectation
Copyright By PowCoder代写 加微信 powcoder
u Linearity of Expectation
u Randomized Approximations and Markov’s Inequality u Las Vegas, Monte Carlo Methods and Chernoff Bounds
Random Variables
CO, CO] É= numberof
6s rolledin towks –
u A random vari•able X can be regarded as a function from the sample space Ω
tothesetofrealnumbers,i.e.,”∶ Ω→R ,
u “=’! isanevent I::÷÷::: u ! = #! = $ ∈ Ω ∶ ! $ = #!
u Expectation of a random variable is the “a-verage” value that the random
variable takes on 9 1 u
°,I,7,3,4,.. ✗’U
10 polls – experiment 5 lines
A= Ca, , 92, . . . . Gn) Pv(MueangseqHartigfourorders0)
Linearity of Expectation
X i = / 1 ” henry happen, 0 Otherwise
indicatorRVs, Prcsomething
F-Exit = =
Pr ( ✗i -_
happen ) 1- Prcxi =
Protheroe ) equation
expectation
Note : ✗ is
RVs= sumof
have to be
independent
Randomized Approximations
u Idea: exploit randomness to construct simple algorithms that produce some (- approximation in expectation
u i.e., the expected value of the output is within a factor of ( of the optimal
u Example: assigning truth value of each variable randomly for the Max-E3SAT
p r o b l e m ( m a x i m i z e n u m b e r o f s a t i s f i e d c l a u s e s i n a n e→x a c t 3 C N F f o r m u l a ) g i v e s “# – approximation
I✗Vyv2 )a[✗vyv>2)
Markov’s (/Reverse Markov’s) Inequality
meangrade 60
-60- F-[×]
2 scores \
90) ≤ Prl✗s>É?
Ra÷ndomized Algorithms
u Las Vegas a
u Output is always correct
u Expected runtime of algorithm is bounded
u Monte Carlo
u Output is not always correct
u Runtime of algorithm is bounded
u One-Sided Error Randomized Algorithms
No false positives
– worst-case
runtim e IT unbraided
No false negatives
One-Sided Error Amplification
O-O001 0.9999
– loop on times] of
Chernoff Bounds
cc sie ) ”
Randomised
approximation
edge i is in CCS , T ) – ◦ teenage
i – c a , V ) -\ u n c – S s i n , ✓ c – T
Prlxi=D= I
✗:= #edgesin ((Si)
u c-T, uts
u c- S , ✓c- – forparticular run 4-the algorithm
E-Ex] =EiÉ✗it=
?_?E-Exit ,,
?_?,Prl✗i=H=
for any edge e – In ,v ) c- F-
add u add a
neighborhoods
i. What are the
different hats
Prl- – -7 ≥ t
is first ÷
lhj.hu, , . . .
Lhihicihiei.
has 6 permutations , Gf
that could neighborhoods –
iii.Xi-{‘ hic-C I =”¥Xi
¥gEE✗i)± ?_?, ÷= 3- Prcxi– 1) ≥ ±
↳¢, 11=-114]=
iv. idea :
Recommend : Diruass.vn
OPT ≤ n VEEICI ] ≥
Encryption
u Information Theoretic Security (unconditional):
Cannot learn the secret from the ciphertext even with unlimited computing
u Computational Security (conditional):
In order to learn the secret from the ciphertext you would have to solve a computationally hard problem
Two Simple Encryption Schemes
u One Time Pad:
u Information Theoretic, cannot get any information knowing the ciphertext
u Have a key 𝑘 = {𝑘$, 𝑘%, ⋯ , 𝑘&}, shift the first character of your message by 𝑘$, the second character by 𝑘%, etc. (mod 26)
u Drawbacks: Need a key as long as the message, cannot use the same key twice or statistical attacks can be used
u Have a key 𝑘, shift all characters in the message by that key (mod 26) u Breakable by statistical attacks
u Not an encryption scheme, allows you to create a secret shared key u Pick a prime 𝑝 and a generator for that prime 𝑔, then:
u Eve knows and wants to learn the shared key
u She can try to compute 𝑎 (i.e. solve the Discrete Log Problem) by trying consecutive powers of g, but this is inefficient (𝑂(𝑝)) WRT the input size (𝑂(log(𝑝)))
RSA Encryption
u An asymmetric encryption scheme that allows other people to encode messages which only you can decode
u Relies on the difficulty of factoring large numbers
RSA Correctness and Security
u For an attacker to determine the message 𝑚 from the ciphertext 𝑐, they would need to have access to the private key 𝑑. The public information is 𝑛, 𝑒 and 𝑐, so to find 𝑑 they would need to @ind e ∗ d ≡ 1 mod(φ(𝑛)).
u You could do this with the Extended Euclidean Algorithm if you knew φ(𝑛), however to find this you would need to factor 𝑛 into 𝑝, 𝑞 which is believed to be hard
RSA Signatures
u Signing a message is designed to show someone that you are the sender, not to encrypt the message.
u Very similar to encrypting a message, but you sign it with your private key and send that ciphertext and the original message, then other parties can authenticate it using the public key
u Note this is still secure: you either need to find d from 𝑚” or factor n
RSA Example 1
RSA Example 2
RSA Example 2 Continued
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com