Fundamental Computer Science Concepts Sequence - TCSU CSCI SEQ A
Description
Introduction to the discipline of computer science; covers the material traditionally found in courses that introduce problem solving, computer programming, algorithms, data structures, computer architecture, assembly programming and discrete structures.
Recommended Preparation
Pre-calculus with a grade of “C” or better
Minimum Unit Requirements
12 semester units
Course Topics
I. Discrete Structures (DS)
DS1. Functions, relations and sets: Minimum coverage time: 6 hours
Topics
1. Functions (surjections, injections, inverses, composition)
2. Relations (reflexivity, symmetry, transitivity, equivalence relations)
3. Sets (Venn diagrams, complements, Cartesian products, power sets)
4. Pigeonhole principle
5. Cardinality and countability
Learning Outcomes
1. Explain with examples the basic terminology of functions, relations, and sets;
2. Perform the operations associated with sets, functions, and relations;
3. Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context; and
4. Demonstrate basic counting principles, including uses of diagonalization and the pigeonhole principle.
DS2. Basic logic: Minimum coverage time: 10 hours
Topics
1. Propositional logic
2. Logical connectives
3. Truth tables
4. Normal forms (conjunctive and disjunctive)
5. Validity
6. Predicate logic
7. Universal and existential quantification
8. Modus ponens and modus tollens
9. Limitations of predicate logic
Learning Outcomes
1. Apply formal methods of symbolic propositional and predicate logic;
2. Describe how formal tools of symbolic logic are used to model algorithms and real-life situations;
3. Use formal logic proofs and logical reasoning to solve problems such as puzzles; and
4. Describe the importance and limitations of predicate logic.
DS3. Proof Techniques: Minimum coverage time: 12 hours
Topics
1. Notions of implication, converse, inverse, contrapositive, negation, and contradiction
2. The structure of formal proofs
3. Direct proofs
4. Proof by counterexample
5. Proof by contraposition
6. Proof by contradiction
7. Mathematical induction
8. Strong induction
9. Recursive mathematical definitions
10. Well orderings
Learning Outcomes
1. Outline the basic structure of and give examples of each proof technique described in this unit;
2. Discuss which type of proof is best for a given problem;
3. Relate the ideas of mathematical induction to recursion and recursively defined structures; and
4. Identify the difference between mathematical and strong induction and give examples of the appropriate use of each.
DS4. Basics of counting: Minimum coverage time: 5 hours
Topics
1. Counting arguments
2. Sum and product rule
3. Inclusion-exclusion principle
4. Arithmetic and geometric progressions
5. Fibonacci numbers
6. The pigeonhole principle
7. Permutations and combinations
8. Basic definitions
9. Pascal's identity
10. The binomial theorem
11. Solving recurrence relations
12. Common examples
Learning Outcomes
1. Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application;
2. Solve a variety of basic recurrence equations; and
3. Analyze a problem to create relevant recurrence equations or to identify important counting questions.
DS5. Trees: Minimum coverage time: 3 hours
Topics
1. Trees and Graphs
2. Spanning trees
3. Traversal strategies
Learning Outcomes
1. Demonstrate different traversal methods for trees and graphs;
2. Model problems in computer science using trees; and
3. Relate trees to data structures, algorithms, and counting.
II. Programming Fundamentals (PF)
PF1. Fundamental programming constructs: Minimum coverage time: 9 hours
Topics
1. Basic syntax and semantics of a higher-level language
2. Variables, types, expressions, and assignment
3. Simple I/O
4. Conditional and iterative control structures
5. Functions and parameter passing
6. Structured decomposition
Learning Outcomes
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; and
6. Describe the mechanics of parameter passing.
PF2. Algorithms and problem-solving: Minimum coverage time: 6 hours
Topics
1. Problem-solving strategies
2. The role of algorithms in the problem-solving process
3. Implementation strategies for algorithms
4. Debugging strategies
5. The concept and properties of algorithms
Learning Outcomes
1. Discuss the importance of algorithms in the problem-solving process;
2. Identify the necessary properties of good algorithms;
3. Create algorithms for solving simple problems;
4. Use pseudocode or a programming language to implement, test, and debug algorithms for solving simple problems; and
5. Describe strategies that are useful in debugging.
PF3. Fundamental data structures: Minimum coverage time: 12 hours
Topics
1. Primitive types
2. Arrays
3. Records
4. Strings and string processing
5. Data representation in memory
6. Static, stack, and heap allocation
7. Runtime storage management
8. Pointers and references
9. Linked structures
10. Implementation strategies for stacks, queues, and hash tables
11. Implementation strategies for trees
12. Strategies for choosing the right data structure
Learning Outcomes
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; and
8. Choose the appropriate data structure for modeling a given problem.
PF4. Recursion: Minimum coverage time: 5 hours
Topics
1. The concept of recursion
2. Recursive mathematical functions
3. Simple recursive procedures
4. Divide-and-conquer strategies
5. Recursive backtracking
6. Implementation of recursion
Learning Outcomes
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; and
8. Determine when a recursive solution is appropriate for a problem.
III. Architecture and Organization (AR)
AR2. Machine level representation of data: Minimum coverage time: 3 hours
Topics
1. Bits, bytes, and words
2. Numeric data representation and number bases
3. Fixed- and floating-point systems
4. Signed and twos-complement representations
5. Representation of nonnumeric data (character codes, graphical data)
6. Representation of records and arrays
Learning Outcomes
1. Explain the reasons for using different formats to represent numerical data;
2. Explain how negative integers are stored in sign-magnitude and twos complement representation;
3. Convert numerical data from one format to another;
4. Discuss how fixed-length number representations affect accuracy and precision;
5. Describe the internal representation of nonnumeric data; and
6. Describe the internal representation of characters, strings, records, and arrays.
AR3. Assembly level machine organization: Minimum coverage time: 9 hours
Topics
1. Basic organization of the von Neumann machine
2. Control unit; instruction fetch, decode, and execution
3. Instruction sets and types (data manipulation, control, I/O)
4. Assembly/machine language programming
5. Instruction formats
6. Addressing modes
7. Subroutine call and return mechanisms
8. I/O and interrupts
Learning Outcomes
1. Explain the organization of the classical von Neumann machine and its major functional units;
2. Explain how an instruction is executed in a classical von Neumann machine;
3. Summarize how instructions are represented at both the machine level and in the context of a symbolic assembler;
4. Explain different instruction formats, such as addresses per instruction and variable length vs. fixed length formats;
5. Write simple assembly language program segments;
6. Demonstrate how fundamental high-level programming constructs are implemented at the machine-language level;
7. Explain how subroutine calls are handled at the assembly level; and
8. Explain the basic concepts of interrupts and I/O operations.
IV. Programming Languages (PL)
PL1. Overview of programming languages: Minimum coverage time: 2 hours
Topics
1. History of programming languages
2. Brief survey of programming paradigms
3. Procedural languages
4. Object-oriented languages
5. Functional languages
6. Declarative, non-algorithmic languages
7. Scripting languages
8. The effects of scale on programming methodology
Learning Outcomes
1. Summarize the evolution of programming languages illustrating how this history has led to the paradigms available today;
2. Identify at least one distinguishing characteristic for each of the programming paradigms covered in this unit;
3. Evaluate the tradeoffs between the different paradigms, considering such issues as space efficiency, time efficiency (of both the computer and the programmer), safety, and power of expression; and
4. Distinguish between programming-in-the-small and programming-in-the-large.
PL4. Declarations and types: Minimum coverage time: 3 hours
Topics
1. The conception of types as a set of values together with a set of operations
2. Declaration models (binding, visibility, scope, and lifetime)
3. Overview of type-checking
4. Garbage collection
Learning Outcomes
1. Explain the value of declaration models, especially with respect to programming-in-the-large;
2. Identify and describe the properties of a variable such as its associated address, value, scope, persistence, and size;
3. Discuss type incompatibility;
4. Demonstrate different forms of binding, visibility, scoping, and lifetime management;
5. Defend the importance of types and type-checking in providing abstraction and safety; and
6. Evaluate tradeoffs in lifetime management (reference counting vs. garbage collection).
PL5. Abstraction mechanisms: Minimum coverage time: 3 hours
Topics
1. Procedures, functions, and iterators as abstraction mechanisms
2. Parameterization mechanisms (reference vs. value)
3. Activation records and storage management
4. Type parameters and parameterized types - templates or generics
5. Modules in programming languages
Learning Outcomes
1. Explain how abstraction mechanisms support the creation of reusable software components;
2. Demonstrate the difference between call-by-value and call-by-reference parameter passing;
3. Defend the importance of abstractions, especially with respect to programming-in-the-large; and
4. Describe how the computer system uses activation records to manage program modules and their data.
PL6. Object-oriented programming: Minimum coverage time: 10 hours
Topics
1. Object-oriented design
2. Encapsulation and information-hiding
3. Separation of behavior and implementation
4. Classes and subclasses
5. Inheritance (overriding, dynamic dispatch)
6. Polymorphism (subtype polymorphism vs. inheritance)
7. Class hierarchies
8. Collection classes and iteration protocols
9. Internal representations of objects and method tables
Learning Outcomes
1. Justify the philosophy of object-oriented design and the concepts of encapsulation, abstraction, inheritance, and polymorphism;
2. Design, implement, test, and debug simple programs in an object-oriented programming language;
3. Describe how the class mechanism supports encapsulation and information hiding;
4. Design, implement, and test the implementation of “is-a” relationships among objects using a class hierarchy and inheritance;
5. Compare and contrast the notions of overloading and overriding methods in an object-oriented language;
6. Explain the relationship between the static structure of the class and the dynamic structure of the instances of the class; and
7. Describe how iterators access the elements of a container.
V. Social and Professional Issues (SP)
SP1. History of Computing: Minimum coverage time: 1 hour
Topics
1. Prehistory -- the world before 1946
2. History of computer hardware, software, networking
3. Pioneers of computing
Learning Outcomes
1. List the contributions of several pioneers in the computing field;
2. Compare daily life before and after the advent of personal computers and the Internet; and
3. Identify significant continuing trends in the history of the computing field.
VI. Software and Engineering (SE)
SE1. Software design: Minimum coverage time: 8 hours
Topics
1. Fundamental design concepts and principles
2. Design strategy
3. Software architecture
4. Structured design
5. Object-oriented analysis and design
6. Component-level design
7. Design for reuse
Learning Outcomes
1. Discuss the properties of good software design;
2. Compare and contrast object-oriented analysis and design with structured analysis and design;
3. Evaluate the quality of multiple software designs based on key design principles and concepts;
4. Select and apply appropriate design patterns in the construction of a software application;
5. Create and specify the software design for a software product from a software requirement document, an accepted program design methodology (e.g., structured or object-oriented), and appropriate design notation;
6. Conduct a software design review using appropriate guidelines;
7. Evaluate a software design at the component level; and
8. Evaluate a software design from the perspective of reuse.
SE2. Using APIs: Minimum coverage time: 5 hours
Topics
1. API programming
2. Class browsers and related tools
3. Programming by example
4. Debugging in the API environment
5. Introduction to component-based computing
Learning Outcomes
1. Explain the value of application programming interfaces (APIs) in software development;
2. Use class browsers and related tools during the development of applications using APIs; and
3. Design, implement, test, and debug programs that use large-scale API packages.
AL. Algorithms: Minimum coverage time: 2 hours
Topics
1. Big O notation
2. Basic sorting and searching algorithms
Learning Outcomes
1. Explain the use of O notation; and
2. Explain the basic sorting and searching algorithms.
Justification
1. This 12 semester unit description has been approved by the CS group both at the IMPAC and the LDTP meetings.
2. The 12 semester unit described introduces students to a set of fundamental computer science topics. In the spirit of the ACM 2001 Curriculum Report, from which these topic groups are based, the disciplinary group is not specifying individual course content.
3. Most Community Colleges have an Introduction to Programming, Programming with Data Structures, Discrete Mathematics, Assembly/Architecture courses which would articulate after some modifications to their courses.
4. Individual institutions have the freedom, as they believe appropriate to package the material in any number of courses.
Descriptor PDF
Courses Approved (Coming Soon)
Back
Documents contained on this page require Adobe Reader to view. If you do not have the Adobe Reader, you can download it free from the Adobe site.
.
|
