Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Abstract data types.
• Data structures.
• The Dictionary ADT.

Preliminaries

Admin

• New partners for in-class work. (Sam will figure a not-very interesting way to assign partners.)
• I think I've invited all of you to a #CSC301 channel on http://grinnell-cs.slack.com. Feel free to use that to ask questions and discuss class issues.
• Warning: It is possible that the next two weeks of class will vary a bit from the indicated plan. I'm still experimenting with how best to approach some of this material.
• Question: How comfortable are you with tree traversal strategies?
  • Depth-first vs. breadth-first
  • For depth-first: Preorder vs. Inorder vs. Postorder

Upcoming Work

• For Wednesday:
  • Read Skiena 3.1-3.3
  • Part 1: Experimental Analysis
    • Look up the randomized nth-largest divide-and-conquer algorithm. (We may talk about it in class today.)
    • Implement it in C.
    • Write unit tests using assert.
    • Write a program that does lots of repeated tests to evaluate it's running time.
  • Part 2: Proof
    • Find bounds for each of the following using the master theorem.
      • a. T(n) <= 3T(n/3) + O(n^2).
      • b. T(n) <= 3T(n/3) + O(n).
      • c. T(n) <= 3T(n/3) + O(1).
      • d. T(n) <= 3T(n/5) + O(n^2).
      • e. T(n) <= 3T(n/5) + O(n).
      • f. T(n) <= 3T(n/5) + O(1).
      • g. T(n) <= 9T(n/3) + O(n^2).
      • h. T(n) <= 9T(n/3) + O(n).
      • i. T(n) <= 9T(n/3) + O(1).
      • j. T(n) <= T(2n/3) + O(n^2).
      • k. T(n) <= T(2n/3) + O(n).
      • l. T(n) <= T(2n/3) + O(1).
    • Prove the bounds of a-c using induction.

Extra Credit

Academic

• CS Table, Tuesday, Hacking Cars
• CS Extras, Wednesday, Jonathan Wellons '04 from Google
• Lunch with Wellons Wednesday in one of the PDRs (central)
• Lunch with Wellons Thursday in CS Commons
• Convo Thursday at 11 am in JRC 101: Mike Latham

Peer

• Soccer, Wednesday, Women at 4pm and Men at 6pm
• EE: Smith show next week (min of 15 minutes, or go to the reception)

Questions

For part 1, what should we use to look at runtimes?

You should use some time function in C. For example, clock seems pretty cool. If you'd rather instrument your program to count key operations (e.g., comparisons, that would also be okay).

    static long comparisons = 0;

    int compare(int x, int y)
    {
      ++comparisons;
      if (x < y) 
        return -1;
      else if (x == y)
        return 0;
      else
        return 1;
   } // compare

Where can we find an algorithm for determining the kth largest value in an array?

quickselect seems like a pretty good one.

What is the master theorem?

See p. 137 of Skiena.

Abstract data types

Questions for your group:

• What is an ADT?
• Why do we use ADTs?
• What steps do you use in designing an ADT?

What is an ADT?

• "It's like a Stack"
• "A data type built from primitive data types" (Sam says no)
• "It's like an interface - It's a list of methods that you want implemented, but not an implementation"
• A way to organize information in which we think about the organization of that information through the methods that are provided (plus some guiding principles)
• A stack is a collection of values that provides push, pop, top, emptyp.
• A stack is a LIFO collection

Why do we use ADTs?

• You can just use them without worrying about underlying implementation - Find the one that works best for your problem.
• Lets you swap implementations
• Don't need to worry about the underlying semantics of the implementation; just the semantics of the interface. - Makes program analysis easier.

What steps do you use in designing an ADT?

• "PUM!"
• How do you Use the ADT
• What Methods do you need - parameters, return values, preconditions, postconditions?
• Philosophy - What are the underlying principles that guide ^

Data structures

Questions for your group:

• What is a data structure?
• Why do we use data structures?
• What steps do you use in designing or building a data structure?
• What are relationships between ADTs and Data Structures?

What is a data structure?

• Concrete implementations of ADTs.
• We might implement a stack as a linked list with the top of the stack at the front of the list.
• We might implement a stack as an array with the top of the stack at the end of the array.

Why do we use data structures?

• Organizing data affects the behavior of our program.
• Sensible organizations can significantly change the running time.

What steps do you use in designing or building a data structure?

• Use an array or pointers?
• What are benefits of each of the two basic mechanisms?
• Some advantages of Arrays
  • Constant time access to individual elements (more or less)
  • Locality of data decreases the cost of accessing elements when you are iterating (or otherwise accessing nearby elements)
  • Constant amount of memory - No problems with malloc and free!
  • Less overhead.
• Some advantages of Pointer-based structures
  • Helpful when you don't know how many elements you're going to have, or if the different elements may have different sizes.
  • Easier to insert and delete and arbitrary points - arrays often require you to shift elements around
  • Easier to rearrange in other ways, too
• What if we want the advantages of arrays but don't know how many elements we have?
  • Skipped

What are relationships between ADTs and Data Structures?

• Data structures implement ADTs

The Dictionary ADT

_If you haven't seen dictionaries, think of them as generalized hash tables.

Questions for your group:

• What is the primary philosophy of the Dictionary ADT?
  • A collection of <Key,Value> pairs accessible by key.
  • Alternately: A collection of values accessible by key.
• What are some cases in which we would want to use a dictionary?
  • Lots of database applications
• What are the primary methods you would expect a Dictionary to provide?
  • Value get(Key k)
  • void remove(Key k)
  • void add(Key k, Value v) - Add a new key/value pair
  • void set(Key k, Value v) - Change a key/value pair
  • boolean empty()
  • Iterator keys()
  • Iterator values()
  • Iterator> contents()
  • Others suggested in our book (forthcoming)
• What mechanisms/approaches do you know for implementing dictionaries?
  • Hash table
  • Unsorted linked list of pairs
  • Linked list of pairs sorted by Key
  • Pair of arrays or array of pairs, sorted by key
  • Pair of arrays or array of pairs, unsorted
  • Skip lists - A funky randomized data structure that only Sam teaches
  • A heap - Not optimized for this kind of access, but hey, whatever.
  • Binary search tree of Key/Value pairs
• For next class: Think about how you might decide which of these to use
  • Note: A prerequisite to such decisions is understanding more about each, an so we will spend time on each