CA.SFU.FAS.UCC/Papers:2003-16

Proposed Introductory Computing Science Course Sequence

G. Baker, B. Bart, T. Dixon, Q. Gu, A. Lavergne, D. Mitchell, Syllabus Working Group, School of Computing Science

October 6, 2003

Proposal

Replace the current CMPT 101/104 (Introduction to Computer Programming) and CMPT 201 (Data and Program Abstraction), with a three course sequence, tentatively denoted CMPT 120, CMPT 121, and CMPT 221, each is a three credit course.

Rationale

Currently, CS majors take CMPT 101 as their only introduction to CS and programming, followed by CMPT 201 (Data Structures) and CMPT 275 (Software Engineering). There are several serious problems with this, among which we will try to partially address the following:

  1. One semester is not nearly enough time to bring students (even bright ones) from no programming knowledge at all to having a reasonably solid facility with even the main componenets of a large modern language like Java or C++.
  2. By starting students with an introduction to programming only, with very little other CS content, we propagate the idea the "CS = programming". This is unfortunate for CS majors and non-CS majors alike (and for our field). Moreover, attempting to teach a "full-sized" language like Java in one semester results in a highly "syntax-directed" approach, taking away from the time available to focus on more important intellectual tasks aspects.
  3. Students enter CMPT 101 with widely diverse backgrounds (and expectations). A large proportion of students have absolutely no exposure to programming, and a similarly large fraction have written substantial programs or written programs in more than one language. Whatever choice of rate and depth of coverage is made, there are many frustrated students.
  4. Students are not trained to have the capability of self-learning new programming languages and OS, which slows down the teaching at upper level courses.
The result is that students are often dissapointed and frustrated with their CMPT 101 experience, and moreover have inadequate preparation for upper level work. We note the that ACM/IEEE-CS curriculum reports specifically cite these same as common difficulties with first year CS programs. We further note that these problems are also closely associated with issues that have been identified as tending to drive women away from computing science programs.

The Proposal

The current ACM curriculum guidelines offer several possibilities for curriculum design. We note that all of these involve two-course introductions in first year, and that they in fact advocate a 3-course introduction where possible. This is in contrast to our current one course introduction. Thus, we propose switching to a two course introduction in the first year. There are several choices for these two courses. To address the problems described above (and others) several ACM reports have advocated beginning with a broad introduction to CS, rather than starting with a pure introduction to programming. This is the approach we propose, although our implementation will be a little different than that proposed by the ACM, to avoid re-designing too many other courses. We also contend that all CS majors should be exposed to a general overview of the field, and in particular it is appropriate and desireable that their very first university experience of computing should be such a course. Benefits of this approach include:
  1. Students will have a better appreciation of the field, and be better equipped to evaluate their interest in pursuing a CS program.
  2. Students who are more motivated by other aspects of the field than programming will not be discouraged from pursuing CS.
  3. Students would be exposed to the intellectual richness and diversity of the field early. This is good for CS majors, for non-CS majors, and for the field.
  4. Students without previous programming experience would be less disadvantaged, since performance is less closely tied to programming proficiency.
Note that there is no suggestion to exclude programming, rather that the heavy syntax of a language like Java should be introduced more slowly, with early emphasis on the power of computing as a paradigm and development other concepts and skills from the beginning. The programming facilities whose main purpose is to support large-scale system structure should follow as the students attain fundamental skills and an appreciation of what those facilities are good for. We propose CMPT 120 as the broad introduction to CS. CMPT 120 can also be used as a Breadth Course required in the future university undergraduate curriculum.

After CMPT 120, CMPT 121 is proposed for introducing CS and OOP to the students who take CS as a major. By CMPT 120, the students in CMPT 121 should have the fundamental knowledge on CS and be able to solve basic problems by a high level programming languages. With this background, CMPT 121 can be focused on the fundamentals of CS and OOP in a more professional way.

One of the problems with our current curriculum is that our students are not trained to learning new knowledges by themselves. We propose CMPT 221 as a course which introduces data structures and OOP, meanwhile provides the chances for the students to gain the self-learning capability. The flexible teaching style (with classes and lab sessions mixed) will be used and students will be exposed in lab to a programming language different from the one used in classes for the self-learning training.

Proposed CMPT 120/121/221 Curriculum

The goal is a curriculum which

Intended CMPT 120 Outcomes

After completing CMPT 120, we intend the students will:

  1. Have general appreciation of computing science, understand what computation is (computable/uncomputable functions), what a computer is (RAM model and  real computers), what a program is, and what a programming language is.
  2. Understand pseudo code, basic data types, data structures, control structures, parameter passing, and algorithms.
  3. Be able to solve elementary problems by a high level programming language.
  4. Have been exposed to some the history of the concepts of algorithms and computation, and computers.
After completing CMPT 121, we intend that students will:
  1. Have a facility with basic object-oriented programming.
  2. Understand the formal definition of computation, there are uncomputable things that we care about, and that there is a difference between things that are not computable and things that we don't know how to compute. Understand formal models of computation, such as the RAM and Turing machine models, and the relationship between these models and real computers. Be exposed to recursion and compelxity analysis. 
  3. Understand basic components in software development: write specification for simple problems; formulate a precise computational problem to solve it; design an algorithm for the problem; reason about the correctness of the algorithm; implement the algorithm in a program; reason about the correctness of the program; analyse the efficiency of the program.
  4. Be exposed to diverse applications of algorithms, more than one programming  paradigm, and social issues of computing science.
After completing CMPT 221, we intend the students will:
  1. Be skillful in OOP and able to solve problems using OOP.
  2. Understand information hiding, recursion, time/space compelxity analysis.
  3.  Understand complex data structures, external data access. Be able to use them to solve problems.
  4. Have the capability of self-learning a new programming language and operating systems.

Outline of CMPT 120 Syllabus

  1. Some elements of discrete math, as needed.
  2. Fundamental Programming Constructs: basic syntax and semantics of a high-level language; variables; types; expressions; statements; simple I/O; conditional and iterative execution; procedure and function calls; parameter passing; structured decomposition.
  3. Algorithms and Problem Solving: history of the idea of algorithm; examples of simple but interesting algorithms; simple problem solving strategies; role of algorithms in problem solving; concept and properties of algorithms.
  4. The RAM model of computation and its relationship to current electronic computers. The idea of computation and computation as a science. The notion of computable objects/behaviours.
  5. Basic Data Structures: (a few) primitive types; strings; arrays or lists
  6. The idea of algorithm analysis: informal complexity notions; reasoning about algorithm and program correctness.
  7. Fundamental Computing Algorithms: Sequential search; Bubble/Selection sort. simple numerical algorithms;
  8. Defining problems; defining solutions; specifications ;
  9. Prerequisistes:  BC-12 Math.

Outline of CMPT 121 Syllabus

  1. Fundamental Data Structures: (more) primitive types; arrays; strings; lists; queues; stacks
  2. OOP: classes and instances; exception handling; GUI; references; event-driven programming; etc.
  3. Software development process: problem statement->OO design (pseudo code)->OO solution->test/debugging.
  4. Recursion: Concept of recursion; divide-and-conquer strateties.
  5. Basic Algorithm Analysis: Big-O Notation; standard complexity classes.
  6. quadratic and O(nlogn) sorting algorithms. sequential and binary search.
  7. History of Computation: History of Computation as a Science; History of Computers ; History of Programming languages
  8. Basic Computatiliby: Machine models (RAM; ASM; TURING MACHINE); Computable functions; tractable and intractable problems; the halting problems; uncomputable functions and implications of uncomputability.
  9. Specifying correctness; proving correctness; designing tests.
  10. Introduction to social aspects.
  11. Prequisite: CMPT 120 or Admission Test.

Outline of CMPT 221 Syllabus

  1. Data structures: Stacks, queues, decks (formal definition of methods, implementation options), trees, hash tables, head and priority queues.
  2. Recursion: callback stack, transforming recursive to iterative.
  3. Information hiding
  4. Time and memory efficiency
  5. Basic algorithms: paser, tree traversal, binary search tree, quick sort, heap sort
  6. External data storage and sorting
  7. OOP: Applets, swing, polymophism, inheritance, references, operator overloading.
  8. Self-learning: A new OOP langauge, UNIX/LINUX.
  9. Prequisite: CMPT 121, MACM101.
We understand that the above outlines of syllabi may not be precise enough to warrant an implementation of the courses we want. Here we propose implementation models for the three courses. We list explicitly what a course should cover in four categories: CS concepts, Algorithms, Programming Langauges, and Assignments. The suggested sketches of models are given in the appendix. Detailed teaching materials are expected to be developed by the instructors for the courses.

Appendix A: CMPT 120 Course Outline

Unit
 		Week
 		Comp. Sci.
 		Algorithms
 		Prog. Lang.
 		Assignment/Examples
1.
 1
 Sketch of CS
Intro of course
 Familiar Algs. (e.g., manual arithmetic) + non-obvious examples
 Psuedo-code+
real example
 Type, compile, run, submit
a given sample program
2.
 1
 Computer, program, programming
language, OS, application program
 Examples of computing
with a sequence of integer
calculations
 Int type (values + operators);variables and
assignment, sequencing, very simple output
 Program with sequence
of calculations and simple output
3.
 1
 RAM model of
computation
 Simple conditionals
 Boolean type & simple expressions; simple if-then/-else blocks
 Program with output
depending on input and decisions by user
4.
 1
 RAMs and real
computers
 Iteration, max/min/sum
linear search
 Iteration (while/for)
loops, 1-dim array
 Compute max/min/sum
linear search
5.
 1
 File systems, OS,
history of CS as a
science
Basic file I/O
 Examples on file I/O
6.
 1
 Binary encoding
 Binary and other
bases, binary arithmetic
 EvaluatingBooleans,
nesting conditionals
 Base conversion
7.
 1
 Computable functions
 Collections, dot
production
 2-dim arrays
 Scalar x vector, dot product
8.
 1
 Probelm decomposition &  solving strategies
 Basic graphics
 Library, procedures
parameter passing
 Drawing/moving simple
objects, bar-graphs
9.
 1
 Floating point numbers, errors
 Numerical methods
 Real type
 mean/std.dev/draw curves
10.
 1
 Non-computable functions
 String processing
reverse
 String type, ASCII
 String processing
11.
 1
 Correctness
 Algorithmic paradigms
 Programming languages
12.
 1
 Time complexity
 Ordering, selection/insertion sort
 Programming languages
 Implementation of sorting algorithms

Appendix B: CMPT 121 Course Outline

A number of case studies will be used to introduce software development process: problem statement->OO design (pseudo code)->OO S/W solution ->testing and debugging.

Unit
 Weeks
Computing Science
Algorithms
Programming Language
Assignment/Examples
1. 1 120 review, basic CS
 Linear search, selection sort, dot product
 Review of 120 using Java Implementation of basic
algorithms in Java
2. 2

Case Study #1
Software Development Process: problem statement -> O.O. design (pseudocode) -> O.O. S/W Solution -> Testing and Debugging

 Conditional
iteration (Java)		 Classes
Exception Handling
(+ Applet,for graphics)
games (use random numbers)
(connect with exercise/assignement/example
seen in similar units of 120)
3. 2

Case Study #2


 Explain binary search visually, introduce its two implementations:
iterative binarysearch		 Arrays, recursion, GUI intro Implement search,
"Hello World" GUI
4. 2 Recursion, divide and conquer, Induction, assertion, correctness, complexity analysis
computational model RAM 		 Recursive Binary search,
Mergesort		 GUI intro
 Snowflake (GUI worked into
other assignments as well)
5. 2

Case Study #3


 Simple parsing
 Strings
File I/O
More about Exception Handling		 parse an int/floating point, implement grep, paragraph formatting, line breaks, code prettyprinter
6. 2 Case Study #4,

 stacks and queues (informal, simple implementation) parsing expressions
 References
Linked List
List ADT		 simple expression parser
7. 1 Turing Machine and computability
Revisit Big O notation		 Review of sorting algorithms, selection or insertion sort
- mergesort
implement FSM, implement
sort, Turing machine paper work
8. 1 User Interface Design
Event-driven programming
(Applet, AWT, SWING)		 GUI
9.
 1
 Social issue of CS: privacy issue,
employment issue;
Program paradigms
Examples  of  different programming
languages

Appendix C: CMPT 221 Course Outline

Unit
 Weeks
Computing Science
Algorithms
Programming Language
Lab/Assignment/Examples
1.
 1
 121 review
 121 review, basic ADT
 Applets, swing
 Fundamental Unix/Linux, C++
2.
 2
 Information hiding, running time analysis
 basic ADTs: stacks, queues, decks.  Formally (methods defined, implementation options)
 References (for data structs), operator overloading
 Fundamental Unix/Linux, C++
Implementation of stacks, queues,
in Java and C++,
Paser program
4.
 3
 Recursion concepts: callback stack, transforming recursive -> iterative
 Trees: binary, traversals, general trees, BSTs
 Java interface
 Implementation of trees: binary, traversals, general trees, BSTs,
in Java and C++
4.
 1
 Hash functions
 Hash tables and algorithms
 GUI
 GUI
Implementation of hash tables
in Java and C++
5.
 2
 Heaps, priority queues
 Heaps, priority queues
 Polymophism, inheritance
 Implementation and applications of heaps and priority queues,
linking object code.
6.
 2
 Time and memory efficiency
 Sorting: quicksort, heapsort, mergesort, in-place sorting
 Polymophism, inheritance
 Implementation of sorting algorithms, project.
7.
 1
 External storage and sorting
 External storage and sorting
Implementation of external soritng, project.