CSC 325 – Algorithms & Advanced Data Structures – Fall 2009

• Policy Statement
• Using command redirection operators in Windows
• Homework 1
• Randomized BST Demo
• Homework 2
• A Level-Order Printer for Homework 2
• Recursive Longest Common Subsequence
• Homework 3
• Midterm, Friday Oct 30
  Chapters 1-3, 4.1, 6-7, 8.1-3, 9.1-2, 10.4, 11.1-4, 13 (just the basic ideas of sections 3 and 4), 15.2-4; also randomized BSTs
• Homework 4
• Homework 5, due Tuesday Dec 1 at 9am
• Homework 6 will be posted on Tuesday Dec 1

Data structures:

• AA tree
• AVL tree
• Binomial heap
• Fibonacci heap
• Hash table
• Pairing heap
• Randomized binary search tree
• Red-black tree (and the simpler left-leaning variant)
• Splay tree
• Treap

Java generics:

• Generics (from The Java Tutorials)
• Generics Tutorial (PDF)

Java classes and interfaces:

BigInteger (in java.math)

Arbitrary-precision integers.

Collections

Provides a number of useful methods on collections, including addAll, binarySearch, copy, replaceAll, sort, and swap. The Arrays class provides many of the same methods for arrays, as well as copyOf and copyOfRange.

Deque

The interface for deques (or "double-ended queues"), which subsume both stacks and queues. ArrayDeque is generally the best implementation.

Formatter

Provides formatted output to files (using printf) and strings (using String.format), though other options are available.

List

The interface for lists (ordered sequences). ArrayList is generally the best implementation, though LinkedList may be preferable if you need to add or delete elements in the middle of the list.

Map

The interface for maps (that associate keys with values). The most useful implementations are HashMap, which uses a hash table, LinkedHashMap, which adds a doubly-linked list to ensure a consistent iteration ordering, and TreeMap, which uses a red-black tree and provides iteration in sorted order.

Matcher (in java.util.regex)

A regular-expression based pattern-matching engine. Compiled regular expressions are stored as Pattern objects.

Math

Provides mathematical functions as well as the constants E and PI.

PriorityQueue

A priority queue implementation based on a min-heap.

Random

Random-number generators.

Scanner

Provides formatted input from files and strings. String.split is also very useful.

Set

The interface for sets (that store a collection of elements without duplicates). The most useful general implementations are HashSet, LinkedHashSet, and TreeSet. For enums, EnumSet is very efficient both in space and time as it is based on an underlying bit vector representation.

String

Provides many useful methods for Strings, including ones for extraction, conversion, matching, formatting, and interning.

Wrappers

The following "wrapper" classes for each of the primitive types provides many useful methods: Boolean, Byte, Character, Double, Float, Integer, Long, and Short.