Computer Science I Topic Outline (Curriculum Guide) Revised: 6-7-04
Optional
I. Object-Oriented Program Design
The overall goal for designing a piece of software (a computer program) is to correctly solve the given problem. At the same time, the design process includes specifying and designing a program that is understandable, can be adapted to changing circumstances, and has the potential to be reused in whole or in part. The design process needs to be based on a thorough understanding of the problem to be solved.
A. Program Design
1. Read and understand a problem’s description, purpose, and goals.
2. Identification of subtasks to be performed
3. Identification of the data types and objects needed to solve the problem.
4. Identify reusable components from existing code using classes and class libraries.
B. Class Design
1. Modify existing classes.
2. Design and implement a class.
3. Implement an interface
4. Choose appropriate data representation and algorithms.
5. Class Qualifiers
a. static
b. final
6. Class Members
a. variables
i. instance variables
b. constants
i. instance constants
c. methods (accessor, modifier, constructor)
C. Documentation
1. Internal comments
a. line comments //
b. block comments /*
2. Meaningful identifiers
3. Program style
a. indentation
b. white space
II. Program Implementation
The overall goals of program implementation parallel those of program design. Created classes, that fill common needs, should be built so that they can be reused easily in other programs. Object-oriented design is an important part of program implementation.
A. Implementation Techniques
1. Methodology
a. Object-oriented development
b. Encapsulation and information hiding
c. Procedural abstraction
2. Objects
a. Wrapper classes
i. Character
ii. Integer
iii. Double
iv. Graphics
b. User-defined methods
i. Return methods
ii. Void methods
c. Parse methods
i. parseInt
ii. parseDouble
iii. string tokenizer
d. Instantiation
e. Object comparison
i. references vs. values
ii. equals( ) (contents) vs. = = (address)
B. Program Constructs
1. Import statements
a. I/O
b. Text
c. Util
2. Primitive types
a. int
b. double
c. boolean
d. char
3. Declaration
a. Constant declarations
b. Variable declarations
c. Class declarations
d. Interface declarations
e. Method declarations
f. Parameter declarations
4. Input and output
a. Console
i. Buffered reader, string parsing
ii. System.out.print, System.out.println
iii. Escape sequences
- \ n
- \ \
- \ ”
- \ u n n n n
- \ ‘
- \ t
b. Files
i. Text files
ii. ready method
c. GUI
5. Control
a. Sequential
i. Arithmetic operators
- +, -, *, /, %
ii. Assignment operators
- =, + =, - =, * =, / =, % =
iii. Unary operators
- -, + +, - - (post)
b. Conditional
i. if, if-else
ii. switch, break
iii. Logical operators
- !, | |, &&, ^
- <<, >>, &, |
- short circuit
- Boolean algebra
iv. Relational operators
- = =, ! =, <, < =, >, > =
c. Iteration
- while, for, nested loops
- do-while
d. Recursion
e. Type cast
i. primitive
III. Program Analysis
The analysis of programs includes analyzing and testing programs to determine whether they correctly meet their specifications. It also includes the analysis of programs or algorithms they implement when applied to different data sets.
A. Testing
1. Test methods in isolation (Stepwise refinement)
2. Identify boundary cases and generate appropriate test data (Robust behavior)
B. Debugging
1. Categorize errors
a. compile-time vs. run-time
b. syntax vs. logic
2. Identify and correct errors
3. Techniques
a. add extra output statements
b. hand-trace code
C. Understand and modify existing code
D. Understand error handling
1. Understand exceptions
2. Unchecked exceptions
a. null pointer
b. index out of bounds
c. array index out of bounds
3. Checked exceptions
a. file not found
E. Analysis of Algorithms
1. Exact calculation of statement execution counts
2. Effective algorithm selection
F. Numerical representations and limits
1. Representations of numbers in different bases
2. Limitations of finite representations
a. maximum integer
b. imprecision of real number representations
c. integer bounds
d. imprecision of floating-point representations
e. round-off error
IV. Standard Data Structures
Data structures are the means by which the information used by a program is represented within the program. An important theme of the development and application of data structures is abstraction.
A. Simple data types
1. Use primitives: int, double, boolean, char
a. Variables
b. Constants (“final” keyword)
2. Typecasting
a. Primitive
B. String object
1. Concatenation
2. String methods
a. substring
b. charAt
c. length
d. indexOf
e. valueOf
f. lastIndexOf
3. Comparison methods
a. equals
b. equalsIgnoreCase
c. compareTo
d. compareToIgnoreCase
C. Arrays
1. One-dimensional
a. Traversal
b. Insertion
c. Deletion
2. Two-dimensional
a. Traversal
D. Scope
1. Class variables (static)
2. Instance variables (non-static)
3. Method variables (local)
4. Block variable (loops, ifs)
E. String Tokenizer
1. nextToken
2. hasMoreTokens
3. countTokens
V. Standard Algorithms
Standard algorithms can serve as examples of good solutions to standard problems. Programs implementing them can serve as models of good program design. They provide examples for analysis of program efficiency. Many are intertwined with standard data structures.
A. Operations on data structures
1. Traversals
2. Insertions
3. Deletions
B. Searching
1. Sequential (linear)
2. Binary
C. Sorting
1. Selection
2. Bubble
VI. Computer Systems
A working knowledge of the major hardware and software components of computer systems is necessary for the study of computer science as is the importance of considering the ethical and social implications of computing systems. These topics need not be covered in detail, but should be considered throughout the course.
A. Major hardware components
1. Primary and secondary memory
2. Processors
3. Peripherals
B. System software
1. Language translators
2. Compilers vs. assemblers
3. Operating systems
C. Types of systems
1. Single-user systems
2. Networks
D. Responsible use of computer systems
1. System reliability
2. Privacy
3. Legal issues and intellectual property
4. Social and ethical ramifications of computer use
VII. Optional Topics Worthy of Study
A. Lisp
B. FSAs – regular expressions
C. Boolean algebra advanced
D. GUI
E. Game Programming
F. Assembly language
G. Bit string flicking
H. Digital Electronics
I. Prefix/Postfix/Infix
J. Graph Theory