COMPSCI 61B Lecture Notes - Lecture 23: Base32, Pigeonhole Principle, Linked List
1 Jun 2017
School
Department
Course
Professor
Document Summary
Most likely midterm 2 time, friday 4/7 at 4 pm. If you have a con ict, we"ll have a makeup form. Coursera exercises were supposed to be done 10 months ago. One extreme approach: all data is really just bits. Downsides of this approach (that we can maybe x): To support checking presence of all positive integers, we need 2 billion booleans. What is the catth element of an array. One idea: use the rst letter of the word as an index. Treat the string as a n-digit base 27 number c: 3rd letter of alphabet, a: 1st letter, t: 20th letter. Thus the index of cat is 3*272 + 1*27 + 20. We"ll use the base 32 approach in lecture. Each letter is exactly 5 bits (32 = 25) Multiplying by 32 is equivalent to shifting right by 5 places. For strings, this was relatively straightforward (treat as a base 27 or base.
