Contents

• 1. Introduction and Overview
  • 1.1 Scope
  • 1.2 Overview
  • 1.3 Reading
    • 1.3.1 Books
    • 1.3.2 Journals
  
  
• 2. Simple Algorithms and Review of Java
  • 2.1 Sequence
  • 2.2 Repetition
    • 2.2.1 Sequence of Repetitions
    • 2.2.2 Repetitions of Repetitions -- Nested
  • 2.3 Procedures -- Methods ...Functions
    • 2.3.1 Without Parameters
    • 2.3.2 Procedures with Parameters
  • 2.4 Selection
  • 2.5 Exercises
  
  
• 3. Introduction to Object-oriented Programming
  • 3.1 Software Engineering and its Requirements and Goals
  • 3.2 The Waterfall Life-cycle and Structured Systems Analysis and Design
  • 3.3 Shortcomings of Waterfall and Top-down Decomposition
  • 3.4 Key Application: Event-driven Interaction
  • 3.5 Cornerstones of Software Engineering and Object-oriented Systems
  • 3.6 Summary
  
  
• 4. Classes and Objects
  • 4.1 Introduction
  • 4.2 A Cell Class
    • 4.2.1 Informal Specification of the Class
    • 4.2.2 Class Cell
  • 4.3 Reference versus Value - Aliases
  • 4.4 A Time Class
    • 4.4.1 Informal Specification of the Class
    • 4.4.2 Class Time1
    • 4.4.3 A User Program
    • 4.4.4 Class Time2
    • 4.4.5 A User Program for Time2
    • 4.4.6 Class Time3
    • 4.4.7 A User Program for Time3
    • 4.4.8 Class Time
    • 4.4.9 A User Program for Time
  • 4.5 Time with a complete change of representation
    • 4.5.1 A User Program for the new Time
  • 4.6 Composition
  • 4.7 Types, Variables, Values
    • 4.7.1 Introduction
    • 4.7.2 Data Types
    • 4.7.3 Values
    • 4.7.4 Variables
    • 4.7.5 L-Values and Values
    • 4.7.6 Aliases
    • 4.7.7 Dangling References
    • 4.7.8 Uninitialized Pointers
    • 4.7.9 Garbage
  • 4.8 Scope of variables
  • 4.9 Heap memory management
    • 4.9.1 Introduction
    • 4.9.2 Garbage
  • 4.10 Lifetime of variables
    • 4.10.1 Lifetime of variables - summary
  • 4.11 Exercises
  
  
• 5. Inheritance, Polymorphism and Genericity
  • 5.1 Introduction
  • 5.2 Extending Cell using Inheritance
    • 5.2.1 Class RCell - Restorable Cell
    • 5.2.2 User Progam for Class RCell
  • 5.3 Use of protected in base class
    • 5.3.1 Protected base member - Class Cellp
    • 5.3.2 Class RCellp
  • 5.4 Summary of Scope Modifiers in Java Classes
  • 5.5 Late Binding and Polymorphism
    • 5.5.1 Late/Dynamic Binding
  • 5.6 Dynamic Typing, Late Binding and Polymorphism
  • 5.7 Inheritance versus Inclusion/Composition, is-a versus has-a
  • 5.8 Reuse - the Real Power of Inheritance & Late Binding
  • 5.9 Extension via Composition - an Example
  • 5.10 Interfaces and Multiple Inheritance
    • 5.10.1 Class ICell - Incrementable Cell
    • 5.10.2 Multiple Inheritance - Incrementable and Restorable?
    • 5.10.3 Interface
    • 5.10.4 Use of Interface in Data Structures and Algorithms
  • 5.11 Object - Superclass of all Classes
  • 5.12 Generic Classes
  • 5.13 Cloning
  • 5.14 Exercises
  
  
• 6. Arrays and Lists
  • 6.1 Introduction
  • 6.2 A List class
    • 6.2.1 Discussion - Choice of Implementation
  • 6.3 Searching
    • 6.3.1 Sequential Search
    • 6.3.2 Performance Measurement
    • 6.3.3 Binary Search
    • 6.3.4 Logarithms
  • 6.4 Exercises
  
  
• 7. Analysis of Algorithms
  • 7.1 The Big `O' Notation
  • 7.2 Estimating the Growth Rate of an Algorithm
    • 7.2.1 Simple Statements
    • 7.2.2 Decision
    • 7.2.3 Counting Loop
  • 7.3 Example, Maximum Subsequence Sum Problem
    • 7.3.1 Cubic Time Algorithm
    • 7.3.2 Quadratic Time Algorithm
    • 7.3.3 N log N Divide-and-Conquer Algorithm
    • 7.3.4 Linear Time Algorithm
  • 7.4 Exercises
  
  
• 8. Sorting
  • 8.1 Bubble-Sort
  • 8.2 Selection Sort
  • 8.3 Insertion Sort
  • 8.4 Comparison, Bubble, Selection, and Insertion Sorts
  • 8.5 Quicksort
  • 8.6 Exercises
  
  
• 9. Lists
  • 9.1 A Linked List
  • 9.2 Generic List with additional features
  • 9.3 Java Lists
  • 9.4 Exercises
  
  
• 10. Stacks and Queues
  • 10.1 Introduction
  • 10.2 A Queue Class
    • 10.2.1 Informal Specification of the Class
    • 10.2.2 Implementation of a Queue
    • 10.2.3 Exercising program for GQueue
  • 10.3 A Stack Class
    • 10.3.1 Informal Specification of the Class
    • 10.3.2 Implementation of a Generic Stack Class
    • 10.3.3 Exercising Program for GStack
  • 10.4 A Stack Application - Balancing Brackets
  • 10.5 Exercises
  
  
• 11. Correctness and Specification
  • 11.1 Introduction
  • 11.2 Syntactic Specification
  • 11.3 Semantic Specification
    • 11.3.1 Introduction
    • 11.3.2 Assertions
    • 11.3.3 Axiomatic Specification
    • 11.3.4 Pre- and Post-conditions
    • 11.3.5 Syntax - also Pre-conditions?
  • 11.4 Design-by-Contract
  • 11.5 Pre-conditions and Defensive Programming
  • 11.6 Exercises
  
  
• 12. Recursion
  • 12.1 Introduction
  • 12.2 Mathematical Induction
    • 12.2.1 Deduction versus Induction
  • 12.3 Recursive Algorithms
  • 12.4 Recursion in Compilers and Calculators
    • 12.4.1 Pre-fix, in-fix, post-fix
  • 12.5 Proving Termination of Recursive and Other Non-deterministic Algorithms
  • 12.6 Divide-and-Conquer
    • 12.6.1 Maximum of an Array
    • 12.6.2 Merge Sort
    • 12.6.3 Towers of Hanoi
    • 12.6.4 Drawing a Ruler
  • 12.7 Trees and Recursion
  • 12.8 Binary Trees
  • 12.9 Traversal of Trees
  • 12.10 Elimination of Recursion
  • 12.11 Exercises
  
  
• 13. Tree Data Structures
  • 13.1 Introduction
  • 13.2 Binary Tree Class
  • 13.3 Exercises
  
  
• Bibliography
• A. CSC721 Examination April 2000