• Continue lab partners.
• Food! (Plus food-like substance.)

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Review: Thinking about data structures.
• Association lists.
• Techniques for improving the implementation.
• Binary search trees.

Preliminaries

Admin

• Today we discuss potential implementations of dictionaries.
  Next week, we'll practice with implementation issues.
• Formal description of project still on my to-do list. Sorry.
• Which three-person group would benefit from EE?
• It's Friday. It's time for your weekly PSA.

Upcoming Work

• Homework: Phase 1 of project (Class design, Algorithm design, I/O subsystem) due Tuesday
• No reading for Monday. Today's discussion should provide appropriate preparation.

Extra Credit

Academic

• CS Table Today: ShellShock
• CS Extra next Thursday: Weinmaniacs on Text Recognition in Maps
• CS Table Next Friday: ???
• CS Extra Tuesday the 25th: Summer Opportunities in CS

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo. TONIGHT!
• YGB on Saturday, 7:30 p.m. at Sebring-Lewis.
• Blackout at 10pm in Loose. Fundraiser!
• Copehagen on Nov. 20-23.
• Basketball 2pm Saturday.

Miscellaneous

• VP Student Affairs Candidate Open Sessions
  • Today, 4:15, JRC 209
  • Wednesday, 4:15, JRC 209
  • Friday next, 4:15, JRC 209

Questions

• Do you count phase one in the grade? Yes
• Do you count phase two in the grade? Yes
• Do you count the presentation in the grade? Yes
• Do you count peer evaluations in the grade? Yes (but only that you do them thoughtfully)

Review: Thinking about data structures

• LIA - Layout (memory), Implement Methods, Analayze
• Layouts: Arrays and Links

You have to implement dictionaries in the next two hours. You don't get to use the java.util.* stuff. What do you do?

Associative arrays

• One really big array, we know the size of the key and the size of the value, so each key/value pair is (keysize+valuesize) after the previous one.
• Two really big arrays, one with keys and one with values. ith element of the keys corresponds to the ith element of the values.

• Create a class, KeyValuePair, that holds a key and a value. Make an array of those.

  public class KeyValuePair<K,V>
  {
    K key;
    V value;
  } // KeyValuePair<K,V>
  
  
  public class AssociativeArray<K,V>
    implements Dictionary<K,V>
  {
    // +-------+-------------------------------------------------------
    // | Notes |
    // +-------+
  
  
    /*
      We store key/value pairs in the locations of an array.
      We have some blank spots, all of which congregate at the
        end.
      We know how many spots are useful through the variable size.
     */
  
  
    // +--------+------------------------------------------------------
    // | Fields |
    // +--------+
  
  
    KeyValuePair<K,V>[] pairs;    // Capacity is pairs.length
    int size;     // The number of key/value pairs in the array
  
  
    // +---------+-----------------------------------------------------
    // | Methods |
    // +---------+
  
  
    public V get(K key)
    {
      for (int i = 0; i < size; i++)
        {
          if (k.equals(pairs[i].key))
            return pairs[i].value;
        } // for
      return null;
    } // get(K)
  
  
    public void add(K key, V value)
    {
    } // add(K, V)
  
  
  } // AssociativeArray<K,V>
  

Association lists

• Like associative arrays, but with linked lists.

Techniques for improving the implementation

Can we do better than O(n) for all of the operations? Suppose we want get to be less than O(n), but we're okay with add and remove being O(n)?

Strategy:

• Store the values in sorted order.
• get can now use binary search.

Strategy:

• Use skip lists.

Binary search trees (BST)

Break up the data into parts

    public class Node<K,V>
    {
      K key;
      V value;
      Node<K,V> smaller;    // Things with smaller keys
      Node<K,V> larger;     // Things with larger keys
    }

If we can arrange the tree in advance, we have O(logn) get

How do we keep them balanced? Take 301