CS112I. Data Abstraction
Continues the introduction of programming begun in CS111I, with a particular focus on the ideas of data abstraction and object-oriented programming. Topics include recursion, programming paradigms, principles of language design, virtual machines, object-oriented programming, fundamental data structures, and an introduction to language translation.
Prerequisites: CS111I; discrete mathematics at the level of CS105 is also desirable.
Syllabus:
- Review of elementary programming
- Recursion: The concept of recursion; recursive specification of mathematical functions (such as factorial and Fibonacci); simple recursive procedures (Towers of Hanoi, permutations, fractal patterns); divide-and-conquer strategies; recursive backtracking; implementation of recursion
- Introduction to computational complexity: Asymptotic analysis of upper and average complexity bounds; big-O notation; standard complexity classes; empirical measurements of performance
- Fundamental computing algorithms: O(N log N) sorting algorithms (Quicksort, heapsort, mergesort); hashing, including collision-avoidance strategies; binary search trees
- Programming languages: History of programming languages; brief survey of programming paradigms (procedural, object-oriented, functional)
- Fundamental issues in language design: General principles of language design, design goals, typing regimes, data structure models, control structure models, abstraction mechanisms
- Virtual machines: The concept of a virtual machine, hierarchy of virtual machines, intermediate languages
- Object-oriented programming: Object-oriented design; encapsulation and information-hiding; separation of behavior and implementation; classes, subclasses, and inheritance; polymorphism; class hierarchies; collection classes and iteration protocols; fundamental design patterns
- Fundamental data structures: Linked structures; implementation strategies for stacks, queues, hash tables, graphs, and trees; strategies for choosing data structures
- Introduction to language translation: Comparison of interpreters and compilers; language translation phases (lexical analysis, parsing, code generation, optimization); machine-dependent and machine-independent aspects of translation
Units covered:
| DS5 | Graphs and trees | 2 | core hours (of 4) |
| PF3 | Fundamental data structures | 6 | core hours (of 14) |
| PF4 | Recursion | 5 | core hours |
| AL1 | Basic algorithmic analysis | 2 | core hours (of 4) |
| AL3 | Fundamental computing algorithms | 4 | core hours (of 12) |
| PL1 | Overview of programming languages | 1 | core hour (of 2) |
| PL2 | Virtual machines | 1 | core hour |
| PL3 | Introduction to language translation | 2 | core hours |
| PL4 | Declarations and types | 2 | core hours (of 3) |
| PL5 | Abstraction mechanisms | 1 | core hour (of 3) |
| PL6 | Object-oriented programming | 7 | core hours (of 10) |
| SE1 | Software design | 2 | core hours (of 8) |
| SE2 | Using APIs | 2 | core hours (of 5) |
| SE3 | Software tools and environments | 2 | core hours (of 3) |
| | Elective topics | 1 | hour |
Notes:
As noted in the description of the CS111I prerequisite, there is no guarantee that students coming into this course will have used an object-oriented language. In any event, the courses in the imperative-first track assume that the introductory course -- even if it happens to use an object-oriented language -- concentrates on the imperative components of that language rather than any object-oriented mechanisms. (For an object-oriented implementation of the introductory curriculum, see the CS111O/CS112O sequence.) One of the main goals of CS112I is to introduce the object-oriented paradigm and give students experience using it. The other major topics are recursion, data structures, and the core units in the Programming Languages area (PL), which fit appropriately into this course.
Online resources for CS112I