Programming Fundamentals (PF)
PF1. Fundamental programming constructs [core]
PF2. Algorithms and problem-solving [core]
PF3. Fundamental data structures [core]
PF4. Recursion [core]
PF5. Event-driven programming [core]
Fluency in a programming language is prerequisite to the study of most of computer science. In the CC1991 report, knowledge of a programming language -- while identified as essential -- was given little emphasis in the curriculum. The "Introduction to a Programming Language" area in CC1991 represents only 12 hours of class time and is identified as optional, under the optimistic assumption that "increasing numbers of students . . . gain such experience in secondary school." We believe that undergraduate computer science programs must teach students how to use at least one programming language well; furthermore, we recommend that computer science programs should teach students to become competent in languages that make use of at least two programming paradigms. Accomplishing this goal requires considerably more than 12 hours.
This knowledge area consists of those skills and concepts that are essential to programming practice independent of the underlying paradigm. As a result, this area includes units on fundamental programming concepts, basic data structures, and algorithmic processes. These units, however, by no means cover the full range of programming knowledge that a computer science undergraduate must know. Many of the other areas -- most notably Programming Languages (PL) and Software Engineering (SE) -- also contain programming-related units that are part of the undergraduate core. In most cases, these units could equally well have been assigned to either Programming Fundamentals or the more advanced area.
PF1. Fundamental programming constructs [core]
Minimum core coverage time: 9 hours
Topics:
- Basic syntax and semantics of a higher-level language
- Variables, types, expressions, and assignment
- Simple I/O
- Conditional and iterative control structures
- Functions and parameter passing
- Structured decomposition
Learning objectives:
- Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit.
- Modify and expand short programs that use standard conditional and iterative control structures and functions.
- Design, implement, test, and debug a program that uses each of the following fundamental programming constructs: basic computation, simple I/O, standard conditional and iterative structures, and the definition of functions.
- Choose appropriate conditional and iteration constructs for a given programming task.
- Apply the techniques of structured (functional) decomposition to break a program into smaller pieces.
- Describe the mechanics of parameter passing.
PF2. Algorithms and problem-solving [core]
Minimum core coverage time: 6 hours
Topics:
- Problem-solving strategies
- The role of algorithms in the problem-solving process
- Implementation strategies for algorithms
- Debugging strategies
- The concept and properties of algorithms
Learning objectives:
- Discuss the importance of algorithms in the problem-solving process.
- Identify the necessary properties of good algorithms.
- Create algorithms for solving simple problems.
- Use pseudocode or a programming language to implement, test, and debug algorithms for solving simple problems.
- Describe strategies that are useful in debugging.
PF3. Fundamental data structures [core]
Minimum core coverage time: 14 hours
Topics:
- Primitive types
- Arrays
- Records
- Strings and string processing
- Data representation in memory
- Static, stack, and heap allocation
- Runtime storage management
- Pointers and references
- Linked structures
- Implementation strategies for stacks, queues, and hash tables
- Implementation strategies for graphs and trees
- Strategies for choosing the right data structure
Learning objectives:
- Discuss the representation and use of primitive data types and built-in data structures.
- Describe how the data structures in the topic list are allocated and used in memory.
- Describe common applications for each data structure in the topic list.
- Implement the user-defined data structures in a high-level language.
- Compare alternative implementations of data structures with respect to performance.
- Write programs that use each of the following data structures: arrays, records, strings, linked lists, stacks, queues, and hash tables.
- Compare and contrast the costs and benefits of dynamic and static data structure implementations.
- Choose the appropriate data structure for modeling a given problem.
PF4. Recursion [core]
Minimum core coverage time: 5 hours
Topics:
- The concept of recursion
- Recursive mathematical functions
- Simple recursive procedures
- Divide-and-conquer strategies
- Recursive backtracking
- Implementation of recursion
Learning objectives:
- Describe the concept of recursion and give examples of its use.
- Identify the base case and the general case of a recursively defined problem.
- Compare iterative and recursive solutions for elementary problems such as factorial.
- Describe the divide-and-conquer approach.
- Implement, test, and debug simple recursive functions and procedures.
- Describe how recursion can be implemented using a stack.
- Discuss problems for which backtracking is an appropriate solution.
- Determine when a recursive solution is appropriate for a problem.
PF5. Event-driven programming [core]
Minimum core coverage time: 4 hours
Topics:
- Event-handling methods
- Event propagation
- Exception handling
Learning objectives:
- Explain the difference between event-driven programming and command-line programming.
- Design, code, test, and debug simple event-driven programs that respond to user events.
- Develop code that responds to exception conditions raised during execution.
