• Know why data giving raw measurements of algorithm performance cannot be used to compare algorithms.
• Understand how equations describing the resource consumption patterns of algorithms stay in the same family, even though computers, compilers, and languages may vary.
• See how the dominant term of the running time equation accounts for most of an algorithm's running time for large problem sizes.
• Develop intuition for the meaning of O-notation by exploring patterns in the same data.
• Understand how O-notation is used by computer scientists to refer to the performance properties of algorithms.
• Understand the formal definition of O-notation.
• Use some useful shortcuts for manipulating O-notation.
• Understand about circumstances in which O-notation analysis does not apply.
• Know what to do to find optimal algorithms under these circumstances.

• Design programs using object-oriented design (OOD).
• Understand the difference between top-down design and bottom-up programming.
• Understand the process of stepwise refinement.
• Examine how to refine choices of data structures and algorithms in parallel.
• Understand unit, integration, regression, and acceptance testing.
• Use test drivers and stubs.
• Understand the separate roles of testing and verification.
• Understand the difference between top-down and bottom-up testing.
• Appreciate the value of formatted debugging aids.
• Understand what a test plan is and write test plans.
• Use concepts of good program structuring.
• Discuss some ideas that help produce good documentation.

• Define a subclass by extending a given class.
• Override applet and interface methods to create a customized new drawing applet.
• Develop programs starting with reusable software components.
• Use abstract classes and abstract methods.
• Understand inheritance and overriding in class hierarchies.
• Use type polymorphism to advantage.
• Draw into off-screen image to eliminate flashing.
• Understand the flavor of OOP that relies on heavy use of prefabricated software components.
• Understand the role of standard applet method invocations.

• Understand what pointers are and how they can be used.
• Appreciate the importance of pointers in real-world systems.
• Understand how Java's reference values can represent pointers and links.
• Know how to allocate object memory dynamically and obtain references to it.
• Manipulate reference values in Java to create linked data representations.
• Understand how to interpret the pointer diagrams used in this book.
• Use a notation for picturing linked representations that is helpful when reasoning about them.
• Understand how to represent and manipulate linked lists using Java objects and reference values.
• Develop skill in designing and implementing linked list algorithms.
• Understand and use a set of useful basic linked list operation.
• Understand some possibilities for linked data representations other than simple, one-way linked lists.
• Illustrate how nodes with two links can be linked into representations such as two-way linked lists, circular lists, and trees.

• Think recursively.
• Understand how strategies for recursion involve both base cases and recursion cases.
• Search for different ways of decomposing a problem into subproblems.
• Understand how to use call trees and traces to reason about how recursive programs work.
• Understand infinite recursion.
• Understand the symptoms caused by the occurrence of infinite recursion.
• Understand that some recursive algorithms have exponential running times.
• Understand why it is impractical to use exponential algorithms to solve problems of large size.

• Identify an abstract data type (ADT) from an example.
• Understand how it is possible to replace the underlying representation for an abstract data type without changing the operations it presents to its external users through its interface.
• Use information hiding features of Java to hide the implementation details of an abstract data type's operations.
• Change underlying data representations implementing an ADT without changing any of the code that uses the ADT.
• Use Java interfaces to make plug-compatible replacement (Strings for integers, etc.) work.
• Understand the role of Java interfaces and classes in implementing modular software.
• Understand the general benefits of modularity and information hiding in the design of large software systems.
• Understand the philosophy and terminology in general use concerning modularity and information hiding.

• Linear Data Structures - Stacks and Queues

The students will be able to

• Understand and use the common terminology of stacks and queues.
• Understand how stacks can be used in dealing with recursion and in other applications.

• Understand the view of ADTs as data structures + operations.
• Understand about the abstract operations and interfaces for stack and queue ADTs.
• Understand how stacks can be used to evaluate postfix expressions.
• Understand how to implement stacks in two different but substitutable ways.
• Understand how to separate implementation details form abstract operations in an ADT interface.
• Understand features of sequential and linked representations.
• Understand how queues can be used in simulations and modeling.
• Understand how to implement queues in two different but substitutable ways.
• Understand about print buffers and print spoolers and synchronization problems.

• Understand the advantages and disadvantages of sequential and lined representations of lists.
• Understand one-way, two-way, and circular linked list representations.
• Understand the role of list header nodes.
• Understand that many varieties of list representations are possible.
• Understand how generalized lists differ from simple linear lists.
• Understand how to represent and manipulate generalized lists.
• Understand the difference between shared and copied sublists.
• Understand how the Java String and StringBuffer classes are used to manipulate a string's characters.
• Understand the difference between static and dynamic memory allocation.
• Understand about available space lists and garbage collection.
• Understand how heaps can be used to support dynamic memory allocation.
• Understand fragmentation, coalescing, handles, and heap compaction.

• Understand the terminology of trees and the relationships among nodes in a tree.
• Understand the definition of binary trees, extended binary trees, and complete binary trees.
• Understand how to represent a heap using a contiguous sequential representation.
• Understand how heaps cam serve as efficient representations for priority queues.
• Understand and be apply to apply the four types of traversal orders commonly applied to nodes of binary trees.
• Understand how stacks and queues can be used to perform nonrecursive traversals of linked binary tree representations.
• Understand how to search for a key in a binary search tree.
• Understand what shapes binary search trees must take to yield the best and worst search performance.
• Understand how binary search trees perform in the average case.

• Understand intuitively hashing concepts using simple examples.
• Be familiar with hash functions, collisions, collision resolution policies, open addressing, probe sequences, chaining, and buckets.
• Understand the performance of hash algorithms.
• Understand how the algorithms for hashing with open addressing work.
• Understand the performance formulas characterizing how well hashing works.
• Understand how to design a good hash function.
• Trace the execution of a serial and binary searches.

• Understanding how comparison trees are defined.
• Understand how abstract priority queue sorting.
• Understand how SelectionSort and HeapSort work.
• Know the O-notation for the sorting times for SelectionSort and HeapSort.
• Understand the divide-and-conquer theme, as applied to sorting methods.
• Understand that MergeSort is an O(n log n) sorting method.
• Understand how QuickSort works and that it runs in average time O(n log n) and worst case time O(n²).
• Understand how the InsertionSort and InterchangeSort work and what their efficiencies are.
• Know about the O(n) RadixSort.
• Understand how the ShellSort and BubbleSort work and why the BubbleSort should be avoided in general.
• Measure the performance of several of the sorting methods and be able to know when and when not to use various sorting methods.