CS101B. Introduction to Computer Science

Prerequisites: No programming or computer science experience is required. Students should have sufficient facility with high-school mathematics to solve simple linear equations and to appreciate the use of mathematical notation and formalism.

Syllabus:

• Discrete mathematics: Functions, relations, and sets; basic logic; proof techniques; basics of counting; discrete probability
• Fundamental programming constructs: 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
• Algorithms and problem-solving: Problem-solving strategies; the role of algorithms in the problem-solving process; the concept and properties of algorithms
• Fundamental data structures: Primitive types; arrays; strings and string processing
• Recursion: The concept of recursion; recursive mathematical functions; divide-and-conquer strategies
• Basic algorithmic analysis: Big "O" notation; standard complexity classes
• Fundamental computing algorithms: Simple numerical algorithms; sequential and binary search algorithms; quadratic and O(n log n) sorting algorithms
• Basic computability: Finite-state machines; Turing machines; tractable and intractable problems; uncomputable functions; the halting problem; implications of uncomputability
• Overview of programming languages: History of programming languages
• Digital logic and digital systems: Overview and history of computer architecture; fundamental building blocks; logic expressions
• History of computing
• Introduction to the social implications of computing

Units covered:

DS1	Functions, relations, and sets	4	core hours (of 6)
DS2	Basic logic	5	core hours (of 10)
DS3	Proof techniques	4	core hours (of 12)
DS4	Basics of counting	3	core hours (of 5)
DS6	Discrete probability	3	core hours (of 6)
PF1	Fundamental programming constructs	3	core hours (of 9)
PF2	Algorithms and problem-solving	2	core hours (of 6)
PF3	Fundamental data structures	2	core hours (of 14)
PF4	Recursion	2	core hours (of 5)
AL1	Basic algorithmic analysis	1	core hour (of 4)
AL3	Fundamental computing algorithms	2	core hours (of 12)
AL5	Basic computability	3	core hours (of 6)
AR1	Digital logic and digital systems	2	core hours (of 6)
PL1	Overview of programming languages	1	core hour (of 2)
PL4	Declarations and types	1	core hour (of 3)
SP1	History of computing	1	core hour
SP2	Social context of computing	1	core hour (of 3)

Notes:
This course is the first of a three-semester sequence (CS101B-102B-103B) that seeks to offer a broad, integrated introduction to computer science, along the lines advocated by the 1989 "Computing as a Discipline" report [Denning89] and Computing Curricula 1991 [Tucker91]. Each of the three courses in the sequence includes theory along with programming, and a range of additional topics are introduced in each course in the sequence.

As we note in Chapter 7, the breadth-first model has not enjoyed the success that its proponents had envisioned. We believe, however, that part of the problem may have come from trying to fit all these topics into too small a space. Given the expansion of prorgamming-related material that must be covered in the introductory sequence, there simply isn't time to cover the broader concepts of the discipline at any depth in the confines of the traditional two-semester sequence. As a result, most breadth-first courses that exist today seem to be lead-ins to a more traditional programming sequence. This model, which has several successful implementations, is outlined in the syllabus for CS100B.

In the last few years, however, the two-semester introductory sequence has become cramped even for the programming material. As a result, several institutions are moving toward a three-semester introductory sequence. We endorse these efforts in section 7.7.3 and offer a sample implementation in CS100B. The interesting question that this move toward three-semester sequences brings up is whether the additional time makes a breadth-first approach more viable.

The material presented in the CS101B-102B-103B sequence is quite similar to that offered in any of the traditional two-semester introductions and the CS115 discrete structures class. The difference is the ordering of the material. In the breadth-first sequence, mathematics is distributed throughout all three semesters and is more directly coupled to the topics that use it. In this way, students will have a greater opportunity to appreciate the connections between theory and practice.

A major danger of all breadth-first approaches lies in the fact that students tend to be far more attracted by the programming material, which they see as exciting and empowering, than they are to the more theoretical material. In this treatment, we have taken care to include more programming in the first course than has sometimes been true of breadth-first introductions. In the count of units, a third of the material in CS101B is directly related to programming and much of the rest can be presented so as to emphasize its practical importance.

We recognize that this approach has not been tested and that it may therefore suffer from the same modes of failure that plagued the earlier breadth-first attempts. We believe, however, that the expansion to three semesters may help to address these problems. After all, three-semester sequences -- a breadth-first preliminary course followed by a two-semester programming sequence -- do exist and seem to be reasonably successful. The advantage of the more integrated design is that students will be exposed to more programming in the first course and more theory in the courses that follow.

Online resources for CS101B