| 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
|