Programming Fundamentals

Programming Fundamentals (PF) (9%) For Computer Science Students


   PF1. Fundamental programming constructs [core]
   PF2. Fundamental data structures [core]
   PF3. Recursion [core]
   

Recommended Books:

1.    How to Program C++ by Deitel and Deitel

2.    Programming C/C++ by Robert Lafore

3.    Data Structures and Algorithm Analysis by Mark Allen Weiss

4.    Data Structures and Algorithm by Robert Lafore

5.    Data Structures using c and C++ by Yedidyah Langsum,      Moshe

6.    J. Augenstein and Aaron M. Tenembaum

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 [3%] [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:

1. Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit.
2. Modify and expand short programs that use standard conditional and iterative control structures and functions.
3. 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.
4. Choose appropriate conditional and iteration constructs for a given programming task.
5. Apply the techniques of structured (functional) decomposition to break a program into smaller pieces.
6. Describe the mechanics of parameter passing.

PF2. Fundamental data structures [4%] [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:

1. Discuss the representation and use of primitive data types and built-in data structures.
2. Describe how the data structures in the topic list are allocated and used in memory.
3. Describe common applications for each data structure in the topic list.
4. Implement the user-defined data structures in a high-level language.
5. Compare alternative implementations of data structures with respect to performance.
6. Write programs that use each of the following data structures: arrays, records, strings, linked lists, stacks, queues, and hash tables.
7. Compare and contrast the costs and benefits of dynamic and static data structure implementations.
8. Choose the appropriate data structure for modeling a given problem.

PF3. Recursion [2%] [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:

1. Describe the concept of recursion and give examples of its use.
2. Identify the base case and the general case of a recursively defined problem.
3. Compare iterative and recursive solutions for elementary problems such as factorial.
4. Describe the divide-and-conquer approach.
5. Implement, test, and debug simple recursive functions and procedures.
6. Describe how recursion can be implemented using a stack.
7. Discuss problems for which backtracking is an appropriate solution.
8. Determine when a recursive solution is appropriate for a problem.