High Tech Programming MATHSC 865 - Advanced Data Structures
	Last updated on October 23, 2006.

 

This represents an evolving, loose collection of notes, examples, and discussons related to the topics in the course.

Object Concepts

Classes and Objects

The class defines all the objects of the same type. In fact, in many respects a class is a type. An object is an instantiation of a class. For example, suppose that x, y, and z are strings with the following values: x = "Ann", y = "Bob", and z = "Carol and Dan". Each is an object of the String class, which is part of the java.lang package. In defining the String class the authors of Java included approximately 55 methods such as length(), charAt(int index), and endsWith(String s). The expression x.length() would evaluate to 3; the expression y.charAt(0) would evaluate to 'B', and the expression z.endsWith("an") would return true.

A class may be abstract, in that it specifies that certain methods must exist without providing any implementation code. Objects cannot be instantiated from an abstract class.

Inheritance

A Java class may extend another class. When that happens the new class inherits all the attributes and methods of the parent class.

The Shape examples discussed in class as well as the Simple Draw applet contain the four classes: Shape, myRectangle, myEllipse, and mySquare. Shape is an abstract class, which specifies that every shape will have a bounding box and a color. The bounding box is specified by four ints: the x,y coordinates of the upper left corner and the height and width. The Shape class also specifies that every shape will have the following methods: moveTo(), draw(), area(), and perimeter(). Since the moveTo() method simply changes the coordinates of the upper left corner of the bounding box this method is implemented in the Shape class. The other methods can not be implemented until we know more about the physical shape. The myRectangle and myEllipse class implement the draw(), area(), and perimeter() methods. They inherit the moveTo() method from the Shape class so that code doesn't have to be rewritten. Since a square is a rectangle the mySquare class inherits the draw(), area(), and perimeter() methods from the myRectangle class.

A subclass may also override a method from its parent class. The shape examples do this in the case of the toString() method which they inherit from the Object class. The Shape class itself implements the code for displaying the attributes. The subclasses simply concatanate their name with the string they obtain by invoking their parents toString() method.

Polymorphism

Polymorphism refers to the fact that an object knows what it is and executes the method that is appropriate for itself. The Simple Draw applet is an excellent example of this. The applet code maintains a list of shapes and the paint method simply tells each shape in the list to draw() itself. Each object executes the draw() method specified in its class definition.

Data Structures

The three most fundamental data structures are the Stack, the Queue, and the Priority Queue. From the perspective of an Abstract Data Type, these three data structures are collections of objects which support a method for adding an item to the collection and a method for retrieving an item from the collection.

For a Stack the methods are usually referred to as Push and Pop. The Stack supports a restricted Last In First Out (LIFO) access to its collection of items. We say that push(x) pushes x onto the top of the stack, and that pop() retrieves the item on the top of the stack. A Stack must maintain the invariant property

x = s.pop(s.push(x))

For a Queue the methods are sometimes referred as Enqueue and Dequeue. In the java.util.Queue interface they correspond to Offer and Poll. The Queue supports a restricted First In First Out (FIFO) access to its collection of items. We say that the enqueue(x) appends x to the back of the queue, and that dequeue() retrieves the item at the front of the queue.

For a Priority Queue the methods are usually referred to in the same terms as the corresponding methods for a Queue. However, there is a ordering relation imposed on the items in the Priority Queue. This is often referred to as the priority of the object. The Priority Queue must satisfy the property that if

If x = pq.dequeue() then x <= y for all y in the Priority Queue

Priority Queues can be efficiently implemented using a Heap. Check the preceding link for a thorough description of the heap implementation including a detailed example of the enqueue and dequeue operations.

Design Methodology

The Unified Modeling Language, UML, was developed to help designers get a handle on different aspects of the design process.

Use cases are scenarios describing how the user of the software will interact with the software. These are particularly important during the initial specifications of the software.

Class Diagrams are used to specify a class. They include the name, the attributes, and the behavior. Class diagrams also indicate relationships between classes, particularly inheritance and composition. Class diagrams can be used effectively from three different perspectives: conceptual, specification, and implementation. In the conceptual phase, the classes are used to communicate about the domain knowledge of the user. In the specification phase, the classes reflect responsibilities. In the implementation phase the classes should match up with those of the software.

In the design phase, Class-Responsibility-Collaboration cards, CRC cards, are particularly useful in extablishing the "contractual" relationships between different objects. This is a good technique for developing the interface specifications as well as delineating what classes are necessary.

Automata Theory and Formal Languages

Formal Languages is a succinct introduction to formal languages. It's in a pdf format.

Regular Expression Specification is a short introduction to regular expressions. Regular expressions are the most common and compact way of describing the typical Type 3 languages.

XML, the eXtensible Markup Language, is used to specify a markup language for a particular subject domain. The specification resides in the DTD, the Data Type Definition, which is usually stored in a file on the web so that it can be referred to by various files which use the markup language.

The file personal.xml is a simple example of an XML file which satisfies the simple Data Type Definition in personal.dtd