HomeClass Notes1,200,000CA670,000

CISC 235 Lecture Notes - Lecture 14: Donald Knuth, American Broadcasting Company

48 views3 pages

amaranthcricket401

8 Mar 2016

School

Queen's University

Department

Course

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

In most of our examples we used h(k) = k % m. this may not be a good choice. A well-designed hash function should try to incorporate all the information in the key - when we use something as simple as k % m we are potentially throwing away most of the information. For example if m = 100, the key values 16 and. 34324392316 will both hash to the same address. Another issue to consider is that ideally, every address in the table should be equally likely to be the first address in a probe sequence. As an example of a hash function that uses all the information in the key but fails on this second issue is this: h(k) = sum of the digits of k. To see that this fails the second test, suppose the keys are 10-digit telephone numbers, and we have a table with 1000 addresses.

Related Documents

CISC 235 Lecture Notes - Lecture 12: Self-Balancing Binary Search Tree, Binary Tree, Null Pointer

amaranthcricket401

CISC 235 Lecture Notes - Lecture 13: Quadratic Probing, Linear Probing, Hash Table

amaranthcricket401

CISC 235 Lecture Notes - Lecture 21: Bit Array, The Algorithm, Bloom Filter

amaranthcricket401

Related Questions

This is just information the question will be next photo

Sketch using these guidelines

pul aill al thes information together to sketch graphs that reveal the important You might ask: Why don't we just use a graphing calculator or computer to graph a It's true that modern technology is capable of producing very accurate graphs. But K 21+1+2 features of functions curve? Why do we need to use calculus? even the best graphing devices have to be used intelligently. It is easy to arrive at a misleading graph, or to miss important details of a curve, when relying solely on tech- nology. (See "Graphing Calculators and Computers" at www.stewartcalcelus.com, espe 4 discover the most interesting aspects of graphs and in many cases to and minimum points and inflection points exocily instead of approximately cially Examples 1, 3.4, and 5. See also Section 4.6.) The use of calculus enables us to calculate maximum FIGURE 1 For instance, Figure I shows the gr aph of /(x)-è¨-21x, + 18x + 2.At first glance it seems reasonable: It has the same shape as cubic curves like y x and it appears to have no maximum or minimum point. But if you compute the derivative, you will see that there is a maximum when x-0.75 and a minimum when x 1. Indeed if we zoom in to this portion of the graph, we see that behavior exhibited in Pigure 2 Without calculus, we could easily have overlooked it. 6a, FIGURE 2 In the next section we will graph functions by using the interaction between calculus and graphing devices. In this section we draw graphs by first considering the foilowing information. We don't assume that you have a graphing device, but if you do have one you should use it as a check on your work. â Guidelines for Sketching a Curve every item is relevant to every function. (For instance, a to make a sketch that displays the most important aspects of the function. The following checklist is intended as a guide to sketching a curve y- f(x) by hand. Not given curve might not have an asymptote or possess symmetry.) But the guidelines provide all the information you need A. Domain It's often useful to start by determining the domain D of f, that is, the set B. Intercepts The y-intercept is f(o) and this tells us where the curve intersects the of values of x for which f(x) is defined y-axis. To find the x-intercepts, we set y-0and solve for xã(You can omit this step if the equation is difficult to solve.) ry (a) Even fusction: reflectional symmetry all x in D, that is, the equation of the curve is unchanged when x is replacea by -x, then f is an even function and the curve is symmetric about the y-axis. This means that our work is cut in half. If we know what the curve looks like for 0, then we need only reflect about the y-axis to obtain the com- plete curve [see Figure 3(a). Here are some examples: y-ey-ry x). and for all x in D, then f is an odd function and the curve is symmetric about the origin. Again we can obtain the complete curve if we know what it looks like for x0. [Rotate 180Â° about the origin; see Figure 3(b).] Some b) Oud function rotational symmetry FIGURE 3 simple examples of odd functions are y-xy-x'y - and y-sin