AP Computer Science AB
Syllabus 2008-2009
Course: Math 477
Instructor: Mr. Naccarato
Course Days: A3/B5/D2/E4/F6
Room: A051

Course Objectives
  1. Prepare for the AB Computer Science Advanced Placement test
  2. Understand and alter the GridWorld Case Study
  3. Use data structures that may appear on the Advanced Placement test
  4. Use and evaluate algorithms that appear on the Advanced Placement test
  5. Use the principles of good software design in creation of software applications
Prerequisites
Class Resources
This class is taught in the Computer Science Lab. The lab has 21 computers, enough for each student. The computers run Windows XP and have a copy of Eclipse for completing all assigned projects. In addition, the lab has a projector that can access each computer and collaboration software that allows the instructor to view and remotely control each desktop in the lab.

Text Books and Resources
  1. Litvin, Maria, and Gary Litvin. Java Methods A & AB: Object-Oriented Programming and Data Structures, AP Edition. Andover, MA.: Skylight Publishing, 2006.
  2. The College Board's GridWorld Case Study
  3. AP® Central Computer Science AB Quick Reference Guide
  4. Lab handouts to describe the programming assignments below in more detail
Assignments
Assignments for this class can be broken down into four categories:
  1. Labs: Computer based projects that emphasize the topics covered in each unit. These will be completed in class.
  2. Tests: Assesments to help the student learn what his strengths and weaknesses are on a given topic. These also help the student become more comfortable with AP style questions.
  3. Homework: Practice exercises that reinforce daily topics.
  4. Oral Presentations: Each week we will take 30 or so minutes to listen to and discuss a presentation by a student on a current topic in Computer Science. Part of learning about Computer Science includes learning to take responsibilty for the programs you create and the consequences of their use. Therefore, the topic of each presentation will be the responsible use of computers. Each student will be responsible for 2 to 3 presentations depending on class size.
    The presentation will revolve around an article read online or in print. The responsible use of computers covers such topics as intellectual property rights, privacy concerns, hacking, and the social and ethical ramifications of computer use. Each student will need to have their article approved by me the week before presenting so that all topics are discussed. Grades for this assignment will be based on the quality of presentations. Participation in discussions will be factored as part of class participation. [C9]
  5. An up-to-date list of assignments will be posted on NetClassroom.
Course Outline [C2][C3][C9]

Weeks 1 - 5 [C4][C6][C8][C9]
Topic 1: Programming Review and GridWorld Case Study
    Objectives:
  • Refresh the students knowledge of programming basics (arrays, decisions, loops, etc.)
  • Review the parts of computer systems (hardware, software, networks) and how they interact[C8]
  • Understand and discuss school's acceptable use policy for computers (see Computer Policy section below), how it relates to policies in other organizations, and how it provides a guideline for responsible computer use in general [C9]
  • Develop programs with multiple, interacting classes
  • Introduce the GridWorld program and its classes
  • Learn to extend the GridWorld Classes
    Readings:
  • Litvin Chapters 1-3 [C8], 5, 6, 9-12
    Programming Assignments
  • Fortune Teller: Write a class to display a random fortune from an array.
  • Creating an Index for a Document: Write a series of classes that create an index for a document.
  • Chomp: A game that attempts to force the other player to occupy the upper left square of a rectangular game board.
  • Using GridWorld: Set up the GridWorld code in Eclipse and run the BugRunner.java application
  • CircleBug: Write a class that describes a bug that moves in a circle around a given Rock
  • HordeBug: Write a class that represents a horde of bugs that all move in the same direction.
Weeks 6 - 9 [C4][C5][C6][C7]
Topic 2: Linked Lists and List Iterators
    Objectives
  • Build a Linked List using the ListNode class
  • Use the java.util.LinkedList class
  • Use an Iterator to traverse a LinkedList
  • Continue to extend the GridWorld code
    Readings
  • Litvin Chapter 20
    Programming Assignments
  • Movie Actors Index: Write a program to read a file containing information on various movies and another file containg a list of actors. Display a list of all movies that a given actor appeared in.
  • Teletext: Display a continuously scrolling list of headlines that a user can add to a delete from.
  • CannibalBug: Create a class containing a list to represent a group of bugs. The bugs must feed on other bugs in the group to survive.

 

Weeks 10 - 14 [C4][C5][C6][C7][C8]

Topic 3: Stacks and Queues
    Objectives
  • Understand the push and pop methods of a Stack
  • Understand the enqueu and dequeue methods of a Queue
  • Identify how stacks and queues are used by a computer and its operating system
    Reading
  • Litvin Chapter 21
    Programming Assignments
  • Toy Browser: Use a Stack to implement the Back and Forward buttons of a simple WWW browser.
  • Actors World: Use Queues to implement a program that allows objects to pass messages to one and other.
  • Knight Bug: Implement a bug that moves like a knight on a chess board. The bug should be programmed to complete the Knight's Tour using Stacks for back tracking.
  • Super Knight Bug: Alter the Knight Bug so that it uses the Warnsdorf's heuristic to speed up the finding of a tour.
  • Feeding Bug: Code a bug which will return to a Rock to feed. The Rock should contain a queue to feed bug's one at a time.
Weeks 15 - 17 [C4][C5]
Topic 4: Recursion
    Objectives
  • Re-introduce the priniciples and terminology of recursion
  • Prove recursive algorithms using math induction
  • Design and implement recursive solutions
    Readings
  • Litvin Chapter 22
    Programming Assignments
  • Towers of Hanoi: Complete a program to print a list of moves needed to complete the Towers of Hanoi puzzel.
  • Hex Game: Complete a program to play the game of Hex. Use recursion to determine if a chain exists for a given player.
  • N-Bugs Problem: Use the GridWorld program to solve the classic N-Queens problem.
Weeks 18-20 [C4][C5][C6][C7]
Topic 5: Trees and GridWorld Case Study
    Objectives
  • Understand tree terminology
  • Introduce and use the TreeSet and TreeMap classes
  • Understand the differences between a set and a map
  • Understand when to use a set and when to use a map
  • Understand map terminology, especially key and value
  • Distinguish between trees and binary search trees (BST)
  • Understand the properties of a BST
  • Build a Binary Seach Tree using the TreeNode class
  • Understand the BoundedGrid and UnboundedGrid classes.
    Readings
  • Litvin Chapter 23
  • Part 5 from the GridWorld case study
    Programming Assignments
  • Morse Code: Use TreeMap and TreeNode to create an application that sends and translates Morse Code messages.
  • Messenger: Use TreeMap and TreeSet to create a mini instant messenger application. You will code both the server and user classes.
  • Fighting Bug: Extend the GridWorld case study to include bugs that combat each other using various power ups found in the environment. The bugs will store their power ups in a TreeSet. You will be required to alter the BoundedGrid environment.
Week 21 - 24 [C4][C5][C6][C7]
Topic 6:Lookup Tables and Hashing
    Objectives
  • Understand how a Lookup Table works
  • Implement a Lookup Table
  • Explore the concepts of hashing
  • Understand the use of a hash function and how it creates a hash table
  • Understand what a collision is in a hash table
  • Be able to discuss methods to deal with collisions, specifically chaining and bucket filling
  • Understand the features and use of the HashMap class
  • Understand the features and use of the HashSet class
    Readings
  • Litvin Chapter 24
    Programming Assignments
  • Cryptography Solver: Use a lookup table to encode and decode messages.
  • Search Engine: Use LinkedList, TreeSet and HashMap to create a program which will display what lines a given word appears on in a text file
  • Replicator Bug: Write the code for a bug that will spawn a copy of itself whenever it reaches certain home locations. The home locations should be stored in a HastSet or HashMap.
Weeks 25-26 [C4][C5][C6][C7][C8]
Topic 7: Priority Queues and Heaps
    Objectives
  • Understand the properties of a Priority Queue
  • Distinguish between a Priority Queue and regular Queue
  • Understand and use the PriorityQueue class
  • Understand the properties of a heap
  • Understand the relationship between heaps and binary trees
    Readings
  • Litvin Chapter 25
    Programming Assignments
  • Heapsort: Implement a program that sorts the data in a file alphabetically using a heap and the heapsort algorithm.
  • Feeding Bug: Revist the Feeding Bug lab, but this time the queue at the rock should be a priority queue. The bugs will be queued by a hunger value.
Weeks 27-28 [C5][C9]
Topic 8: Algorithm Analysis
    Objectives
  • Perform temporal and spacial analysis of algorithms using Big-O notation
  • Recognize and understand the common Big-O functions (n, n2, n log(n), etc.)
  • Review the common sorting (Merge, Selection, Insertion, Quick and Heap) and search (Sequential and Binary) algorithms
  • Give the Big-O analysis for common sorting and searching algorithms in their worst, best and average cases both spacially and temporally
  • Recognize the importance of algorithm analysis in providing reliable, secure (in terms of both preventing hacking and protecting user privacy) and robust applications
    Readings
  • Litvin Chapter 18
    Programming Assignments
  • Algorithm Analysis: Run the common sorting algorithms on sets of data. Use the System.currentTimeMillis() function to give a general idea of how long each algorithm takes for each data set.
Week 29 [C5][C6][C9]
Topic 9: Design Patterns
    Objectives
  • Understand the concept of a Design Pattern
  • Describe several well-known patterns: Facade, Singleton, MVC, and others
  • Understand and discuss how these design patterns can enforce responsible computer use by enhancing a software applications reliability and security
    Readings
  • Litvin Chapter 26
Weeks 30-32 [C6][C7]
Topic 10: Exam Preparation
    Objectives
  • Practice with multiple choice questions
  • Practice with free response questions
  • Review the GridWorld case study
    Readings
  • AP® Central Computer Science AB Quick Reference Guide
  • GridWorld Case Study parts 1-5 (review as neccessary)
  • Questions from previous AP® tests
Weeks 33-End
Topic 11:C++ and Unix
    Objectives
  • Understand the basic differences between C++ and Java
  • Write a simple C++ application
  • Write a C++ class
  • Write a C++ application using mulitple classes
  • Learn basic Unix commands for moving around a file system
  • Learn to use the vi text editor
C2 - The course includes all of the topics listed in the "Computer Science AB" columns of the Topic Outline in the AP Computer Science Course Description.
C3 - The course teaches students to design and implement computer-based solutions to problems in a variety of application areas.
C4 - The course teaches students to use and implement commonly used algorithms and data structures.
C5 - The course teaches students to develop and select appropriate algorithms and data structures to solve problems.
C6 - The course teaches students to code fluently in an object-oriented paradigm using the programming language Java. The course teaches students to use standard Java library classes from the AP Java subset delineated in Appendixes A and C of the AP Computer Science Course Description.
C7 - The course teaches students to read and understand a large program consisting of several classes and interacting objects, and enables students to read and understand the current AP Computer Science Case Study posted on AP Central.
C8 - The course teaches students to identify the major hardware and software components of a computer system, their relationship to one another, and the roles of these components within the system.
C9 - The course teaches students to recognize the ethical and social implications of computer use.

* Note 1: Tests will occur at the end of each topic
* Note 2: Class design and implementation are taught throughout the course
* Note 3: The social and ethical ramifications of computer use are discussed throughout the course via presentation assignments (see Assignments section) and class discussions during lectures


Computer Policy [C9]

Salesianum School offers computer resources for the use of the school community.  All users have a responsibility to use those resources and the Internet in an appropriate, lawful and ethical manner. The expectation is that use of the Internet will always be in line with the school’s philosophy, educational goals and moral teachings.  This policy applies to all computers whether they are connected to the school networks or not, and wherever they may be located throughout the school.

Acceptable Uses

Unacceptable Uses

Safety Guidelines

Course Administration
    Class Rules
  1. Respect yourself, your classmates, your teachers, and your school.
  2. Help to create a productive classroom environment.
  3. Attack each problem as if you are going to solve it.

  4. ****If you choose to ignore these expectations, the following will happen:
        1st offense: verbal warning
        2nd offense: written assignment
        3rd offense: after or before school detention
        4th offense: phone call home
        Any further problems will result in a disciplinary referral to the dean of students.
    Classroom Procedures
  1. Be in your seat and ready to start class when the bell rings. Have all required materials ready to use. If you are late you must have a note. Unexcused lateness will result in time after school.
  2. Dispose of all trash, sharpen all pencils, and attend to rest room needs before class.
  3. Eating, drinking and talking out of turn is not permitted.
  4. If you need to leave the room to use the restroom, sign-out when you leave.
  5. You may consult classmates when doing your classwork or homework. However, each person must turn-in his or her own work.
  6. Log out of computers before you leave. Other students will be using them and you would not want them to have access to your files.
    Assignments
  1. All programming assignments should be turned in via Moodle. Accomodations can be made if this cannot be accomplished.  Homework can be handed in on paper or electronically; it's up to you.
  2. All assignments are due by the start of class on the due date.  I will not hold up class so that a student can use the computer.
  3. Any assignment not submitted in class on the due date is late. Late assignments can will be penalized 10% per day. The instructor reserves the right to judge whether circumstances surrounding late assignments warrent extension.
  4. You are responsible for all assignments (test, homework, etc.) if you are absent. Assignments for which you had more than a days notice are due the day you return to school. If you fail to submit assignments on the appropriate day, you are subject to the above deductions.
    Testing Procedures
  1. There will be no talking during quizzes and tests.
  2. Tests will model the AP test and be split into two parts over two days. The first day will consist of multiple choice questions. The second day will consist of free response questions.
  3. Keep your paper in the center of your desk at all times and keep your eyes on your paper.
  4. When finished, turn over your paper; always have additional materials to work on after tests and quizzes.
  5. When absent, you must make-up any missed quizzes or tests on the day you return.

  6. *****Failure to follow the above testing procedures will result in an automatic grade of "zero."
    Grading Policy
  1. Tests: 50%
  2. Programming Projects: 25%
  3. Class Participation: 15%
  4. Homework: 10%
    Academic Integrity
    It is presumed that you will do all work in the course using the highest standards of integrity and honesty, as befits a Salesianum student. Copied assignments, plagarized code, or violations of testing procedures will result in the following sanctions:
  1. A grade of "0" will be given on the assignment.
  2. All students involved in copying assignments or cheating on a test will be penalized.
  3. Your parents will be notified by the instructor.
  4. The Academic Dean will be notified by the instructor.
    *****Receiving a grade of 0 can seriously impact your quarter and final grade, possibly leading to failure for the quarter which would seriously impact your eligibility for participation in extracurricular activities (sports, plays, etc.).
What To Expect From Me
My goal in this course is to provide each student with a rewarding and exciting introduction to Computer Science. I will be available during, after class, and via email to answer any questions you may have. It is my hope this class will inspire you to continue to pursue an education in the field of Computer Science.