CS1ADS: Algorithms and Data Structures
Syllabus
The purpose of this course is to investigate building medium-sized applications.
This means looking in detail at notions of abstraction. In terms of Java
this means constructing packages and appreciating the notion of a software
architecture. As an example of a package, a package of algorithms and data
structures (ADS) will be investigated. Some attention
will also be paid to the Java Collections Framework, Java Generic
Library (JGL), Abstract Window Toolkit (AWT)
and, perhaps, Swing (the part of the Java Foundation Classes
(JFC) dealing with user interface construction).
This will necessitate futher coverage of inheritance and association as
abstraction techniques and also the event and exception handling systems.
The input/output streaming model and its associated object pipelining model
will also be investigated.
In investigating the ADS package, various
data structuring techniques and a number of searching and sorting algorithms
will be covered. The following data structures will be covered in this
course:
- Fundamental data structures and iterators over them:
- Lists (singly-linked and doubly-linked lists)
- Stack
- Queue
- Heap
- Priority Queue
- Hash Tables (open and chained)
- Map (aka Dictionary)
- Binary Tree
- (AVL Tree, if there is time; rationale only done in 1997-8, not covered
1998-9)
- (Red-Black Tree, if there is time; rationale only done in 1997-8, not
covered 1998-9)
- (B-Tree, if there is time, not done in 1997-8, not covered 1998-9)
-
Searching and Sorting:
- Selection Sort
- Bubble Sort
- Insertion Sort (aka Sifting)
- Quicksort
- Merge Sort
- Heap Sort
- Count Sort (aka Bucket Sort)
- Radix Sort (aka Digit Sort)
- Balanced Multiway Merge
- Polyphase Merge
- (Graphs -- but only if there is time, not done in 1997-8, not covered 1998-9:
- Adjacency matrix representation
- Adjacency list representation
- Breadth-first search
- Depth-first search)
ADS is not a production library but is a pedagogical
tool. Packages such as the Java Collections Framework and ObjectStore's
Java Generic Library (JGL) -- a `port' of the C++
Standard Template Library (STL) -- are ones
that are production system tools.
If time permits the ideas of JavaBeans will be introduced also the Java Media
Framework (JMF). This was not done in 1997-8 nor 1998-9.
The processes and tools of programming, and most especially testing
and debugging, will be investigated and analysed.
Russel Winder
Last updated: 2000-01-12