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.