CS 240 Enriched

Data Structures and Data Management

1/15/2015

Elvin Yung

Summation Formulae

Arithmetic sequence
Geometric sequence
Harmonic sequence

Techniques for Algorithm Analysis

There are two general strategies:
Use theta bounds throughout the analysis and obtain a theta bound for the complexity of the algorithm.
Prove a big-O upper bound and a matching big-omega lower bound separately to get a theta bound. Sometimes this technique is easier because arguments for O-bounds might use simpler upper bounds, and/or the arguments for omega-bounds may use simpler lower bounds.

AND NOW, ONTO:

Abstract Data Types

An *abstract data type is a collection of data and the operations defined over it.

List

Standard linked list

Stack

A stack is a set of items stacked in order of arrivals.
It implements the following interface:
- push(x) - pushes x on top of the stack.
- pop() - removes the top item from the stack.
- peek() - returns the top item without mutating the stack.
- isEmpty() - returns some indicator of whether the stack is empty.
- size() - returns the size of the stack.
Stack is an example of a LIFO (last in, first out) data structure.

Queue

A queue is an example of a FIFO (first in, first out) data structure.
It implements the following interface:
- front() - returns the item at the front of the queue.
- enqueue(x) - pushes an item to the back of the queue.
- dequeue() - removes the item at the front of the queue.

Dequeue

A dequeue (pronounced deck) is essentially a queue with two ends.
It has the following interface:
- front()
- rear()
- frontEnqueue(x)
- rearEnqueue(x)

Priority Queue

In a priority queue (PQ) instead of ordering objects by insertion order, items are ordered by priority.
For CS240, larger priority values indicate higher priority. (In some other implementations, a priority of 1 or A indicates highest priority.)
It has the following interface:
- insert(priotiy, value) - inserts item with priority.
- deleteMax() - extracts the value with the highest priority.
Using a linked list to naively implement a priority queue, insert runs at Ө(1) and deleteMax linearly searches for the highest priority item and removes it, running at Ө(n).
An array implementation is to use an unsorted array. In this case, insert runs at Ө(1) and deleteMax runs at Ө(n).
Using a sorted array (by insertion), insert at Ө(n) and deleteMax runs at Ө(1).
The choice of which implementation to use is trivial if insertions are performed much more frequently than deletions (or vice versa), but if insertions and deletions are both done very frequently, we need a better implementation that is efficient for both insert and deleteMax.
Using a heap to implement a priority queue, both insert and deleteMax run at Ө(lg n).

Heap

See 2015/01/20.