AP Computer Science Syllabus

Resources

Big Java, C. Horstmann, Second Edition, 2006, Wiley. (ISBN 0-471-69703-6)

AP Computer Science Course Description 2007-08

The GridWorld Case Study

Overview

This course is divided into four major academic units. Completion of a unit will include reading the assigned chapters of the text and completing their review and programming exercises, completing at least one large-scale programming project, and taking an exam covering all material in the course to that point (i.e. the exams will be cumulative). The following table summarizes the plan for the year, including correlation to the topic outline included in the course description.

Unit Summary Class Days Textbook Chapters Topic Outline Correlation
1 Basic OOP, Java language features 20 1–7 II.B (except II.B.2.d and II.B.4.e), III.H, IV.A-C General coverage units 1-4
I (except I.A.4 and I.B.5), II.A, II.B.4.e, II.C, III.C, VI
2 Advanced OOP, debugging and testing 30 8–11, 15 I.A.4, I.B.5, II.A, II.B.2.d, III.A-B, III.D-F, IV.E-G
3 Searching, sorting, advanced data structures, algorithm analysis 30 14, 16, 19, 21 III.G, IV.H-L, V
4 Case Study Extension Project 24 none III.C-D
5 AP Test Review

Unit Details

Unit 1

You will accomplish two major goals in this unit. First, you'll thoroughly review the Java programming language. Second, you'll explore the essential features of the object-oriented programming paradigm. During this period of study, you will begin to learn how to read and understand code, and how to think about a problem by decomposing it into small pieces and solving them individually.

We will revisit recursion throughout the year, but during this unit you'll start by visualizing it. We'll use Logo to build fractal art, including trees, ferns, Sierpinski triangles, and Koch curves.

Topics

Java Language Object-Oriented Programming Basic Concepts
  • Variables and data types
  • Primitive data types
  • Objects
  • Control structures
  • Data structures
    • One-dimensional arrays
    • Two-dimensional arrays
  • Strings
  • Objects vs. primitives
  • Object references
  • Encapsulation
  • Data hiding
  • Static vs. instance
  • Physical organization of computers
  • Computer languages and compilers
  • Low-level representation of data
  • Operating systems
  • Heap and stack memory
  • Virtual machines

Projects

Using the supplied GUI framework, you will create a card game complete with graphical display, mouse interaction, and a computerized opponent. The basic classes are supplied. You will be creating new classes using the top-down design methodology to factor your code.

Unit 2

In this unit you will expand your object-oriented knowledge to include the concepts of inheritance, interfaces, and polymorphism. You will also learn about debugging and testing your code, including the use of Java's system of run-time exceptions. Linear data structures will be covered (lists, stacks and queues) in the context of Java's Collections framework.

Topics

Object-Oriented Programming Errors, Debugging and Testing Data Structures
  • Interfaces
  • Polymorphism and run-time binding
  • Inheritance
    • Constructors
    • Fields
    • Methods
  • Casting across object types
  • Abstract classes
  • Types of errors
    • Compile-time
    • Run-time
    • Logic
  • Debugging strategies
  • Testing strategies
  • Linked Lists
  • Stacks
  • Queues

Projects

You will complete two programming projects in this unit, both of which emphasize interfaces and inheritance. One project is a simulation of a hot-air balloon race. The other is a robot which is programmed to solve a maze. Both projects will provide a base balloon or robot class and require you to create subclasses which act in various ways.

During this unit you will also do a research project and presentation on a contemporary topic at the intersection of sociology, politics and computer science. Potential topics are DRM, intellectual property and copyright; hacking; data security, encryption and privacy; information-age patents; and mission-critical software and five-9s reliability.

Unit 3

You will learn about advanced data structures in this unit: trees, heaps, and priority queues. You will also learn about the concept of abstract data types (such as sets and maps) in the context of the Java Collections framework. Algorithms for working with all data types in the course will be explored and analyzed. You will learn about Big-Oh notation and how it is used to predict the performance of algorithms and classify them relative to each other.

Topics

Data Structures Standard Algorithms Algorithm Analysis
  • Trees
  • Heaps
  • Priority Queues
  • Abstract Data Types
    • Sets
    • Maps
  • Java Collections framework
  • Standard operations (insert, traverse, remove) for data stuctures
  • Searching
  • Sorting
  • Time complexity
  • Space complexity
  • Big-Oh notation
  • Limitations of computers
    • NP-Complete problems
    • Undecidable problems

Projects

The project for this unit is a web-crawling search engine. Using the supplied framework to access URLs, you will learn how to parse HTML text and look for links. You will examine strategies for indexing contents of pages and then construct a database of all the pages you crawled. The database can be stored and accessed in multiple ways; we will examine various data structures to determine which are the best to use for our purposes, and look at the impact of different sorting and searching algorithms on the performance of the search engine.

Unit 4

This unit will comprise a large-scale programming project. You will become familiar with the GridWorld case study, its classes and documentation. In the first part of your studies you will complete the case study narrative through chapter 5. In the second part, you will extend the existing system by writing your own classes that significantly enhance the capabilities of the code. Once you have done that, you will conduct a simulation of your own devising that incorporates Genetic Programming, a tree-based evolutionary programming model. Your simulation will evolve a population of agents whose goal is to accomplish a particular task within a set time.

Unit 5

You will spend this time preparing for the AP exam. We will take at least two practice exams and review all the material covered during the year.