Java Software Structures for AP® Computer Science AB, 1st Edition ©2006

Lewis, Chase, Sudol

Correlated to: AP Computer Science AB Topic Outline

Note: Only the sublevels of each topic are listed with sections.

I. Object Oriented Program Design

A. Program Design
1. Read and understand a problem description, purpose, and goals. Specify the purpose and goals for a problem 1.7, 2.5, Program Assignments throughout, Definitions of every data structure and example throughout
2. Apply data abstraction and encapsulation 2.2, 2.4, 2.5, 2.6
3. Read and understand class specifications and relationships among the classes. (is-a, has-a relationships) Decompose a problem into classes; define relationships and responsibilities of those classes 2.5, 2.6, 2.7, 2.8, 2.9, 2.10, 2.12, 2.13, 2.14, program assignments throughout
4. Understand and implement a given class hierarchy 2.1, 2.2, 2.13, 2.14, 2.15
5. Identify reusable components from existing code using classes and class libraries 2.3, 2.11, 2.13
B. Class Design
1. Design and implement a class. Design and implement a set of interacting classes 2.5, 3.3, Each data structure contains an example of how that structure would be used in a larger scenario involving many interacting classes
2. Design an interface 3.1, 3.2, Interfaces are addressed in every chapter that introduces a new data structure
3. Choose appropriate data representation and algorithms. Choose appropriate advanced data structures and algorithms Each data structure chapter discusses the differences between implementations based upon different data representation (See 8.4, 8.5, 8.6 for example)
4. Apply functional decomposition 3.4, every data structure implementation
5. Extend a given class using inheritance 2.12, 2.13, 2.14, 9.7

II. Program Implementation

A. Implementation techniques
1. Methodology (object oriented development, top down development, encapsulation and information hiding, procedural abstraction) 1.3, 1.7, 2.1, 2.2, 2.6, 2.10
2. Programming constructs (Primative types vs. objects, declaration of constants, variables, classes, interfaces, methods, parameters) Appendix A (Basic concept review)
3. Console output Appendix A, 2.2
4. Control (Methods, sequential, conditional, iteration, recursion) Appendix A, 2.4, 6.1, 6.2, 6.3
C. Java library classes included in A and AB AP Java Subset Appendix B, 3.1, 10.6, 12.5

III. Program Analysis

A. Testing
1. Test classes and libraries in isolation 1.2, Introduction of each data structure
2. Identify boundary cases and generate appropriate test data 1.2, Various programming problems
3. Perform integration testing 1.2, Use of each data structure in another program, various programming problems
B. Debugging
1. Categoize Errors 1.2
2. Identify and Correct Errors 1.2
3. Techniques: use a debugger, add extra output statements, hand trace code Various programming problems
C. Understand and modify existing code Various programming problems, Case Study supplement
D. Extend existing code using inheritance 2.12, 9.7, Case Study Supplement
E. Understand Error Handling (understanding runtime exceptions, throw runtime exceptions) 2.15, 3.2, Introduction of exceptions for each data structure
F. Reason about programs (pre and post conditions, assertions, invariants) Addressed throughout book with method comments in every code example
G. Analysis of Algorithms (informal comparison of running times, exact calculations of statement execution counts, big-Oh notation, Worst-case and average-case time and space analysis 1.6, 3.5, 4.5, 5.5, 6.4, 7.1, 7.2, 8.7, 9.8, 10.6, 12.3
H. Numerical representations and limits (representations of numbers in different bases, limitations of finite representations) Appendix A

IV. Standard Data Structures

A. Simple Data Types Appendix A
B. Classes 2.5, Appendix A
C. One Dimensional Arrays Appendix A
D. Two Dimensional Arrays 6.3
E. Linked Lists 4.1, 4.2, 4.3, 4.4
F. Stacks 8.1, 8.2, 8.3, 8.4, 8.5, 8.6, 8.7
G. Queues 9.1, 9.2, 9.3, 9.4, 9.5, 9.6, 9.7, 9.8
H. Trees Chapters 11 and 12
I. Heaps Case Study Assignment
J. Priority Queues 9.7
K. Sets 3.2, 3.3, 3.4, 3.5, 4.4, 4.5
L. Maps Chapter 5

V. Standard Algorithms

A. Operations on A and AB level data structures Chapters 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
B. Searching (Sequential, binary, hashing) 7.1, 5.4
C. Sorting (Selection, Insertion, Mergesort, Quicksort, Heapsort) 7.2, 12.3

VI. Computing in Context

A. Major Hardware Components (primary and secondary memory, processors, peripherals) Assume to be covered in AP CS A course
B. System software (Language translators/compilers, virtual machines, operating systems) Assume to be covered in AP CS A course
C. Types of systems (single user, networks) Assume to be covered in AP CS A course
D. Responsible use of computer systems (Reliability, privacy, legal issues and intellectual property, social and ethical ramifications of computer use) 1.1, 1.2, 1.7

Please Note: this textbook is meant as a second year course for the AP® Computer Science AB topics. While a few of the A topics are mentioned briefly, the AB topics are covered in entirety where listed.

AP® is a trademark registered and/or owned by the College Board, which was not involved in the production of, and does not endorse, this site.