Hexo
0%

Posted on Edited on In

Lab 9: Tree Maps vs. Hash Maps

In this lab, you’ll create BSTMap, a BST-based implementation of the Map61B interface, which represents a basic map. Then, you’ll create MyHashMap, another implementation of the Map61B interface, which instead represents a Hash Map rather than a Tree Map. This lab is pretty long, so it’s unlikely you’ll finish in the allotted time. Don’t worry, though, the autograder is friendly, and you shouldn’t stress about completing every last part, though doing so is great midterm practice.

1: BSTMap

The skeleton provides a BSTMap that implements the Map61B interface using a BST (Binary Search Tree) as its core data structure in a file named BSTMap.java. We provide instance variables, a constructor, and a clear method. Your goal is to implement get, put, and size. Other methods such as remove, keySet, and iterator are optional for this lab, and by default should throw an UnsupportedOperationException unless you choose to implement them.

For get and put, you may find it useful to use the putHelper and getHelper helper methods we’ve provided you in the skeleton. We recommend that you work on methods in the order they appear int he file.

Note that the BSTMap class is declared such that the generic keys extend Comparable, so you should use the compareTo method found in the Comparable interface to compare keys.

1
2
3
4
5
6
7
public static void main(String[] args) {
        BSTMap<String, Integer> bstmap = new BSTMap<>();
        bstmap.put("hello", 5);
        bstmap.put("cat", 10);
        bstmap.put("fish", 22);
        bstmap.put("zebra", 90);
}

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package lab9;

import java.util.Iterator;
import java.util.Set;

/**
 * Implementation of interface Map61B with BST as core data structure.
 *
 * @author Macon
 */
public class BSTMap<K extends Comparable<K>, V> implements Map61B<K, V> {

    private class Node {
        /* (K, V) pair stored in this Node. */
        private K key;
        private V value;

        /* Children of this Node. */
        private Node left;
        private Node right;

        private Node(K k, V v) {
            key = k;
            value = v;
        }
    }

    private Node root;  /* Root node of the tree. */
    private int size; /* The number of key-value pairs in the tree */

    /* Creates an empty BSTMap. */
    public BSTMap() {
        this.clear();
    }

    /* Removes all of the mappings from this map. */
    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    /** Returns the value mapped to by KEY in the subtree rooted in P.
     *  or null if this map contains no mapping for the key.
     */
    private V getHelper(K key, Node p) {
        if (key ==  null) throw new IllegalArgumentException("the argument of get() is null!");
        if (p == null) return null;
        int cmp = key.compareTo(p.key);
        if (cmp < 0) return getHelper(key, p.left);
        if (cmp > 0) return getHelper(key, p.right);
        return p.value;
    }

    /** Returns the value to which the specified key is mapped, or null if this
     *  map contains no mapping for the key.
     */
    @Override
    public V get(K key) {
        return getHelper(key, root);
    }

    /** Returns a BSTMap rooted in p with (KEY, VALUE) added as a key-value mapping.
      * Or if p is null, it returns a one node BSTMap containing (KEY, VALUE).
     */
    private Node putHelper(K key, V value, Node p) {
        if (p == null) {
            size++;
            return new Node(key, value);
        }
        int cmp = key.compareTo(p.key);
        if (cmp < 0) {
            p.left = putHelper(key, value, p.left);
        } else if (cmp > 0) {
            p.right = putHelper(key, value, p.right);
        } else {
            p.value = value;
        }
        return p;
    }

    /** Inserts the key KEY
     *  If it is already present, updates value to be VALUE.
     */
    @Override
    public void put(K key, V value) {
        root = putHelper(key, value, root);
    }

    /* Returns the number of key-value mappings in this map. */
    @Override
    public int size() {
        return size;
    }

    //////////////// EVERYTHING BELOW THIS LINE IS OPTIONAL ////////////////

    /* Returns a Set view of the keys contained in this map. */
    @Override
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

    /** Removes KEY from the tree if present
     *  returns VALUE removed,
     *  null on failed removal.
     */
    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    /** Removes the key-value entry for the specified key only if it is
     *  currently mapped to the specified value.  Returns the VALUE removed,
     *  null on failed removal.
     **/
    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<K> iterator() {
        throw new UnsupportedOperationException();
    }
}

2: MyHashMap

The skeleton provides a MyHashMap that implements the Map61B interface in a file named MyHashMap.java. Your implementation is required to implement get, put, and size. Other methods such as remove, keySet, and iterator are optional for this lab, and by default should throw an UnsupportedOperationException unless you choose to implement them. We’ve provided instance variables for you.

We provide the following constructors:

1
2
public MyHashMap();
public MyHashMap(int initialSize);

We also provide the clear method and a private hash method that computes the hash function of a key.

Unlike lecture (where each bucket was represented as a naked recursive linked list), each bucket in this lab is implemented as an ArrayMap, similar to what we developed in lecture 13. Because our bucket class is so powerful, your get and put methods will be very short (our get method is only 2 lines, and our put method isn’t many more).

While using such a sophisticated bucket class seems like cheating, it’s not. Delegating work to a helper class is a very important way to manage complexity, and there’s really no reason that the MyHashMap class should be doing things like manually scanning through buckets – that’s the bucket’s job!

Start by implementing get, put, and size with no resizing. After you’ve made figured these out, modify put so that it resizes. You should resize the array of buckets anytime the load factor exceeds MAX_LF, and you should resize multiplicatively (e.g. doubling the number of buckets) rather than arithmetically (e.g. adding 100 new buckets).

You can test your implementation using the TestMyHashMap class in the lab9tester package.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
package lab9;

import java.util.Iterator;
import java.util.Set;

/**
 *  A hash table-backed Map implementation. Provides amortized constant time
 *  access to elements via get(), remove(), and put() in the best case.
 *
 *  @author Macon
 */
public class MyHashMap<K, V> implements Map61B<K, V> {

    private static final int DEFAULT_SIZE = 16;
    private static final double MAX_LF = 0.75;

    private ArrayMap<K, V>[] buckets;
    private int size;

    private int loadFactor() {
        return size / buckets.length;
    }

    public MyHashMap() {
        buckets = new ArrayMap[DEFAULT_SIZE];
        this.clear();
    }

    public MyHashMap(int capacity) {
        buckets = new ArrayMap[capacity];
        this.clear();
    }
    /* Removes all of the mappings from this map. */
    @Override
    public void clear() {
        this.size = 0;
        for (int i = 0; i < this.buckets.length; i += 1) {
            this.buckets[i] = new ArrayMap<>();
        }
    }

    /** Computes the hash function of the given key. Consists of
     *  computing the hashcode, followed by modding by the number of buckets.
     *  To handle negative numbers properly, uses floorMod instead of %.
     */
    private int hash(K key) {
        if (key == null) {
            return 0;
        }

        int numBuckets = buckets.length;
        return Math.floorMod(key.hashCode(), numBuckets);
    }

    /* Returns the value to which the specified key is mapped, or null if this
     * map contains no mapping for the key.
     */
    @Override
    public V get(K key) {
        if (key == null) throw new IllegalArgumentException("the key is null!");
        int i = hash(key);
        return buckets[i].get(key);
    }

    /* Associates the specified value with the specified key in this map. */
    @Override
    public void put(K key, V value) {
        if (key == null) throw new IllegalArgumentException("first argument to put is null");
        if (loadFactor() > MAX_LF) {
            resize(2 * buckets.length);
        }
        int i = hash(key);
        if (!buckets[i].containsKey(key)) size++;
        buckets[i].put(key, value);
    }

    private void resize(int capacity) {
        MyHashMap<K, V> mhm = new MyHashMap<>(capacity);
        for (int i = 0; i < buckets.length; i++) {
            for (K key : buckets[i].keySet()) {
                mhm.put(key, buckets[i].get(key));
            }
        }
        this.size = mhm.size;
        this.buckets = mhm.buckets;
    }
    /* Returns the number of key-value mappings in this map. */
    @Override
    public int size() {
        return size;
    }

    //////////////// EVERYTHING BELOW THIS LINE IS OPTIONAL ////////////////

    /* Returns a Set view of the keys contained in this map. */
    @Override
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

    /* Removes the mapping for the specified key from this map if exists.
     * Not required for this lab. If you don't implement this, throw an
     * UnsupportedOperationException. */
    @Override
    public V remove(K key) {
        throw new UnsupportedOperationException();
    }

    /* Removes the entry for the specified key only if it is currently mapped to
     * the specified value. Not required for this lab. If you don't implement this,
     * throw an UnsupportedOperationException.*/
    @Override
    public V remove(K key, V value) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<K> iterator() {
        throw new UnsupportedOperationException();
    }
}

Posted on Edited on In

1 Warmup (Spring 2015 MT2: 1c)

Draw the External Chaining Hash Set that results if we insert 5. As part of this insertion, you should also resize from 4 buckets to 8 (in other words, the implementer of this data structure seems to be resizing when the load factor reaches 1.5). Assume that were using the default hashCode for integers, which simply returns the integer itself.

2 Hashtable Runtimes (Fall 2016 MT2: Q3)

Consider a hash table that uses external chaining and also keeps track of the number of keys that it contains. It stores each key at most once; adding a key a second
time has no effect. It takes the steps necessary to ensure that the number of keys is always less than or equal to twice the number of buckets (i.e., that the load factor is ≤ 2). Assume that its hash function and comparison of keys take constant time. All bounds should be a function of N, the number of elements in the table.

  1. Give Θ() bounds on the worst-case times of adding an element to the table when the load factor is 1 and when it is exactly 2 before the addition.
    Bound for load factor 1: Θ(N). Worse case they are all in the same bucket.
    Bound for load factor 2: Θ(N). Assuming that resize doesn’t do an duplicate check. If the resize is implemented such that there is a duplicate check (e.g. resize just calls put), it could be Θ(N2).

Posted on Edited on In

1 WQU and Path Compression

Assume we have eight sets, represented by integers 1 through 8, that start off a completely disjoint sets. Draw the WQU Tree after the series of union() and find()
operations with path compression. Write down the result of find() operations. Break ties by choosing the smaller integer to be the root.

Read more »

Posted on Edited on In

Intuition

For the following recursive functions, give the worst case and best case running time in the appropriate O(·), Ω(·), or Θ(·) notation.
1.1 Give the running time in terms of N.

1
2
3
4
5
6
7
8
public void andslam(int N) {
    if (N > 0) {
        for (int i = 0; i < N; i += 1) {
            System.out.println("datboi.jpg");
        }
        andslam(N / 2);
    }
}

The worst case and best case is all $\Theta(n)$

1.2 Give the running time for andwelcome(arr, 0, N) where N is the length of the input array arr.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void andwelcome(int[] arr, int low, int high) {
    System.out.print("[ ");
    for (int i = low; i < high; i += 1) {
        System.out.print("loyal ");
    }
    System.out.println("]");
    if (high - low > 0) {
        double coin = Math.random();
        if (coin > 0.5) {
            andwelcome(arr, low, low + (high - low) / 2);
        } else {
            andwelcome(arr, low, low + (high - low) / 2);
            andwelcome(arr, low + (high - low) / 2, high);
        }
    }
 }

1.3 Give the running time in terms of N.

1
2
3
4
5
6
1 public int tothe(int N) {
2 if (N <= 1) {
3 return N;
4 }
5 return tothe(N - 1) + tothe(N - 1);
6 }

1.4 Give the running time in terms of N.

1
2
3
4
5
6
7
8
1 public static void spacejam(int N) {
2 if (N <= 1) {
3 return;
4 }
5 for (int i = 0; i < N; i += 1) {
6 spacejam(N - 1);
7 }
8 }

Posted on Edited on In

1 It Begins (Spring 2017, MT2)

For each code block below, fill in the blank(s) so that the function has the desired runtime. Do not use any commas. If the answer is impossible, just write “impossible” in the blank.

1
2
3
4
5
6
7
8
9
public static void f1(int N) { //Desired Runtime: Θ(N)
    for (int i = 1; i < N; i++) {System.out.println("hi");}
}
public static void f2(int N) { //Desired Runtime: Θ(logN)
    for (int i = 1; i < N; i *= 2) {System.out.println("hi");}
}
public static void f3(int N) { //Desired Runtime: Θ(1)
    for (int i = 1; i < N; i += N) {System.out.println("hi");}
}
Read more »

Posted on Edited on In

Asymptotic Notation

1.1 Order the following big-O runtimes from smallest to largest

$O(log n), O(1), O(n^n), O(n^3), O(nlogn), O(n), O(n!), O(2^n), O(n^2logn)$

$O(1) < O(logn) < <O(n)<O(nlogn) <O(n^2logn)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

1.2 Are the statements in the right column true or false? If false, correct the asymptotic notation (Ω(·), Θ(·), O(·)). Be sure to give the tightest bound. Ω(·) is the opposite of O(·), i.e. f(n) ∈ Ω(g(n)) ⇐⇒ g(n) ∈ O(f(n)).

Read more »

Posted on Edited on In

Linked Lists

Q1: Deep Linked List Length

A linked list that contains one or more linked lists as elements is called a deep linked list. Write a function deep_len that takes in a (possibly deep) linked list and returns the deep length of that linked list. The deep length of a linked list is the total number of non-link elements in the list, as well as the total number of elements contained in all contained lists. See the function’s doctests for examples of the deep length of linked lists.

Hint: Use isinstance to check if something is an instance of an object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def deep_len(lnk):
    """ Returns the deep length of a possibly deep linked list.

    >>> deep_len(Link(1, Link(2, Link(3))))
    3
    >>> deep_len(Link(Link(1, Link(2)), Link(3, Link(4))))
    4
    >>> levels = Link(Link(Link(1, Link(2)), \
            Link(3)), Link(Link(4), Link(5)))
    >>> print(levels)
    <<<1 2> 3> <4> 5>
    >>> deep_len(levels)
    5
    """
    "*** YOUR CODE HERE ***"
    if lnk is Link.empty:
        return 0
    elif not isinstance(lnk, Link):
        return 1
    else:
        return deep_len(lnk.first) + deep_len(lnk.rest)

Posted on Edited on In

OOP

Question 4

Write make_max_finder, which takes in no arguments but returns a function which takes in a list. The function it returns should return the maximum value it’s been called on so far, including the current list and any previous list. You can assume that any list this function takes in will be nonempty and contain only non-negative values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def make_max_finder():
    """
    >>> m = make_max_finder()
    >>> m([5, 6, 7])
    7
    >>> m([1, 2, 3])
    7
    >>> m([9])
    9
    >>> m2 = make_max_finder()
    >>> m2([1])
    1
    """
    maximum = 0
    def max_finder(lst):
        nonlocal maximum
        if max(lst) > maximum:
            maximum = max(lst)
        return maximum
    return max_finder
Read more »

Posted on Edited on In

Order of growth

Questions

What is the order of growth for the following functions?

1
2
3
4
5
def sum_of_factorial(n):
    if n == 0:
        return 1
    else:
        return factorial(n) + sum_of_factorial(n - 1)
Read more »

Posted on Edited on In

Check-Off

Q1: A-Okay

Sign up for checkoffs in your lab if you’d like to get credit for this week’s checkoff.
What happens in the following code? Make sure you can explain why each line works or breaks.

1
2
3
4
5
6
7
8
9
10
11
12
>>> class A:
...    y = 1
...    def __init__(self, y):
...        self.y = y
...    def f(self, x):
...        self.y += x
...  
>>> a = A(0) # Ok or not okay?
>>> a.f(6)   # Ok or not okay?
>>> a.f(A, 9) # Ok or not okay?
>>> A.f(a, 4) # Ok or not okay?
>>> A.f(A, 4) # Ok or not okay?
Read more »