compsciap Mr. Farrell
Millburn High School  
http://www.millburn.org
 
Computer Science AP
C++


This course follows the introduction to C++ course. It covers the AB-level curriculum as described in the College Boards’ Advanced Placement Course Description for Computer Science.  

Objectives

* Understanding the importance of structured approach to problem solving.

* Learning common algorithms and data structures.

* Learning to code fluently in C++ in a well structured fashion.

* Preparing for the AB-level AP exam in computer science.

* Introduce the concepts of good object oriented design (inheritance, polymorphism and encapsulation).

Organization

The course will consist of class lecture followed by ample hands on exercises, labs and case studies.  The intended ratio of class lecture to actual development efforts will be 2:3 three days of exercises to two days of lecture (as the year progresses, lab time will grow to 4 out of 5 days).  Handouts will be provided for each unit but it is highly recommended that students take copious notes during the lecture.

At the conclusion of the chapter lecture, there will be extensive lab time to work on the workbook questions
And programming problems.  

Chapter tests will be given at the end of each chapter, with the exception of the review lectures.  

Each student will be required to work on a special project that will focus on an area of technology or computer science.  Written documentation and a class presentation of the project are required.  This project is intended to broaden the students vision of our technological landscape and provide a glimpse into the professional IT experience.  


Towards the middle of April, students will be given a practice AB test to work on.  This test is designed to be slightly more difficult than the actual AB test.  

Another practice test will be given out a week before the actual AB test.


Text

C++ How to Program, Deitel & Deitel

Supplemental Sources:
C++ for You++: An Introduction to Programming and Computer Science, AP Edition (Ch 11-28 9) &
Workbook to Accompany C++ for You++, Skylight Publishing, Andover, Massachusetts, 1998.

It is highly recommended that students purchase the workbook.  It can be purchased independently or through the school for $9.60, plus S/H.  The textbook is also recommended,
although not necessary,  as it contains the proper subset of C++ to cover the AP exam.  The textbook can be purchased for $38.00, plus S/H.

Also recommended is the purchase of the AB test preparation book which is $15.95


Course Outline


1.   Review of Computer Science 2 (C++ introduction)

Constants and variables, simple data types. Input and output operators. Arrays, apvector and apmatrix classes. Conditional statements, Boolean expressions, true and false values, relational and logical operators. while, for, do-while loops. The switch statement. Simple algorithms.

1.A.  Discussion of the professional application development environment

The real world of IT is a dynamic, heterogeneous environment that rarely relies on a single technology
to deliver a systems solution to meet a business need.  A technologist’s value is in his/her ability to provide technological solutions that utilize different platforms, communication protocols and development tools.
Use the “software development lifecycle” document.

1.B.   Special Project Overview

In addition to the other assignments and tests, each student will be required to research an area of computer science (or technology) of their choice and prepare both written and oral (a class presentation) documentation of their findings.  Students need to have their topic approved by the instructor.  The project will be due the third week of May.

2. Pointers, references, memory allocation  
Pointers and references. Passing arguments to functions by reference and constant reference. Memory allocation: new and delete operators.

3. Strings  
Literal strings. The apstring class. Input and output for strings.

5. Structures  
User-defined types. Accessing structure members. Passing and returning structures to or from functions. Overloading input and output operators.

6. Modularity
Modular programs. Header files. Projects. Global and static variables.


7. Classes
Classes. Public and private members, encapsulation. Constructors and destructors.

8. Templates
Templated classes and functions.


9. Linked lists  
Introduction to abstract data types. Linked lists as an implementation of the "List" ADT. Linked list traversal; Insert, Remove and Destroy functions. Linked lists vs. arrays. Linked lists with a tail and doubly linked lists.


10. Stacks  
Applications of stacks. Array implementation of a stack. The apstack class.



11. Recursion  
Examples of recursive functions used for handling nested structures or branching processes. Base case and recursive case. Formal reasoning about recursive functions using mathematical induction. When not to use recursion.


12. Queues  
Ring buffer and linked list implementations of queues. The apqueue class. Case study: "Pizza delivery scheduling."

13. Classes-more advanced features. AP free-response practice  
Initializer lists. Constructors with initializer lists in structures and classes. Operator overloading. Canonical features of a class. Constructors as casts.
Practice on past free-response questions that use classes, member functions, overloaded operators. Reading and exercises: Sections 21.1 - 21.5, 21.9 - 21.10.
Labs:Past AP free response questions.


14. Trees
Tree structure and terminology. Binary search trees. Find and Insert functions for binary search trees. Traversals.

15. Expression trees
Prefix, infix, and postfix notations. Converting one notation into another using a stack.
16. Heaps  
Non-linked representation for binary trees. Priority queue as a heap.


17. AP Exam Case Study  
Practice with the College Board's Case Study materials, exercises, and sample questions.
Reading and exercises: The College Board's Case Study booklet and web site
Programming project: Write a client program that uses the Case Study functions; re-implement selected functions in the Case Study code.


18. Analysis of algorithms  
Big-O notation. Linear, logarithmic, and quadratic growth. Examples of "big-O" analysis.
Lab: Based on the AP Case Study.


19. Searching, look-up tables, and hashing  
Sequential and binary search algorithms and their big-O comparison. Look-up tables. Hashing.


20. Sorting  
Selection sort, insertion sort, bubble sort (optional), mergesort, quicksort, and heapsort.
.
21. Final Review  
Final review of the Case Study, the apvector, apmatrix, apstring, apstack, and apqueue classes, past AP exam questions.





Grading

Grading will consist of a combination of assigned labs (projects), written chapter tests, midterm exam and a special project.  Each graded assignment (project, test) will be assigned a point value.  Grades will be a function of the sum of the students accumulated points divided by the sum of the individual point values for each assignment.  

For the projects, value is given to coding style and structure and not just the result.  

For the independent project, value will be placed on content and presentation.

Adjustments to the grade will be made based on preparation, classroom participation and demeanor.
Useful links
Last updated  2008/09/28 07:44:16 PDTHits  200