01:198:344 Lecture Notes - Lecture 8: Knapsack Problem, Insert Key, Dynamic Programming

• School: Rutgers University
• Department: Computer Science
• Course: 01:198:344
• Professor: Farach- Colton

Document Summary

P (x) = favorable no of outcomes total no of outcomes. Indicator variable x = 1 if an event occurs, 0 otherwise. We have e(x + y ) = e(x) + e(y ). because. E(x) = x x xp (x = x) X y (x + y)p (x = x)p (y = y) xp (x = x)p (y = y) + x x. X y yp (x = x)p (y = y) xp (x = x) + x y yp (y = y) What is the expected number of tails in n tosses of an unbiased coin: keys from 1u . hash function h : 1u {0, . Assume h can be computed in o(1) time. Insert key i in t [h(i)] takes o(1) time. Unsuccessful search for key i takes searching entire list t [h(i)] which in expectation is 1 + n/m. Say keys inserted in order x1, , xn.