Review — Topics You Should Know from 1115 and 3115

Supplement 1 — Java Basics

You should be familiar with just about everything here with the following exceptions:

• Applets
• Enumerations
• Scope
  • You kow this material, possibly just not by this name
• The Class StringBuilder
  • You may have encountered the StringBuffer class. Both of these are often used as an alternative to the String class.
• Using Scanner to Extract Pieces of a String
  • This section presents somewhat more advanced uses of the Scanner class.
• Use of = and == with Arrays
  • You've probably seen the material in this discussion, though possibly not in as technical a manner
• Arrays and the For-Each Loop
• Multidimensional Arrays
  • As we will see, we're trying to get away from arrays; in general, multidimensional arrays have very specific, specialized applications (matrices, video frame buffers)

Supplement 2 — File Input and Output

• Ignore the section on Binary Files

Appendix A

This chapter covers program documentation — a topic probably discussed in 1115 and 3115. You can ignore the Java Documentation Comments section though you should probably be able to understand them …; we may cover javadoc at some point.

Appendix B

You should have covered all the material in this Appendix, most likely in 3115.

Appendix C

The core concepts of this Appendix — composition and inheritance — are central to class design in general, and data structures in particular. We will be discussing, comparing, and contrasting them on a regular basis.

Prelude — Designing Classes

This chapter covers the basics of designing classes, a process more abstract (and sophisticated) than the basic mechanics of class definitions. The ideas presented lead to the notion of 'programming to the interface, not the class' that we will cover after our introduction to the classic containers.

• Ignore the sections on CRC Cards and Unified Modelling language

Despite my pointing out sections you can skip, as somewhat-experienced Java programmers, there is no reason you shouldn't be able to read all of the above secitions … feel free to come to class with questions. If I think they're relevant to our discussions, I will elaborate on them in class; if not, I will be happy to answer them offline.

Lecture 01 — Preliminaries

Introduction - Organizing Data

This introductory chapter introduces much of the basic terminology and concepts: abstract data type (ADT, data structure, collection as well as the names and fundametnal properties of the classical containers.

• We will be using the same collection names as the Java Collection Framework; this differs occasionally from the text and will be pointed out.
• We will use the term map for the ADT the text calls a dictionary.
• We will not be discussing trees quite the same way as the other containers, like stack or queue. We will also probably not be working with graphs at all. Feel free to ignore the brief discussion of these two ADT's.

Lecture 02 — Introduction to Containers

Chapter 1 — Bags

• first section through The ADT Set

Chapter 5 — Stacks

• first section through Specifications of the ADT Stack ADT Set

Chapter 7 — Queues, Deques, and Priority Queues

• whole chapter is fine

Chapter 10 — Lists

• first section through Specifications for the ADT List

Chapter 20 — Dictionaries

• first section through Specificati:qons for the ADT Dictionary

Container Variations

Chapter 2 — Bag Implementations That Use Arrays

The entire chapter is fair reading.

As discussed above, the variations we presented focused on using pointers to the ends of the containers, in an attempt to avoid the shifting requiring in opening an closing a gap in the underlying array. This made sense for sequences that were restricted to the ends of the containers: stack, FIFO queue and deque. List supports insertion/removal operations within the list proper, and thus do not benefit from end pointers. Similarly, priority queue and all the associatives — including bag — have operations whose semantics are dependent on the values of the elements, rather than their positions; their (primary) challenge is not that sort of insertion/removal but rather how to find particular elements either without explicit sorting, or find an efficient sorting method.

Despite this, Chapter 2 addresses the issue of implementing bag using an array. This is because the book's approach is to start with what they consider a fundamental data structure — the bag — and discuss implementations using a familiar facility — the array. In some respects, the chapter is a good one to read in that it presents many of the reasons for not using a bag that we have discussed; but it also discusses memory management (resizing).

• As discussed above, the variations we presented focused on using pointers to the ends of the containers, in an attempt to avoid the shifting requiring in opening an closing a gap in the underlying array.

Chapter 6 — Stack Implementations

• Whole chapter is fine except, skip A Linked Implementation
  • We will eventually cover linked lists
• The section A Vectoa-Basedr Implementation should be readable; it moves the array implementation into Java's Vector (an equivalent, older version of ArrayList) world. You are not responsible for that yet, though it's not that different then our use of ArrayArray.

Chapter 8 — Queue, Deque, and Priority Queue Implementations

• Skip A Linked Implementation of a Queue, Circular Linked Implementations of a Queue, A Doubly Linked Implementation of a Deque, and Possible Implementations of a Priority Queue
• The section on the array implementation of a queue discusses the implementation discussed in class of having one unused element in the queue to distinguish between the empty and full conditions.