Data Structures and Algorithms

Asymptotic Complexity

f(n) is  O(g(n)) iff there are constants c and n0 such that for all n > n0, |f(n)| < c |g(n)| .

f(n) ~ g(n) iff the limit as n gets big of |f(n)| / |g(n| is 1.

Application Program Interface (API)

1 Basic Search

• Implementation: SequentialSearch<Item>.
• Implementation: BinarySearch<Item>.

2 Lists

• Interface: List<Item>.
• Percursor: AbstractList<Item>.
• Implementation: LinkedList<Item>.
• Interface: TwoWayList<Item>.
• Implementation: ArrayList<Item>.
• Implementation: TwoWayLinkedList<Item>.
• Implementation: Sequence<Item>.
• Implementation: MoveToFrontSequence<Item>.

2.1 Bags

• Interface: Bag<Item>.
• Percursor: AbstractBag<Item>.
• Implementation: LinkedBag<Item>.
• Implementation: ArrayBag<Item>.

2.2 Queues

• Interface: Queue<Item>.
• Percursor: AbstractQueue<Item>.
• Implementation: LinkedQueue<Item>.
• Implementation: ArrayQueue<Item>.

2.3 Stacks

• Interface: Stack<Item>.
• Percursor: AbstractStack<Item>.
• Implementation: LinkedStack<Item>.
• Implementation: ArrayStack<Item>.

2.4 Deques

• Interface: Deque<Item>.
• Percursor: AbstractDeque<Item>.
• Implementation: ArrayDeque<Item>.
• Implementation: LinkedDeque<Item>.

3 Sorting

• Interface: Sort<Item>.
• Percursor: AbstractSort<Item>.

3.1 Comparison Sorts

• Implementation: SelectionSort<Item>.
• Implementation: InsertionSort<Item>.
• Implementation: MergeSort<Item>.
• Implementation: QuickSort<Item>.
• Implementation: ThreeWayQuickSort<Item>.
• Implementation: HeapSort<Item>.

3.2 Counting Sort

• Implementation:BooleanSort.
• Implementation:CountingSort<Item>.

3.3 String Sorts

• Percursor: AbstractStringSort.
• Implementation:LSDRadixSort.
• Implementation:MSDRadixSort.
• Implementation:ThreeWayQuickSort.
• Implementation:LSDRadixSortWithCutoff.
• Implementation:MSDRadixSortWithCutoff.
• Implementation:ThreeWayQuickSortWithCutoff.

3.4 Priority Queues

• Priority Queue
  • Interface: PriorityQueue<Item>.
  • Implementation: SelectionPriorityQueue<Item>.
  • Implementation: InsertionPriorityQueue<Item>.
  • Percursor: AbstractPriorityQueue<Item>.
  • Implementation: TreeHeapPriorityQueue<Item>.
  • Implementation: ArrayHeapPriorityQueue<Item>.

4 Symbol Tables

• Interface: SymbolTable<Key, Value>.
• Percursor: AbstractSymbolTable<Key, Value>.

4.1 (Unordered) Symbol Tables

• Implementation: LazySequenceSymbolTable<Key, Value>.
• Implementation: SequenceSymbolTable<Key, Value>.

4.1.1 Integer Tables

• Implementation: IntegerTable<Value>.
• Implementation: LinkedListIntegerTable<Value>.
• Implementation: SequenceIntegerTable<Value>.

4.1.2 Hash Tables

• Implementation: ExternalHashTable<Key, Value>.
• Implementation: InternalHashTable<Key, Value>.
• Implementation: SequenceHashTable<Key, Value>.
• Implementation: SequenceExternalHashTable<Key, Value>.
• Implementation: SequenceInternalHashTable<Key, Value>.

4.1.3 Sets

• Interface: Set<Item>.
• Percursor: AbstractSet<Item>.
• Implementation: SequenceSet<Item>.
• Implementation: HashSet<Item>.

4.2 Ordered Symbol Tables

• Interface: OrderedSymbolTable<Key, Value>.
• Percursor: AbstractOrderedSymbolTable<Key, Value>.
• Implementation: MinimalLazyBinarySearchTree<Key, Value>.
• Implementation: LazyBinarySearchTree<Key, Value>.
• Implementation: BinarySearchTree<Key, Value>.
• Implementation: LazyRedBlackSearchTree<Key, Value>.
• Implementation: RedBlackSearchTree<Key, Value>.

4.3 String Symbol Tables

• Interface: StringSymbolTable<Value>.
• Percursor: AbstractStringSymbolTable<Value>.
• Implementation: MinimalTrie<Value>.
• Implementation: Trie<Value>.
• Implementation: MinimalTernarySearchTrie<Value>.
• Implementation: TernarySearchTrie<Value>.

5 Graphs

5.1 Union/Find Data Structures

• Interface: UnionFind<Vertex>.
• Percursor: AbstractUnionFind<Vertex>.
• Implementation: SlowUnionUnionFind<Vertex>.
• Implementation: ListUnionFind<Vertex>.
• Implementation: TreeUnionFind<Vertex>.
• Implementation: WeightedListUnionFind<Vertex>.
• Implementation: WeightedTreeUnionFind<Vertex>.
• Implementation: WeightedTreePathCompressionUnionFind<Vertex>.

6 Miscellaneous Utitity Classes

• Utility: Link<Item>.
• Utility: Pair<Key, Value>.
• Percursor: Ordered<Item>.
• Implementation: NaturalOrder<Item>.
• Implementation: ReverseOrder<Item>.
• Interface: HasKey<Key>.
• Interface: KeyFor<Item, Key>.

Here is the Javadoc for Java these classes. They classes are also available as a jar file: cmp338.jar (last modified: 12/13/12). To import them into Eclipse:

1. Download the jar file onto your computer.
2. Create a new java project, API (say), under Eclipse.
3. Click the API project folder.
4. From the File menu, select Import....
5. In the Import popup, select General ~> Archive File, then click Next.
6. Use the Browse... button, to put the path to the just downloaded cmp338.jar file in the From archive file: field.
7. Move the edufolder under the src folder.