Advanced Placement Computer Science II Curriculum (2002-2003)

Walter Ivie, Westwood High School

 

Textbook:  Fundamentals of Program Design and DataStructures with C++ by Lambert & Naps

Reference: Exposure C++ by Leon Schram

 

                                                                                               Suggested                      AP Computer Science

          Unit                                                                              Timeline         Dates            AB Subset

 

Fall Semester:

 

1.      Class Procedures and Prologue/C++ Review                                  2 blocks            8/20–  8/23  Do I remember what I learned

                                                                                                                                                                        in AP Computer Science A?        

2.      Data Abstraction, Object Oriented Programs (OOP) (Ch. 2)       5 blocks            8/26–  9 / 9   Can I design and write

Object Oriented Programs? Do I understand how templates are used?

3.      Algorithm Analysis of sorts and searches, Big-Oh (Ch. 1)           4 blocks            9/10–  9/19  Do I understand:

invariants, Big Oh analysis and notation, worst case, average case and time-space analysis.

Can I explain and trace N2 sorts?

4.      Software Engineering (OOP Design, CRC Cards)  (Ch. 3)           1 blocks            9/20–  9/23  Can I identify appropriate Classes,

Responsibilities and Collaborators for a Object Oriented Design?

5.      Linked Lists and Pointers (Ch. 4)                                                     8 blocks            9/24–10/16  Do I understand how to:

Use pointers to create a linked list?  

                                                                                                                                                                        Allocate and de-allocate memory?

Insert into a linked list?

Delete from a linked list?

Traverse a linked list?

6.      Stacks and Queues (Ch. 5)                                                                  4 blocks          10/17–10/28  Can I implement a program using a

Stack class and a Queue class?

Can  I explain how the class methods are written when implemented with  a linked list or an array? Do I understand the difference between a queue and a priority queue?

7.      Recursion (Ch. 6)                                                                                  4 blocks          10/29–11 / 7  Can I analyze problems and develop

solutions using recursive functions?

 

8.      Binary trees, General Trees and Graphs (Ch. 7)                        11 blocks          11 / 8–12/12  Do I understand how to implement

binary trees, binary search trees, general trees and graphs using linked lists or arrays? Can I use these objects in other classes?

Spring Semester:

 

9.       Advanced Sorting Algorithms (Ch. 8)                                             6 blocks          1 / 7  – 1 /23   Can I explain how the more efficient

sorting methods (n log n) achieve their efficiency?  Can I implement and use the merge sort, heap sort, shell sort, radix sort and quick sort methods?

10.  Advanced Search Algorithms (Ch. 9)                                              9 blocks          1 /24 – 2 /19  Can I explain how the density

dependent search methods achieve their efficiency ( Hashing)?  Can I explain and use the alternative techniques for collision resolution (linear, quadratic, rehashing)?  Can I implement a indexed sequential search?  Can I explain B-trees and Trie index methods?

11.  Marine Biology Case Study & AP Exam Prep                           20 blocks          2 /20 – 4 /28  Can I modify the Marine Biology

case study classes as required to simulate a more enhanced environment?

12.  Graphics and GUI Programming                                                    9 blocks           4 /29 – 5 /22  Can I use the Carnegie Mellon

University graphics package and the Microsoft Foundation classes to implement a graphical user interface?