Cs520 Advanced Analysis of Algorithms and Complexity

Operations for ADT

• Constructors
• create a new object and return a reference to it
• Access functions
• return information about an object, but do not modify it
• Manipulation procedures
• modify an object, but do not return information
• State of an object
• current values of its data
• Recursive ADT
• if any of its access functions returns the same class as the ADT

ADT Design e.g. Lists

• Every computable function can be computed using Lists as the only data structure!
• IntList cons(int newElement, IntList oldList)
• Precondition: None.
• Postconditions: If x = cons(newElement, oldList) then 1. x refers to a newly created object; 2. x != nil; 3. first(x) = newElement; 4. rest(x) = oldList
• int first(IntList aList) // access function
• Precondition: aList != nil
• IntList rest(IntList aList) // access function
• Precondition: aList != nil
• IntList nil //constant denoting the empty list.

Binary Tree

• A binary tree T is a set of elements, called nodes, that is empty or satisfies:
• 1. There is a distinguished node r called the root
• 2. The remaining nodes are divided into two disjoint subsets, L and R, each of which is a binary tree. L is called the left subtree of T and R is called the right subtree of T.
• There are at most 2d nodes at depth d of a binary tree.
• A binary tree with n nodes has height at least Ceiling[lg(n+1)] – 1.
• A binary tree with height h has at most 2h+1 –1 nodes

Stacks

• A stack is a linear structure in which insertions and deletions are always make at one end, called the top.
• This updating policy is call last in, first out (LIFO)