Next:
1. Introduction and Overview
Up:
Algorithms and Data Structures
Previous:
Algorithms and Data Structures
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
jc 2005-11-16