CS103B. Principles of Object-Oriented Design

Prerequisites: CS103B

Syllabus:

• Discrete mathematics: functions, relations, and sets; proof techniques; solving recurrence relations; mathematical properties of graphs and trees; discrete probability
• Fundamental programming constructs: Iterators and iteration models; recursion in data structures
• Fundamental data structures: Implementation strategies for stacks, queues, hash tables, graphs, and trees; strategies for choosing the right data structure
• Using APIs: API programming; class browsers and related tools; programming by example; debugging in the API environment; introduction to component-based computing
• Algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; identifying differences among best, average, and worst case behaviors; little "o," omega, and theta notation; empirical measurements of performance; time and space tradeoffs in algorithms; using recurrence relations to analyze recursive algorithms
• Fundamental computing algorithms: Binary search trees; representations of graphs; depth- and breadth-first traversals; shortest-path algorithms; transitive closure; minimum spanning tree; topological sort
• Introduction to language translation: Comparison of interpreters and compilers; language translation phases; machine-dependent and machine-independent aspects of translation; parsing strategies
• Object-oriented programming: Object-oriented design; encapsulation and information-hiding; separation of behavior and implementation; collection classes and iteration protocols; internal representations of objects and method tables
• Overview of operating systems: Role and purpose of the operating system; history of operating system development; functionality of a typical operating system
• Fundamental issues in intelligent systems: History of artificial intelligence; philosophical questions; fundamental definitions; philosophical questions; modeling the world; the role of heuristics
• Software engineering: Software design; object-oriented analysis and design; design for reuse; design patterns; programming environments; testing tools

Units covered:

DS1	Functions, relations, and sets	2	core hours (of 6)
DS3	Proof techniques	3	core hours (of 12)
DS4	Basics of counting	2	core hours (of 5)
DS5	Graphs and trees	2	core hours (of 4)
DS6	Discrete probability	3	core hours (of 6)
PF1	Fundamental programming constructs	1	core hour (of 9)
PF3	Fundamental data structures	6	core hours (of 14)
PF4	Recursion	3	core hours (of 5)
OS1	Overview of operating systems	1	core hour (of 2)
AL1	Basic algorithmic analysis	1	core hour (of 4)
AL3	Fundamental computing algorithms	3	core hours (of 12)
PL3	Introduction to language translation	2	core hours
PL5	Abstraction mechanisms	1	core hour (of 3)
PL6	Object-oriented programming	4	core hours (of 10)
IS1	Fundamental issues in intelligent systems	1	core hour
SE1	Software design	2	core hours (of 8)
SE2	Using APIs	2	core hours (of 5)
SE3	Software tools and environments	1	core hour (of 3)

Notes:
This course is the third of a three-semester sequence (CS101B-102B-103B) that seeks to offer a broad, integrated introduction to computer science. The rationale for the design of the sequence and suggestions for its implementation are given in the notes to CS101B.

Online resources for CS103B