CS 201 - 10/23/14 Advising sign-up is this week (October 20-24) and advising is next week (October 27-31). -------------------------- Midterm Exam next Tuesday 10/28/14 during lecture covering linked lists, dynamic arrays algorithms of stacks, queues, in-order lists ------------------------- From Last Time: Run Time of Algorithms Big-Oh Notation From the Wiess Data Strcture Book Big-Oh: T(N) is O(F(N)) if there are positive constants c and N0 such that T(N) <= cF(N) when N >= N0 T(N) : The run time of an agorithm on data set of N elements F(N) : A mathimatical formula on variable N N0 : Some base number of elements If the run time of the algorithm is determined to be: T(N) = 8N^3 + 15N^2 - 4N + 8 The "Order-of" the Run-Time of the "Big-Oh" of the Run-Time is would be expressed as: T(N) = O(N^3) Since 8N^3 + 15N^2 - 4N + 8 < 50N^3 In practice, we determine the most significant term and remove any constants from the term to make this "modified term" the Big-Oh formula value ----------------------------- Set Data Structure an unordered collection of data Operations: add, remove, isMemberOf union, intersection, difference Most often set items are unique, but sometimes we may allow/want duplicate items. When a set can contain duplicate items, it is called a "multi-set" ------------------- When choosing an implementation, we want the "best" one possible. One criteria for "best" is speed of execution. For speed of execution, one mantra is to "make the common case fast" We need to know the run-time of algorithms to determine whether the common operations are "fast". ---------------------- Hash Tables - a super fast storage structure for sets - inserts, deletes, look-up can occur in O(1) time - unfortunately, hash tables requires HUGE amounts of memory.