CSC301.01 2015F, Class 08: Roles of Data Structures and Abstract Data Types =========================================================================== _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 . 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 `` 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