What CSC Graduates Should Know

[revised 2/9/96]

What follows is a proposed list of what our undergraduate curriculum should teach. Right now it is neither complete nor in any sort of consistent format. it should be viewed as a starting point for curriculum discussions. Please send suggested additions or comments to Matt Stallmann (Matt_Stallmann@ncsu.edu). Things that I deliberately omitted from the list, with my comments, are in the overflow list.

Major Themes

The following issues should be addressed frequently throughout the curriculum, whenever and wherever appropriate.
  1. Scientific approaches to debugging (formulating a hypothesis about the source of error and testing it, with or without the aid of a debugging tool).
  2. Software correctness (making precise assertions about entry and exit conditions for subprograms, loop invariants, etc.)
  3. Effective communication of technical ideas and details (this includes comments in programs, external documentation, oral presentations, and teamwork).
  4. Object-oriented design and engineering.
  5. Recursion in software design and analysis.
  6. Quantitative analysis of software (this includes complexity analysis with big oh notation, analysis of error propagation, performance evaluation of systems, back of envelope calculations).
  7. Ethics (what are the individual and societal impacts of technical decisions).
  8. Multiprocessing (what parts of a computation can be done independently, if two processes work independently what do they have to communicate, etc.).
  9. High-level systems views of computing and how it interacts with the rest of the world.
  10. Understanding the (simplifying) assumptions behind theories and analyses.
  11. Risks: potential sources of trouble (related to simplifying assumptions and high-level system perspectives).

Fundamental Algorithms

These are algorithms that students should know from memory (or with very little help from a reference).
  1. Insertion sort.
  2. Merge sort.
  3. Quicksort.
  4. Root finding (binary search, Newton's method).
  5. Matrix multiplication (basic algorithm).
  6. Gaussian elimination.
  7. Radix conversion (e.g. binary to decimal and vice-versa).
  8. Tree and graph traversals (preorder, postorder, depth-first, breadth-first)

Topics

These are actual topics that could be assigned to specific courses with an indication of how many hours should be spent. Notations in brackets are ACM Curriculum 1991 "knowledge units". Numbers in parentheses are approximate lecture hours that should be devoted to the topic. I have purposely not indicated the courses in which these topics are currently taught to allow us to think more freely about how the curriculum could be structured.
  1. Design and implementation of basic data structures (lists, arrays, tables, stacks, queues, trees, and graphs). [AL1] (15)
  2. Abstract data types (separating implementation from use of data, defining data in terms of the operations on it). [AL2] (6)
  3. Recursive algorithms and programs. [AL3] (3)
  4. Big oh notation, worst- and average-case analysis. [AL4] (10)
  5. Nondeterminism, P & NP, NP-completeness. [part of AL5] (2) (exposure only)
  6. Sorting and searching. [AL6] (5)
  7. Computability and undecidability (the Halting problem). [AL7] (3) (exposure only, comprehension should not be expected)
  8. Divide and conquer algorithms and recurrence relations. [part of AL8] (3)
  9. Combinational (gates, Boolean algebra) and sequential (flip-flops, state machines) logic. [AR1] (12)
  10. Composition of computers from logic circuits. (10)
  11. The stored-program computer (including the fetch-decode-execute cycle for computer instructions). [AR4] (15)
  12. Basic computer organization (CPU, memory, I/O, buses). [AR5] (12)
  13. Handling of I/O operations (concurrency and communication at the machine level), interrupt routines. [AR6] (6)
  14. User interfaces (command interpreters, shells, menu-driven systems, pointing devices, common principles of interface toolkits, design issues). [HU1] (5)
  15. Number representation (finite precision, errors in arithmetic and portability, implications for numerical software). [NU1] (5)
  16. Memory organization, virtual memory and caches. [OS5] (4)
  17. Representation of data types (basic types in C++, creation of user-defined types). [PL3] (6)
  18. Sequence control (expressions, statements, subprograms, exception handling). [PL4] (6)
  19. Finite automata and regular expressions. [PL7] (10)
  20. Context-free grammars and pushdown automata (including LL(1) or recursive-descent parsing). [PL8] (10)
  21. Problem solving (abstraction, stepwise refinement, use of existing programs). [SE1] (16)
  22. The software life cycle (requirements, specification, design, implementation, verification and validation). [SE2] (8)
  23. Software requirements and specifications. [SE3] (5)
  24. Software design, implementation, and testing (bottom-up versus top-down implementation, for example). [SE4] (10)
  25. Verification and validation. [SE5] (10)
  26. Sets, relations, functions, and closure. (10)
  27. Propositional calculus. (10)
  28. Predicate calculus. (6)
  29. Basic probability and statistics (counting, conditional probability, mean and standard deviation, distributions: normal, uniform, etc). (not relevant -- taught in non-CSC course)
  30. Exposure to different programming paradigms with at least one non-trivial programming assignment in a non-procedural language. [related to PL11] (6)