Questions
0. Introduction. This laboratory assignment involves designing a perfect hash function for a small set of...

0. Introduction.

This laboratory assignment involves designing a perfect hash function for a small set of strings. It demonstrates that a perfect hash function need not be hard to design, or hard to understand.

1. Theory.

We’ll start by reviewing some terminology from the lectures. A hash function is a function that takes a key as its argument, and returns an index into an array. The array is called a hash table. The object that appears at the index in that array is the key’s value.The key’s value is somehow associated with the key.
      A hash function may return the same index for two different keys. This is called a collision. Collisions are undesirable if we want distinct values to be associated with distinct keys. A hash function that has no collisions for a set of keys is said to be perfectfor that set. Note that a hash function may be perfect for some sets of keys, but not perfect for others.
      Most modern programming languages use a small set of reserved names as operators, punctuation, and syntactic markers. (They’re also called reserved words or keywords.) For example, Java currently uses reserved names like if, private, while, etc.
      A compiler for a programming language must be able to test if a name in a program is reserved. Programs may be hundreds or thousands of pages long, and may contain thousands or even millions of names. As a result, the test must be done efficiently. It might be implemented using a hash table and a perfect hash function.
      Here’s how the test may work. Suppose that the hash table T is an array of strings. Each time the compiler reads a name N, it calls a perfect hash function h to compute an index h(N). If h(N) is a legal index for T, and T[h(N)] = N, then the name is reserved, otherwise it is not. Unused elements of T might be empty strings "". If we measure the efficiency of a test by the number of string comparisons it performs, then the test requires only O(1) comparisons. Of course this works only if h is perfect for the set of reserved names.
      Now suppose there is a very simple programming language that uses the following set of twelve reserved names.

and

else    

or

begin

end

return

define  

if

then

do

not

while

We might define a perfect hash function for the reserved names in the following way. We get one or more characters from each name. Then we convert each character to an integer. This is easy, because characters are already represented as small nonnegative integers. For example, in the ASCII and Unicode character sets, the characters 'a' through 'z' are represented as the integers 97 through 122, without gaps. Finally, we do some arithmetic on the integers to obtain an index into the hash table. We choose the characters, and the arithmetic operations, so that no two reserved names result in the same index.
      For example, if we define the hash function h so that it adds the first and second characters of each name, we get the following indexes.

h("and")

  =  

207

h("begin")

  =  

199

h("define")

  =  

201

h("do")

  =  

211

h("else")

  =  

209

h("end")

  =  

211

h("if")

  =  

207

h("not")

  =  

221

h("or")

  =  

225

h("return")

  =  

215

h("then")

  =  

220

h("while")

  =  

223

This definition for h does not result in a perfect hash function, because it has collisions. For example, the strings "and" and "if" result in the index 207. Similarly, the strings "do" and "end" result in the index 211. We either didn’t choose the right characters from each string, or the right operations to perform on those characters, or both. Unfortunately, there is no good theory about how to define h. The best we can do is try various definitions, by trial and error, until we find one that is perfect.

2. Implementation.

Design a perfect hash function for the reserved names shown in the previous section. To do that, write a small test class, something like this, and run it with various definitions for the function hash. It calls hash for each reserved name, and writes indexes to standard output.

class Test  
{  
  private static final String [] reserved =  
   { "and",  
     "begin",  
     "define",  
     "do",  
     "else",  
     "end",  
     "if",  
     "not",  
     "or",  
     "return",  
     "then",  
     "while" };  
  
  private static int hash(String name)  
  {  
    //  Your code goes here.  
  }  
  
  public static void main(String [] args)  
  {  
    for (int index = 0; index < reserved.length ; index += 1)  
    {  
      System.out.print("h(\"" + reserved[index] + "\") = ");  
      System.out.print(hash(reserved[index]));  
      System.out.println();  
    }  
  }  
}

When defining hash, you might try adding characters at specific indexes from each name. You might try linear combinations of the characters: that is, multiplying the characters by small constants, then adding or subtracting the results. You might try the operator %. You might also try a mixture of these. Whatever you try, reject any definition of hash that is not perfect: one that returns the same index for two different names.
      Your method hash must work in constant time, without loops or recursions. It must not use if’s or switch’es. It must not call the Java method hashCode, because that uses a loop, and so does not work in O(1) time. It must not return negative integers, because they can’t be array indexes.
      The character at index k in name is obtained by name.charAt(k). Characters in Java Strings are indexed starting from 0, and ending with the length of the string minus 1. For example, the first character from name is returned by name.charAt(0), the second character by name.charAt(1), and the last character by name.charAt(name.length() - 1).
      Don’t worry if there are gaps between the indexes: your hash function need not be minimal. Also, try to keep the returned indexes small: they shouldn’t exceed 2000. For example, I know a perfect hash function for the reserved words in this assignment, whose indexes range from 1177 to 1413. I found it after about ten minutes of trial-and-error search.

In: Computer Science

What are the various ways you can analyze financial statements? Hint: Vertical and common-sized are the...

What are the various ways you can analyze financial statements? Hint: Vertical and common-sized are the same thing. Which method do you believe is used most often internally? Why? Which method do you believe is used most often by external stakeholders? Why? Of the different general types of ratios, liquidity, solvency, profitability, etc., which do you think are the most useful by the various stakeholders? Why?

In: Accounting

When choosing a topic, do you prefer to already know about it, or do you like...

When choosing a topic, do you prefer to already know about it, or do you like to choose topics that you know a little about? Why? What are the pros and cons of each of these choices?

In: Math

A 22- year-old woman presents to the ED with complaints of bladder fullness , incomplete bladder...

A 22- year-old woman presents to the ED with complaints of bladder fullness , incomplete bladder emptying , and severe pain in her right flank. She rates the pain a 9 on a 0-10 numeric pain scale. Patient states she has a history of kidney stones . She also states when she is able to void, it burns and has a foul odor . Vital signs: HR 85 , BP 120/80 , RR 16, SPO2 98% on RA, temp 100.9 (oral). Pt takes the following medications : Hydrochlorothiazide (HCTZ ) 25 mg PO daily , Detrol LA 2 mg PO daily Lab results : CBC : WBC 26 Urinalysis : WBC (too many to count), Bacteria (5+, large), Leukoesterase (+) Positive , Protein (-) negative , Ketones (-) negative.
Assessment? Diagnosis? Evaluation ? Implementation ? Planning?

In: Nursing

how does the diffraction peak width vary with the slith width? how does the number of...

how does the diffraction peak width vary with the slith width?
how does the number of secondary maxima vary with slit width?

In: Physics

Please write in full sentences and atleast 1-2 paragraphs for each please. -Correctly describe Groupthink in...

Please write in full sentences and atleast 1-2 paragraphs for each please.

-Correctly describe Groupthink in detail

-What questions do you now have after considering the event in light of psychological theory of groupthink

-What type of experiment(s) might help address groupthing further? Like how can we better our understanding of this? What experiments can we design to better understand it or explore more?

IMPORTANT If you can please find examples in greys anatomy in Season 2 episode 26 when they cut the LVAD wire.

Give an example of each of these from that scene please

•Insulated groups

•Don’t consider relevant info

•Normative pressure toward consensus

•Self-censorship

•Commitment to decisions

•Strong, opinionated leaders

In: Psychology

Simon Company’s year-end balance sheets follow. At December 31 Current Yr 1 Yr Ago 2 Yrs...

Simon Company’s year-end balance sheets follow.

At December 31 Current Yr 1 Yr Ago 2 Yrs Ago
Assets
Cash $ 31,200 $ 34,800 $ 37,400
Accounts receivable, net 89,400 62,100 57,500
Merchandise inventory 50,220 82,300 50,000
Prepaid expenses 10,260 9,166 3,444
Plant assets, net

358,920

261,634 161,656
Total assets $ 540,000 $ 450,000 $ 310,000
Liabilities and Equity
Accounts payable $ 134,460 $ 75,289 $ 39,692
Long-term notes payable secured by
mortgages on plant assets
101,520 104,535 67,140
Common stock, $10 par value 162,500 162,500 162,500
Retained earnings 141,520 107,676 40,668
Total liabilities and equity $ 540,000 $ 450,000 $ 310,000


The company’s income statements for the Current Year and 1 Year Ago, follow.

For Year Ended December 31 Current Yr 1 Yr Ago
Sales $ 702,000 $ 535,500
Cost of goods sold $ 428,220 $ 348,075
Other operating expenses 217,620 135,482
Interest expense 11,934 12,317
Income tax expense 9,126 8,033
Total costs and expenses 666,900 503,907
Net income $ 35,100 $ 31,593
Earnings per share $ 2.16 $ 1.94


Additional information about the company follows.

Common stock market price, December 31, Current Year $ 32.00
Common stock market price, December 31, 1 Year Ago 30.00
Annual cash dividends per share in Current Year 0.32
Annual cash dividends per share 1 Year Ago 0.16


For both the Current Year and 1 Year Ago, compute the following ratios:

1. Return on common stockholders' equity.
2. Price-earnings ratio on December 31.
2a. Assuming Simon's competitor has a price-earnings ratio of 8, which company has higher market expectations for future growth?
3. Dividend yield.

In: Accounting

Nguyen, Tran and Le are partners sharing profits and losses equally and with capital balances of...

Nguyen, Tran and Le are partners sharing profits and losses equally and with capital balances of $225, $675 and $450 respectively. Before Tran leaves the partnership the assets are revalued. An independent valuer assesses the equipment to be worth $12 less than the carrying amount (book value), and property $147 more than the carrying amount.

a) Prepare the journal entries to record the revaluation of property and equipment.

b) Prepare the journal entries to record the revaluation of property and equipment if the partnership agreement specifies profits and losses are allocated on the basis of the capital balances.

c) Prepare the journal entries to record the retirement of Tran (after revaluation and profits and losses are allocated on the basis of capital balances as in (b) above) if she is allowed to take $842.50 in cash (record to the nearest cent)

In: Accounting

Sales, Production, Direct Materials Purchases, and Direct Labor Cost Budgets The budget director of Royal Furniture...

  1. Sales, Production, Direct Materials Purchases, and Direct Labor Cost Budgets

    The budget director of Royal Furniture Company requests estimates of sales, production, and other operating data from the various administrative units every month. Selected information concerning sales and production for February is summarized as follows:

    a. Estimated sales of King and Prince chairs for February by sales territory:

    Northern Domestic:
        King 610 units at $780 per unit
        Prince 750 units at $550 per unit
    Southern Domestic:
        King 340 units at $780 per unit
        Prince 440 units at $550 per unit
    International:
        King 360 units at $850 per unit
        Prince 290 units at $600 per unit

    b. Estimated inventories at February 1:

    Direct materials:
        Fabric 420 sq. yds.
        Wood 580 linear ft.
        Filler 250 cu. ft.
        Springs 660 units
    Finished products:
        King 90 units
        Prince 25 units

    c. Desired inventories at February 28:

    Direct materials:
        Fabric 390 sq. yds.
        Wood 650 linear ft.
        Filler 300 cu. ft.
        Springs 540 units
    Finished products:
        King 80 units
        Prince 35 units

    d. Direct materials used in production:

    In manufacture of King:
        Fabric 6.0 sq. yds. per unit of product
        Wood 38 linear ft. per unit of product
        Filler 4.2 cu. ft. per unit of product
        Springs 16 units per unit of product
    In manufacture of Prince:
        Fabric 4.0 sq. yds. per unit of product
        Wood 26 linear ft. per unit of product
        Filler 3.4 cu. ft. per unit of product
        Springs 12 units per unit of product

    e. Anticipated purchase price for direct materials:

    Fabric $12.00 per sq. yd.
    Wood 7.00 per linear ft.
    Filler $3.00 per cu. ft.
    Springs 4.50 per unit

    f. Direct labor requirements:

    King:
        Framing Department 1.2 hrs. at $12 per hr.
        Cutting Department 0.5 hr. at $14 per hr.
        Upholstery Department 0.8 hr. at $15 per hr.
    Prince:
        Framing Department 1.0 hr. at $12 per hr.
        Cutting Department 0.4 hr. at $14 per hr.
        Upholstery Department 0.6 hr. at $15 per hr.

    Required:

    1. Prepare a sales budget for February.

    Royal Furniture Company
    Sales Budget
    For the Month Ending February 28
    Product and Area Unit Sales
    Volume
    Unit Selling
    Price
    Total Sales
    King:
    Northern Domestic
    Southern Domestic
    International
    Total
    Prince:
    Northern Domestic
    Southern Domestic
    International
    Total
    Total revenue from sales

    2. Prepare a production budget for February. For those boxes in which you must enter subtracted or negative numbers use a minus sign.

    Royal Furniture Company
    Production Budget
    For the Month Ending February 28
    Units
    King Prince

    3. Prepare a direct materials purchases budget for February. For those boxes in which you must enter subtracted or negative numbers use a minus sign.

    Royal Furniture Company
    Direct Materials Purchases Budget
    For the Month Ending February 28
    Direct Materials
    Fabric
    (sq. yds.)
    Wood
    (linear ft.)
    Filler
    (cu. ft.)
    Springs
    (units)
    Total
    Required units for production:
    King
    Prince
    Desired inventory, February 28
    Total
    Estimated inventory, February 1
    Total units to be purchased
    Unit price
    Total direct materials to be purchased

    4. Prepare a direct labor cost budget for February.

    Royal Furniture Company
    Direct Labor Cost Budget
    For the Month Ending February 28
    Framing
    Department
    Cutting
    Department
    Upholstery
    Department
    Total
    Hours required for production:
    King
    Prince
    Total
    Hourly rate
    Total direct labor cost

Check My Work

In: Accounting

A JavaFX question a method called generate2Num(Pane, pane){}; A botton "botton1" that botton.setOnAction(e-> {}); calling generate2Num...

A JavaFX question

a method called generate2Num(Pane, pane){};

A botton "botton1" that botton.setOnAction(e-> {}); calling generate2Num method and show the numbers on Scene.

Every time the user clicks botton1, the updated number will show on the Scene.

I just wanna know how can I update my data by click the button.

Please show the code , thank you

In: Computer Science

Shelly's Boutiques and Crafts had revenue of $5,700,000 this year on sales of 575,000 units. Variable...

Shelly's Boutiques and Crafts had revenue of $5,700,000 this year on sales of 575,000 units. Variable costs were 35% and fixed costs totaled $3,150,000. Although the first five years were relatively profitable, increases in competition have led to a negative trend in profitability that has led them to the point where they have to make some changes to stay afloat. The company is evaluating two options to stay afloat.

Option 1:Purchase machinery to automate their operations. This machinery costs $625,000, but will decrease variable costs by 9%.

Option 2:Outsource the production of one of their main components that requires a substantial amount of machinery and skilled labor. This will reduce fixed costs by $425,000, but increases variable costs from their current 35% of sales to 40% of sales.

c.) Calculate the operating leverage before applying any of the options: What is the contribution margin in Total? What is the operating income in total? What is the operating leverage factor?

In: Accounting

The School District of Philadelphia wants to encourage teachers to fill out an “end-of-year” survey designed...

The School District of Philadelphia wants to encourage teachers to fill out an “end-of-year” survey designed to elicit their feedback about various issues affecting schools. The survey is one of the primary channels through which the school district learns about what is happening in schools across the city, and increasing engagement is a key policy priority for the city. The School District has already created the survey and plans to send out the survey in an email to its 8,062 teachers. The District is willing to manipulate the messaging content in the email that will be sent out and/or provide rewards and incentives for survey completion. (They have up to $3,000 to spend.) Using your knowledge of behavioral economics, what would you suggest they do to maximize survey response rates? Be as specific as possible and justify your choices.  

In: Economics

Explain how globalization process can alleviate poverty form the stand point of Aid?

Explain how globalization process can alleviate poverty form the stand point of Aid?

In: Economics

A multinational firm wants to estimate the average number of hours in a month that their...

A multinational firm wants to estimate the average number of hours in a month that their employees spend on social media while on the job. A random sample of 83 employees showed that they spent an average of 21.5 hours per month on social media, with a standard deviation of 2.5. Construct and interpret a 95% confidence interval for the population mean hours spent on social media per month.

In: Math

Write a program to sort the student’s names (ascending order), calculate students’ average test scores and...

Write a program to sort the student’s names (ascending order), calculate students’ average test scores and letter grades (Use the 10 point grading scale). In addition, count the number of students receiving a particular letter grade. You may assume the following input file data :


Johnson 85 83 77 91 76

Aniston 80 90 95 93 48

Cooper 78 81 11 90 48

Gupta 92 83 30 69 87

Muhammed 23 45 96 38 59

Clark 60 85 45 39 67

Patel 77 31 52 74 83

Abara 93 94 89 77 97

Abebe 79 85 28 93 82

Abioye 85 72 49 75 63

  1. (40%) Use four arrays: a one-dimensional array to store the students’ names, a (parallel) two dimensional array to store the test scores, a one-dimensional array to store the student’s average test scores and a one-dimensional array to store the student’s letter grades.

  2. (60%) Your program must contain at least the following functions :

    1. A function to read and store data into two arrays,

    2. A function to calculate the average test score and letter grade,

    3. A function to sort all the arrays by student name, and

    4. A function to output all the results (i.e. sorted list of students and their corresponding grades)  

    5. Have your program also output the count of the number of students receiving a particular letter grade.  

NOTE : No non-constant global variables are to be used. You can name the arrays and functions anything you like. You can use the operator >= to sort the strings.

In C++

In: Computer Science