题目内容

Next we toss a huge ball with 1,000 dots on it. Half the dots are red and the other half are blue. We roll the ball and when it stops, we note the color of the dot on the very top of the ball.True or False? If we roll it four times, and it comes up red once and blue three times, then we have proved that the ball is biased.

查看答案

搜索结果不匹配？点我反馈

更多问题

A fair two-sided coin is flipped 4 times. It comes up heads all four times. What is the probability that it comes up heads on the fifth flip? Answer in reduced fraction form - eg 1/5 instead of 2/10.______

Hash table size = 10 buckets; number of unique insertions = 100Expected average length of the list for each bucket =______

Hash table size = 10 buckets; number of unique insertions = 20Expected average length of the list for each bucket =______

Imagine we implement a dictionary, all of whose keys are U.S. social security numbers (9 digit numbers). If we used a list with 109 elements to represent the dictionary, we could do lookups in constant time. Of course, if the dictionary contained entries for only 20 people (or, for that matter, only 3∗108 people), this would waste quite a lot of space.Which gets us to the subject of hash functions. A hash function maps a large space of inputs (e.g., all natural numbers) to a smaller space of outputs (e.g., the natural numbers between 0 and 5000). The space of possible outputs should be much smaller than the space of possible inputs!A hash function is "many-to-one", that is, multiple different inputs are mapped to the same output. When two inputs are mapped to the same output, it is called a collision. A good hash function produces a uniform distribution, i.e., every output in the range is equally probable, which minimizes the probability of collisions.Remember the intDict code from the previous video? intDict uses a simple hash function (modulus) to implement a dictionary with integers as keys. The basic idea is to represent instances of class intDict by a list of buckets, where each bucket is a list of (key, value) tuples. By making each bucket a list, we handle collisions by storing all of the values that hash to that bucket.Collisions are inevitable when implementing hash tables, because generally we are mapping a really big set of inputs to a much smaller set of buckets. Thinking about the way that intDict implements hashing - making each bucket a list, and assigning each element to one bucket's list - what is the expected average length of the list in each bucket of the hash table when the hash table is 10 buckets big for the following number of unique insertions (that is, no two elements inserted are equal)?Hash table size = 10 buckets; number of unique insertions = 10Expected average length of the list for each bucket =______