*** SequentialSearchST.java Code ***

package edu.princeton.cs.algs4; import java.util.Queue; public class SequentialSearchST { private int n; // number of key-value pairs private Node first; // the linked list of key-value pairs // a helper linked list data type private class Node { private Key key; private Value val; private Node next; public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } } public SequentialSearchST() { } public int size() { return n; } public boolean isEmpty() { return size() == 0; } public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; } public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) return x.val; } return null; } public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; } for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) { x.val = val; return; } } first = new Node(key, val, first); n++; } public void delete(Key key) { if (key == null) throw new IllegalArgumentException("argument to delete() is null"); first = delete(first, key); } // delete key in linked list beginning at Node x // warning: function call stack too large if table is large private Node delete(Node x, Key key) { if (x == null) return null; if (key.equals(x.key)) { n--; return x.next; } x.next = delete(x.next, key); return x; } public Iterable keys() { Queue queue = new Queue(); for (Node x = first; x != null; x = x.next) queue.enqueue(x.key); return queue; } public static void main(String[] args) { SequentialSearchST st = new SequentialSearchST(); for (int i = 0; !StdIn.isEmpty(); i++) { String key = StdIn.readString(); st.put(key, i); } for (String s : st.keys()) System.out.println(s + " " + st.get(s)); } }

*** BinarySearchST.java Code ***

package edu.princeton.cs.algs4; import java.util.NoSuchElementException; import java.util.Queue; public class BinarySearchST, Value> { private static final int INIT_CAPACITY = 2; private Key[] keys; private Value[] vals; private int n = 0; public BinarySearchST() { this(INIT_CAPACITY); } public BinarySearchST(int capacity) { keys = (Key[]) new Comparable[capacity]; vals = (Value[]) new Object[capacity]; } // resize the underlying arrays private void resize(int capacity) { assert capacity >= n; Key[] tempk = (Key[]) new Comparable[capacity]; Value[] tempv = (Value[]) new Object[capacity]; for (int i = 0; i  0) lo = mid + 1; else return mid; } return lo; } public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; } int i = rank(key); // key is already in table if (i  i; j--) { keys[j] = keys[j-1]; vals[j] = vals[j-1]; } keys[i] = key; vals[i] = val; n++; assert check(); } public void delete(Key key) { if (key == null) throw new IllegalArgumentException("argument to delete() is null"); if (isEmpty()) return; // compute rank int i = rank(key); // key not in table if (i == n || keys[i].compareTo(key) != 0) { return; } for (int j = i; j  0 && n == keys.length/4) resize(keys.length/2); assert check(); } public void deleteMin() { if (isEmpty()) throw new NoSuchElementException("Symbol table underflow error"); delete(min()); } public void deleteMax() { if (isEmpty()) throw new NoSuchElementException("Symbol table underflow error"); delete(max()); } public Key min() { if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table"); return keys[0]; } public Key max() { if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table"); return keys[n-1]; } public Key select(int k) { if (k = size()) { throw new IllegalArgumentException("called select() with invalid argument: " + k); } return keys[k]; } public Key floor(Key key) { if (key == null) throw new IllegalArgumentException("argument to floor() is null"); int i = rank(key); if (i  0) return 0; if (contains(hi)) return rank(hi) - rank(lo) + 1; else return rank(hi) - rank(lo); } public Iterable keys() { return keys(min(), max()); } public Iterable keys(Key lo, Key hi) { if (lo == null) throw new IllegalArgumentException("first argument to keys() is null"); if (hi == null) throw new IllegalArgumentException("second argument to keys() is null"); Queue queue = new Queue(); if (lo.compareTo(hi) > 0) return queue; for (int i = rank(lo); i  st = new BinarySearchST(); for (int i = 0; !StdIn.isEmpty(); i++) { String key = StdIn.readString(); st.put(key, i); } for (String s : st.keys()) StdOut.println(s + " " + st.get(s)); } }

In this assignment I want you to study the performance of both sequential search and binary search as a function of the amount of duplication in the data set. You will do this by writing a simple Java program to measure total search time on a Symbol Table of constant size 1000000, for a variety of "amounts of duplication". We can generate a set of 1000000 Integers with varying amounts of duplication by filling it with random numbers drawn from a limited range. For example, if we generate 100000 numbers randomly chosen between 0 and 1000, then each number appears an average of 1000 times. Here are the steps that you should take for both sequential search and binary search. For each of the following values of range: 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000, 50000) Generate a list of one million integers from 0 to range - Put these numbers into a symbol table - Search for each of the numbers Measure both the time it takes to insert the numbers into the symbol table and the time it takes to search for them Compute the times, and record them and the range When done, generate a graph of insert time and search time versus the ratio of range to the total data set size (1000000). Do this for both sequential search and binary search. You should start by modifying the author's SequentialSearchST, and BinarySearchST. I only had to make modifications to the main method In this assignment I want you to study the performance of both sequential search and binary search as a function of the amount of duplication in the data set. You will do this by writing a simple Java program to measure total search time on a Symbol Table of constant size 1000000, for a variety of "amounts of duplication". We can generate a set of 1000000 Integers with varying amounts of duplication by filling it with random numbers drawn from a limited range. For example, if we generate 100000 numbers randomly chosen between 0 and 1000, then each number appears an average of 1000 times. Here are the steps that you should take for both sequential search and binary search. For each of the following values of range: 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000, 50000) Generate a list of one million integers from 0 to range - Put these numbers into a symbol table - Search for each of the numbers Measure both the time it takes to insert the numbers into the symbol table and the time it takes to search for them Compute the times, and record them and the range When done, generate a graph of insert time and search time versus the ratio of range to the total data set size (1000000). Do this for both sequential search and binary search. You should start by modifying the author's SequentialSearchST, and BinarySearchST. I only had to make modifications to the main method