CS 136: Designing Object-Oriented Programs

Here is a possible description of the course. It is to be used more as an aid to understanding the content than an actual schedule; any given lecture may contain too much or not enough material. Later lectures correspond quite closely to lectures in CS 134, albeit in a slightly different order. Close correspondences and relationships are noted in italics.

Week 1

• Lecture 1: Introduction to Java: Primitive types and strong typing. Objects and classes. Class definition: fields, constructors, methods. Interpretation and compilation. The main method.
• Lecture 2: Selector, accessor, and mutator methods. Information hiding. Parameter passing.

Week 2

• Lecture 3: Aspects of imperative languages: assignment, conditionals, loops.
• Lecture 4: Imperative programming. Local variables. Strings.

Week 3

• Lecture 5: Object interaction, abstraction in software. Object diagrams. Internal and external methods and variable references. "this".
• Lecture 6: Debuggers for visualization and tracing. Console and file I/O. Testing.

Week 4

• Lecture 7: The memory model. Java (fixed size) arrays. Iterating through an array.
• Lecture 8: ArrayList and Vector. Implementing partially filled arrays. 2-d arrays.

Week 5

• Lecture 9: Class hierarchies. Inheritance.
• Lecture 10: Class design. Responsibility-driven design.

Week 6

• Lecture 11: Abstract data types. Language features that support ADTs. Interfaces and abstract classes. Related to Lecture 3 in CS134.
• Lecture 12: Set and Table ADTs. Implementations using arrays. Related to Lecture 16 in CS134.

Week 7

• Lecture 13: Linked lists in Java. Assessing the efficiency of implementations. Implementing Set and Table using linked lists. Related to Lecture 13 in CS134.
• Lecture 14: Algorithm analysis: asymptotic notation. Corresponds to Lecture 17 in CS134.

Week 8

• Lecture 15: Techniques for analyzing iterative and recursive programs. Assertions. Program correctness.
• Lecture 16: Linear and Binary search in arrays. Analysis. Corresponds to Lecture 18 in CS134.

Week 9

• Lecture 17: Iterative sorting algorithms (selection and insertion) and their analyses. Corresponds to Lecture 21 in CS134.
• Lecture 18: Mergesort and quicksort in Java. Asymptotic analysis. Related to Lectures 22 and 23 in CS134. They have seen the algorithms in CS135, so the focus will be on the Java implementation and the analysis.

Week 10

• Lecture 19: Stack ADT: definitions, properties, implementations, applications. Corresponds to Lecture 8 in CS134.
• Lecture 20: Queue ADT: definitions, properties, implementations (iterative and recursive), applications. Corresponds to Lecture 9 in CS134.

Week 11

• Lecture 21: Discrete event simulation (largish example using queues). Corresponds to Lecture 10 in CS134.
• Lecture 22: Binary trees in Java. Implementation and analysis. Related to Lecture 11 in CS134, but they have seen trees in Scheme.

Week 12

• Lecture 23: Tree traversal and applications. Corresponds to Lecture 14 in CS134.
• Lecture 24: Computer science as a profession. New material into CS134 and CS136.

Week 13

• Lecture 25: History of the concepts covered in this course.