Advanced Placement Computer Science

Course Overview
Course Policies
Computer Science AP
Computer Science 2 AP
   Syllabus
   Class Schedule
   Assignments
   Study Material
   Grades
Get Software
Useful Resources
Teacher Information
Assignments for Computer Science 2AP

Assignments need to be completed or read by the date listed
  • New extra credit assignment due before the end of the semester (due date will be listed later)
I want to know something... I want to know what the average maximum depth of an ordered binary tree created by assigning 10000 random values to an empty ordered binary tree.  Do not rebalance the tree.  Run this simulation enough times (at least a 1000) to get a good sample.  Find out the maximum depth of the tree for each simulation and then find the average of the 1000 values.   

This is an individual project and worth 10 points.
  • Extra credit assignments due on 4/28/04 are here
  • AP Review Part 3 Worksheet.  This will not be collected.  But the final AP Review Test will cover all that was covered in Parts 1 & 2.  In addition, it will cover chapters 15, 16, 17 & 18.  Note: At least one of these problems will appear on the exam.
    1. Write a non-recursive Node method public void removeEvens():  The executor removes every other Node from the linked list, i.e., the second, fourth, sixth, etc.  (this is based on the Node class from Chapter 15)
    2. Write a recursive Node method private static Node copyList (Node toCopy):  It returns a new linked list identical to the toCopy parameter. (this is based on the Node class from Chapter 15)
    3. Write a generic containsAll method, i.e., coding that it works correctly for any Collection executor and for any Collection parameter. Use the parameter's Iterator to go through its elements one at a time.  (this is based on the Collection class from Chapter 15)
    4. Write an ArrayMap method private int lookUp (Object id):  The executor returns the index of the MapEntry with a matching id.  It returns -1 if there is no match.  (this is based on the ArrayMap class from Chapter 16)
    5. Write the ArrayMap method public Object remove (Object id):  The executor first sees if the key is in the data structure.  If not, nothing happens except that remove returns null.  But if the key is there, the executor replaces that key/value pair by the one at the end of the array, makes the array one MapEntry smaller, and returns the value that corresponded to the key. (this is based on the ArrayMap class from Chapter 16)
    6. Write the recursive TreeNode method public int size() that returns the number of data values in the tree.  (this is based on the TreeNode class from Chapter 17)
    7. Write the recursive TreeNode method public Object putRecursive (Comparable id, Object value) to put the MapEntry in the tree.  Write the two methods it calls as well.  (this is based on the TreeNode class from Chapter 17)
    8. Write an independent method public static void transfer (PriQue one, PriQue two):  It transfers all elements from the first parameter into the second parameter.  Precondition:  Both parameters are non-null.  (this is based on the PriQue class from Chapter 18)
    9. Write the method public void add (Object ob) for HeapPriQue to add a new data value in the heap structure.  Existing values are in itsItem[0]...itsItem[itsSize-1].  (this is based on the HeapPriQue class in Chapter 18)
  • FRQ due on 4/23/04 is here.  Do this on paper individually and have it ready by the START of class.  Answers are here
  • Project 5 - What made Bill Gates famous!
** Some new notes from 4/27/04

Some tips:
  • It's probably easiest to seperate this into 3 classes
    1. A class to store information about the students (the name, the id, and their age)
    2. A class to store information about the courses (name, maximum enrollment, period, teacher... and you really need to have an ArrayList storing the students as well)
    3. A class to actually do the work that has 2 ArrayLists, one to store the students, one to store the courses.  This should also display the menus to the user, select the input, and then do the various tasks you must do.
  • As an example, when you are to create a student you should create an object of the type of the student class you defined, enter all the relevent information into that object, and then add that object into the ArrayList.  Ditto on the courses.
  • Finding a student by id number will require you to go through the ArrayList of students one at a time, cast each element to type of your student class, and check the id number against the one you're looking for.

** End of the new notes from 4/27/04
    When Bill Gates went to high school, there was a computer at his school.  In the early 1970s this was very very unusual.  He, being a person who actually knew how to program it, was called upon to work on the class scheduling software, a duty he eagerly accepted.  For some odd reason when the course schedules came out, somehow Bill Gates was always in the classes with the cutest girls..  Go figure. (yeah, this did happen)
    Now it is your turn!  With luck this project will be your first step toward a life of riches and scheduling malfeasance.  You are to write a program to schedule students for classes. 

    Your program needs to be able to do the following:
    Define a class, you need to be able to have the user enter information about a class, such as name, size, period, and teacher.
    Define a student, you need to be able to have the user enter information about a student such as their name, their age, and their id number
    Assign a student to a class, you need to be able to place a student into a class (ask the user for the student's id number, and then display a list of all classes available, and have the user select the one they want).  Be sure that the program will not allow the user to assign a student to a class that has a period that the student is already enrolled in a class. In addition, if the class has all the students it can handle (there are as many students enrolled in there as are allowed according to the size of the class) then add the student to a queue for a waiting list
    Print a course roster by student name, where the program prints the names of all students to the screen  sorted by the student name
    Print a course roster by student ID number, where the program prints the names of all students to the screen  sorted by the id number
    Allow a student to remove a course where a student can choose to drop a class. Make sure to enroll the first student on the waiting list for the class being dropped assuming there is a waiting list for that class
Your program should have a menu where the user can select any of those options or select to quit the program, and once a task is completed (except for quitting the program) it should return the user to the menu.  You will need to define a class for classes, and one for a student.  You should keep an ArrayList of Students and of Classes.  This need not be a GUI program, and it is up to you to decide what the best way to get input from the user is (JOptionPane or System.in are probably the easiest)
You also have to make sure to handle errors.  You should reprompt the user if they enter in anything that is invalid (especially input that generates exceptions!)

Your program is due on 4/28/04, and is worth 20 points.  This is an individual project.

  • AP Review Part 2 Worksheet.  Due on 4/23/04.  This covers chapters 7, 9, 11, 12, 13 and 14.  It is worth 10 points.
  1. Write a WorkerList method public WorkerList mergeList: The executor creates and returns a new WorkerList object containing all the values in both lists.  Its size is the sum of the two and, if both lists are ascending order, then the list returned also has its values in ascending order (in other words, code on the assumption both are in ascending order).  This is based on the WorkerList class developed in Chapter 7
  2. List five different RuntimeExceptions and state a short example of when they could be thrown.
  3. The addMore method in Listing 11.3 from the book returns null if you try to add a number for which the result is not computable, i.e., when the add method returns null.  Revise it to return the sum of all the numbers up to that point.
  4. Write an independent class method that prints out the digits of a given positive integer in base 8, but in reverse order (e.g., prints "213" for 2 + 1*8 + 3*64).
  5. Write a class method for TextFileOp with two String parameters that are file names:  It reads from one file and prints to a second file each line that is not lexicographically after the preceding line (i.e., each line s2 for which the preceding line s1 does not satisfy s1.compareTo(s2) < 0).  This is based on the TextFileOp class frm Chapter 12
  6. Write an independent class method that returns the longest token in a given String parameter.  Return null if the String has no tokens.  Use StringTokenizer.
  7. Rewrite the insertionSort method to use binary search to find the place where the next value is to be inserted.  Essay:  Is this faster or slower than the coding in Listing 13.2?  Why?
  8. Count the number of comparisons to sort 4 values in the worst case for (a) mergeSort and (b) selectionSort.  Which is more?
  9. Write a NodeList constructor public NodeList (String fileName) to construct a NodeList containing the separate lines in the the file of the given name, in the order they occur in the file.
  10. Rewrite the ListADT size method using a loop instead of recursion.
  • For the FRQ assignment for 4/7/04 or 4/14/04, do the translated FRQ here.  It is due at the end of class and must be done on paper.  It is worth 2 points.
6) Write an application program that reads in a single decimal number from the keyboard that represents the circumference of a circle and prints out the diameter and area of that circle.  Use 3.14159 as the value of pi.
7) Write MathOp methods to calculate the sine and cosine of any number of radians correct to eight decimal places.  Use the formulas cosine(x) = 1 - x2/2 + x4/(2*3*4) - x6/(2*3*4*5*6)... and  sine(x) = x -x3/(2*3) + x5/(2*3*4*5) - x7/(2*3*4*5*6*7)...
8) Write an independent class method named endsWith with two String parameters big and little:  It tells whether big equals someString + little.
9) Write an independent method with a parameter x that returns x itself unless (a) x is larger than 20, in which case it returns 20, or (b) x is smaller than 10, in which case it returns 10.  Do not use any boolean expression; use both Math.max and Math.min.

For you, this assignment is worth 9 points, it covers chapters 1 - 6, and is otherwise the same.  It is due on the same day, and also must be done individually.
  • Do CSAP's project 4.  Same due dates and rules.
  • Chapter 18 Assignments due on 4/1/04 at the start of class
Read the following sections of Chapter 18: 18.1-18.5

Do the following problems: 18.4, 18.8, 18.15, 18.28, 18.35

Worth 7 points

Extra Credit problems (also due 4/1/04): 18.6, 18.16, 18.34, 18.37

Worth 5 points

  • Chapter 17 Assignments due on 3/25/04 at the start of class
Read the following sections of Chapter 17: 17.1-17.6

Do the following problems: 17.2, 17.8, 17.9, 17.14, 17.15, 17.21, 17.24, 17.37

Worth 10 points

Extra Credit problems (also due 3/25/04): 17.16, 17.23, 17.32, 17.36

Worth 5 points

  • Chapter 17 Assignment 1 due on 3/18/04
Do the following problems: 17.2, 17.9, 17.15

Worth 2 extra credit points if done at the start of class on 3/18
  • Case Study Project #1 due on 3/15/04
Alter the project to simulate a more realistic view of a major water body...  include some scummy polution.  Modify the environment class to keep track of a number of possible spots on the grid (use an array or arraylist).  You can arbitrarily assign some locations as polluted in your code.  (later it may be changed so you can load that information from a file, or from the user) 

Modify the fish class to keep track of a number of steps left before they die, and modify the swim methods such that if they swim in any of the polluted spots, they start a countdown whereby they move one step closer to death every turn after they swim through the polluted spot.  When they have no steps remaining, they should never move again, and if possible they should change their appearance so that you know they have left and joined the choir invisible. 

I am leaving the exact changes to make and where you make them up to you. 

This is an individual assignment and it is worth 15 points.  There will be more assignments based on this one, so you MUST do this.
  • Chapter 16 assignments due on 3/5/04
Do problems 16.19, 16.20, 16.22, 16.24*, 16.43*, 16.62** (this is a hard one, give yourself time)  All but the last problem together are worth 5 points, 16.62 is worth another 5 points.  (out of 10)
  • Chapter 15 assignments (no quiz if everyone completes these assignments)
Take your linked list code from the last chapter, and make it implement the Collection class as defined in 15.2.  (You need to modify your own code, not use the book's code later in the chapter)

Create an iterator class for this class and a method to return an iterator class for your linked list.  (defined in 15.6)  (again, you need to have the code work for YOUR class, simply copying 15.7 is not adequate)

These assignments are worth 6 points and are due on 2/26/04
  • Chapter 14 (quiz on 2/18/04)
Concepts you are responsible for:
  • Stacks (the concept and implementions as Arrays, Arraylists and Linked Lists)
  • Queues (the concept and implementions as Arrays, Arraylists and Linked Lists)
  • Linked Lists (the concept, advantages/limitations, implementations)
  • Doubly and circular linked lists (concept, advantages/limitations, implementations)
  • Invariants
Required problems from this chapter (Chapter 14 homework):
14.11, 14.16, 14.24, 14.37, 14.50 (it's ok to use 2 lines), 14.57, 14.60
worth 10 points
  • Assignment 3 - Due on 2/17/04 at the start of class -
Implement a clone of the ArrayList class using a linked list.  The class MUST have the following methods:

a default constructor
void add(Object o) Adds the object to the end of the linked list
void add(int position, Object o) inserts the object into the list at the given position
Object remove() removes the last item from the list and returns that Object
Object remove(int position) deletes the object from the given position in the list, returns the object and moves every other item up in their position
Object get(int position) returns the Object at the given index
void set(int position, Object o) sets the object at the given position to a certain value
int size() returns the size of the "ArrayList"

Throw RuntimeExceptions as needed.  And call this class something other than ArrayList.  Write a driver method to test out the code.  Worth 5 points.

  • Assignment 2 - Due on 2/11/04 at the start of class -
Do problems 14.6 & 14.10.  Worth 2 points of extra credit, but MUST be ready at the START of class.
  • Assignment 1 - Due on 2/9/04 at the start of class -
Implement an ADT for a queue and stack.  Both classes need to include the following methods:

void add(Object o) which adds an object to its proper location into the data structure (at the end for a queue, at the start for a stack)
Object remove() which returns the first item from the ArrayList and removes an object from the data structure
int count() which returns the number of items held within the structure. 
you also need a default constructor

Make sure you throw a RuntimeException if a method is going to operate beyond bounds.  (you try to remove when you have no items in the structure)  Write a driver method to test out the code.  Worth 3 points. 

Queue Solution
Stack Solution

Bonus points (worth 2):
Implement the above ADTs using arrays of Objects as well (with a maximum size defined as 100).  Note:  You need to also throw a RuntimeException if you try to add beyond the maximum size of the array. 
  • Due on 2/3/04 -
Read 13.1-13.6 (THIS IS ALMOST ALL NEW MATERIAL FOR AB COMPUTER SCIENCE)

Do problems 13.3, 13.10, 13.15, 13.16, 13.30, 13.39, 13.40, 13.45, and 13.47 worth 10 points



last updated on 5/20/04
Copyright (C) 2004 Jim Casaburi