CMPS 12B Lecture 12: Class 12 - Assignment 3

6 Pages
Unlock Document

Computer Science
Darrell Long

CMPS 12B Lecture 12 5162017 (3:204:55) Assignment3 Bloom filters You have a wall, and little holes in the wall You have a word named booger o It passes through both filters before getting to the hash table, where you then change the word o Were optimizing for the common case (hence move to front) o Bloom filter has hash function. o Bloom filter code is BitVector code + 2 lines cite your code Move to front: b is for basic, m should be many times faster o Default is no move to front rule Queues o A queue is a data struct with a front (head) and a rear (tail). o We normally think of a queue as a bounded (fixed size) data structure but this is not a requirement. o A buffer is an example of a queue. These are used to match speeds in operating systems (and other software, like networks). o Buffer = a chunk of memory, a queue is a type of buffer o Queues are used for maintaining (ordered) task lists Firstendfirstout o English people stand in queues, Americans stand in line, Italians mob the Gellato place but it is the same thing. o Operations on queues bool empty(q) cant delete more bool full(q) cant add more Finite queue like having not enough seats at a movie theater item dequeue(*q) remove from tail
More Less

Related notes for CMPS 12B

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.