Advanced Placement Computer Science AB

Dual Enrollment with MCCC as CS111 (3 credits)

Course Design:

This is a year long course that meets for 90-minutes every other day. The course includes several individual and paired programming projects assigned for one or two weeks each. The time after the AP exam is devoted to a team project and enrichment activities. The course includes an enrichment unit on graphic manipulation and graphical user interfaces (GUI) which are not required for the AP exam.

Course Objectives:

Text and Supplementary Materials:

Litvin, Maria, and Gary Litvin. Java Methods A&AB: Object-Oriented Programming and Data Structures, AP Edition, Andover, Mass.: Skylight Publishing, 2007
Litvin, Maria, and Roger Frank, Judy Hromcik, Gary Litvin, Dave Wittry. Be Prepared for the AP Computer Science Exam in Java, 3rd Edition, Andover, Mass.: Skylight Publishing, 2007.
The College Board’s GridWorld case study
http://www.skylit.com/javamethods/JM-Appendix-F.pdf.  Java Methods A & AB: Appendix F: Computing in Context: Responsible and Ethical Computer Use.

Current magazine and internet articles discussing ethical and social issues related to computer use.

Course Outline:

Chapter numbers for readings and exercises refer to Java Methods A&AB, AP Edition. GridWorld refers to the College Board’s GridWorld case study narrative.

Unit 1: Introduction to Java (September)

1. Introduction to hardware, software and the Internet
Elements of a computer system. How information is represented in computer memory. A glimpse of binary and hex systems and ACSII/Unicode.

Reading: Chapter 1
Lab: How to read the binary clock, convert your age into binary and hex, write your name in Unicode

2. Software development environment
Getting familiar with the software development process. Compilers and interpreters. JDK tools (javac, java, appletviewer, javadoc). Running a Java program in a command-line environment. Using an IDE. Java classes and source files. A brief introduction to OOP.

Reading: Chapter 2
Lab 1: Compile and run simple programs using command line JDK tools
Lab 2: Compile and run simple GUI applications and an applet

3. First look at objects and classes
Classes and objects. Classes and source files. Case Study: First Steps (A prototype for the Dance Studio program). CRC cards. Library classes and packages. The import statement. Extending library classes. A first look at fields, constructors and methods of a class. Inheritance.

Reading: Chapter 3
Lab 1: Exploring objects: Calling a Foot object methods
Lab 2: Finish the Walker class and write the WalkerTest class
Lab 3: Redefining methods in subclasses, Pacer class
Lab 4: Exploring objects: add Walker and Pacer objects to the group.

4. Algorithms
The concept of an algorithm. Pseudocode and flowcharts. Iterations. Recursion. Working with lists. Case study: Euclid’s GCF Algorithm.

Reading: Chapter 4
Lab: print stars using iteration and recursion

5. Java syntax and style
Syntax and style in a programming language. Comments. Reserved words and programmer-defined names. Statements, braces, blocks, indentation. Syntax errors, run-time errors, logic errors.

Reading: Chapter 5 and Appendix A
Lab: Correcting syntax errors and a logic error of an "adventure game"

6. Data types, variables, and arithmetic
The concepts of a variable and a data type. Declarations of variables. Fields vs. local variables. The primitive data types: int, double and char. Literal and symbolic constants. Initialization of variables. Scope of variables. Arithmetic expressions. Data types in arithmetic expressions. The cast operator. The compound assignment (+=, etc.) and increment and decrement operators
(++, --). Converting numbers and objects into strings.

Reading: Chapter 6
Lab 1: Exercises for Chapter 6
Lab 2: Pie Chart
Lab 3: Rainbow

7. The if-else statement
The if-else statement, Boolean expressions, the boolean data type, true and false values. Relational and logical operators. DeMorgan’s laws. Short-circuit evaluation. Nested if-else and if-else-if. Case Study: Craps. Elements of OO design in Craps. The switch statement. enum data types.

Reading: Chapter 7
Lab 1: From exercises for Chapter 7
Lab 2: The CrapsGame class for Craps: fill in the blanks and test in isolation
Lab 3: Finishing and testing the Craps program

8. Iterative statements
while, for, and do-while loops. break and return in loops.

Reading: Chapter 8
Lab 1: From exercises for Chapter 8
Lab 2: Perfect Numbers

Unit 2: Classes, Class hierarchies, GridWorld (October-November)

1. An introduction to GridWorld (1 day)
Experimenting with the GridWorld GUI. An overview of the classes and objects involved. Role-play exercise.

Reading: GridWorld Part 1
Lab 1: Set up a GridWorld project and run BugRunner.
Lab 2: Simple extensions of the Bug class.

2. Details of defining classes and using objects (4 days)
Public and private fields and methods. Constructors and the new operator. References to objects. Calling methods and accessing fields. Passing parameters to constructors and methods. return statement. Overload methods. Static fields and methods. GridWorld continued.

Reading: Chapter 9; GridWorld Part 2
Lab 1: Snack Bar
Lab 2: GridWorld exercises for Part 2

3. Strings (3 days)
String objects. Literal strings. Immutability. String methods. Converting strings into numbers and numbers into strings. The Character class and its methods.

Reading: Chapter 10
Lab: Lipograms

4. Class hierarchies, abstract classes, and interfaces (5 days)
Class hierarchies. Polymorphism. Abstract classes. Invoking superclass’s constructors and calling superclass’s methods. Case Study: Dance Studio. Interfaces.

Reading: Chapter 11, GridWorld Part 3
Lab 1: Dance Studio
Lab 2: Past free-response questions on class hierarchies and polymorphism
Lab 3: Creating a subclass of Actor, GridWorld Part 3 group activity.

Unit 3: Arrays, ArrayLists, Searching and Sorting (November - December)

1. Arrays (1 day)
One-dimensional arrays. Arrays as objects. Declaring and initializing. Indices. Length. IndexOutOfBoundsException.

Reading: Chapter 12, Sections 12.1-12.3
Lab: Fortune Teller

2. ArrayLists. Array and ArrayList algorithms (4 days)
List interface. ArrayList’s constructors and methods. Traversals and the “for each” loop. Finding the largest and the smallest element. Inserting and removing elements. ArrayLists in GridWorld.

Reading: Chapter 12, Sections 12.4-12.9, GridWorld Part 4
Lab 1: Creating an Index for a Document
Lab 2: Past free-response questions on arrays and ArrayList
Lab 3: GridWorld Part 4 exercises.

3. Two-dimensional arrays (3 days)
Declaring 2D arrays. Indices. Accessing the number of rows and columns. Traversals.

Reading: Chapter 12, Sections 12.10-12.11
Lab 1: Chomp
Lab 2: Past free-response questions on 2D arrays

4. Searching and Sorting (5 days)
Comparing objects. The equals method and the Comparable interface. Sequential and Binary Search. Selection Sort, Insertion Sort, Mergesort, and Quicksort. The java.util.Random class

Reading: Chapter 14
Lab 1: Chapter 13 exercises
Lab 2: Keeping things in order
Lab 3: Benchmarks

Unit 4: Data Structures (January-March)

1. Big-"O" analysis of algorithms (2 days)
The "Big-O" notation. Linear, logarithmic, and quadratic growth. Worst-case and average-case time and space analysis. Review of O(n2) sorts: Selection Sort and Insertion Sort. O(n log n) sorts: Mergesort and Quicksort

Reading: Chapter 18

2. The Java collections framework (5 days)
The Collection and Iterator interfaces. The List interface and the ArrayList and LinkedList classes. The Stack class. The Queue interface. The PriorityQueue class. The Set interface and the TreeSet and HashSet classes. The Map interface and the TreeMap and HashMap classes.

Reading: Chapter 19
Lab: Exercises for Chapter 19
Team programming project: Stock Exchange or Snake

3. Lists and iterators (3 days)
Singly-linked lists. Traversals and iterators. Do-it-yourself linked list. Linked list with a tail. Doubly-linked lists. Circular lists.

Reading: Chapter 20
Lab 1: Implementing a singly-linked list
Lab 2: Teletext

4. Stacks and queues (3 days)
Array and linked list implementations of stack. Review the java.util.Stack class. Applications of stacks. The hardware stack. Review of the java.util.Queue interface. Ring buffer and linked list implementations of queues. Applications of queues.

Reading: Chapter 21
Lab 1: Browsing
Lab 2: Actors World

5. Recursion (3 days)
Examples of recursive methods used for handling nested structures or branching processes. Base case and recursive case. When not to use recursion (e.g., Fibonacci Numbers). Understanding and debugging recursive methods.

Reading: Chapter 22
Lab: Towers of Hanoi
Programming Project: A Game of Hex

6. Binary search trees (5 days)
Binary tree concepts and terminology. Working with AP’s TreeNode objects. Traversals. Binary search trees. Review of the java.util.Set and java.util.Map interfaces and their implementations in the java.util.TreeSet and java.util.TreeMap classes. Case Study: Instant Messanger

Reading: Chapter 23
Lab: Morse Code
Programming Project: Java Messenger

7. Look-up tables and hashing (4 days)
Look-up tables. Hashing. The hashCode method. Resolving collisions by chaining and probing. Review of the java.util.HashSet and java.util.HashMap classes.

Reading: Chapter 24
Lab 1: Cryptogram solver
Lab 2: Search Engine

Unit 5: Review (April)

1. GridWorld grid implementations and review (4 days)
Review of the GridWorld classes, interfaces, and objects and their interactions. Grid implementations.

Reading: GridWorld Parts 1-4; GridWorld Part 5; Be Prepared Chapter 7
Labs: GridWorld Enhancements
Labs: GridWorld implementation

2. Review and practice for the Exam (7 days)

Reading: Be Prepared Chapters 1-6 and 8
Labs: Be Prepared practice exams

Unit 6: Enrichment (Post Exam)

1. Streams and files (5 days)
Text and binary files. Streams vs. random-access files. Java I/O package. The Scanner class. Checked exceptions

Reading: Chapter 14
Lab: Dictionary for Ramblecs

2. Graphics and GUI (7 days)
Computer graphics concepts. The Java Graphics class. GUI components and their events. Layouts. Handling mouse and keyboard events.

Reading: Chapters 15, 16, 17
Lab: Pieces of the Puzzle
Programming Project: Drawing Editor

Topics covered throughout the year:

The course teaches students to recognize the ethical and social implications of computer use.  The topics on responsible use of computers, intellectual property, piracy and its implications, are discussed throughout the year, using current events and published magazine articles as starting point of discussions.

Run-time exceptions are taught throughout the year, as the appropriate material is studied: division by zero and ArithmeticException, arrays and ArrayIndexOutOfBoundsException, uninitialized or null objects and NullPointerException, class-type mismatch of objects and ClassCastException, IllegalArgumentException.