1) Design a data structure called POLYNOMIAL that stores mathematical polynomial

Question

1) Design a data structure called POLYNOMIAL that stores mathematical polynomials of degree up to m. Explain the pros and cons of your design.

2) Implement a procedure in your favorite computer language that generates 100,000 random integer numbers between 0 and 1000, and stores these numbers to 4 hash tables. The hash tables should have collision resolution by chaining based on (i) the multiplication hashing method with (a) A=0.2 and m=100, (b) A=0.5 and m=100, and (c) A=0.8 and m=100; and (ii) the division hashing method with (d) m=100. Run your procedure 5 times, and calculate the average number of keys per slot (from the 5 runs). Plot 4 histograms with the results (one for each hash table). Post your code, your results, and a deep analysis of your findings?
*Tip: Make sure to seed the random function so the drawn numbers are different each time.

3) Design a (good) hash function to chain integer numbers drawn from a Normal Distribution around a mean value M.
*Tip. A Normal Distribution is characterized by a larger frequency of numbers drawn near the mean, and gradually less frequent numbers drawn as they move away from the mean.

Explanation / Answer

1.

A simplest way of representing polynomials would be to store it as an array (or a list) of it's coefficients. For instance, consider the polynomial 5x^4+3x^2+1,
which can be represented as [5 0 3 0 1]. But this is an inefficent way of representation, because of additional memory usage, as the missing terms should be represented by a zero in it's place. Consider the polynomial (2x^1000 + x^2 + 4), this would require an array of size 1001 to represent it, although there are only few terms.

A more effiecient way of storing in terms of memory will be using a map or a dictionary. Consider the polynomial 2x^1000 + 3x^2 + 4, we can store the following as [1000:2, 2:3, 0:4]

2.

import java.util.ArrayList;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class HashAnalysis {

   public Map<Integer,List<Integer>> hashTableOne;
   public Map<Integer,List<Integer>> hashTableTwo;
   public Map<Integer,List<Integer>> hashTableThree;
   public Map<Integer,List<Integer>> hashTableFour;
  
   public HashAnalysis() {
       hashTableOne = new HashMap<Integer,List<Integer>>();
       hashTableTwo = new HashMap<Integer,List<Integer>>();
       hashTableThree = new HashMap<Integer,List<Integer>>();
       hashTableFour = new HashMap<Integer,List<Integer>>();
       startTest();
       calculateAverageChainLengths();
   }
  
   public void startTest() {
       Random random = new Random();
       for (int i=0; i<100000; i++) {
           int value = random.nextInt(1000);
           fillUpByMultiplicationHash(hashTableOne, 0.2, 100, value);
           fillUpByMultiplicationHash(hashTableTwo, 0.5, 100, value);
           fillUpByMultiplicationHash(hashTableThree, 0.8, 100, value);
           fillUpByDivisionHash(hashTableFour, 100, value);
       }
   }
  
   public void fillUpByMultiplicationHash(Map<Integer,List<Integer>> hashTable, double A, int m, int value) {
       int hashKey = (int) Math.floor(m * (value*A % 1));
       List<Integer> chain = hashTable.get(hashKey);
       if (chain == null) {
           chain = new ArrayList<Integer>();
           hashTable.put(hashKey, chain);
       }
       chain.add(value);
   }
  
   public void fillUpByDivisionHash(Map<Integer,List<Integer>> hashTable, int m, int value) {
       int hashKey = value%m;
       List<Integer> chain = hashTable.get(hashKey);
       if (chain == null) {
           chain = new ArrayList<Integer>();
           hashTable.put(hashKey, chain);
       }
       chain.add(value);
   }
  
   public void calculateAverageChainLengths() {
       double loadFactorOne = getAverageChainLength(hashTableOne, 100);
       double loadFactorTwo = getAverageChainLength(hashTableTwo, 100);
       double loadFactorThree = getAverageChainLength(hashTableThree, 100);
       double loadFactorFour = getAverageChainLength(hashTableFour, 100);
       System.out.println("LoadFactor-1 = " + loadFactorOne + ", LoadFactor-2 = " + loadFactorTwo + ", LoadFactor-3 = "+loadFactorThree+", LoadFactor-4 = "+loadFactorFour);
   }
  
   public double getAverageChainLength(Map<Integer,List<Integer>> hashTable, int m) {
       double loadFactor = 0;
       for (Entry<Integer, List<Integer>> entry : hashTable.entrySet()) {
           if (entry.getValue() != null) {
               loadFactor += entry.getValue().size();
           }
       }
       if (m == 0) {
           return -1;
       }
       return loadFactor/m;  
   }
  
   public static void main(String args[]) {
       for (int i=1; i<=5; i++) {
           System.out.println("Trail - " + i);
           new HashAnalysis();
       }
   }
}

// Please post remaining as seperate questions, I have answered two questions although i am entitled to answer only one as per Chegg's policy

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.