CPS 6, Ramm - Spring 2000 - 4/24/00, #38
- Announce
- Final, Thursday, 5/4, 9:00am, "here"
- Review Today
R E V I E W (Outline below since last test)
- Chap 10. Recursion, Lists, & Matrices
- Towers of Hanoi
- Recursion vs Iteration
- What's Going on With the Fibonacci Recursion?
- Scope & Lifetime
- Initialization, Shadowing, Scope Resolution Operator
- Normal (automatic), Global, Static
- Dynamic (new, delete)
- Two Dimensional Arrays
- Matrix Class
- Definition Syntax, Creation and Use, Initialization
- A Character Plotting Program
- Enumerated Types - Syntax
- enum identifier {value,
..., value};
- The Coin Class
- Combine Use of Matrices and Recursion
- The Blob Count Problem
- Example: Recursive Solution to Fill Problem
- Operator Overloading
- Set meaning of traditional operators with new types
- Operator Overloading as a Free Function
- Operator Overloading as Part of a Class
- 11. Sorting, Templates, and Generic Programming
- Sorting
- Selection Sort
- Loop Invariant & Complexity
- Function Overloading
- Function Templates
- Other Simple Sorts
- Insertion Sort & Bubble Sort (XXX)
- Quicksort
- Analysis of Sorts
- O (big-Oh) Notation to Describe Complexity
- Other Sophisticated, Fast Sorts
- Mostly to expose you to the names
- Merge Sort, Heap Sort, Binary Tree Sort
- All O(N log N)
- Other Simple Sorts
- Insertion Sort, Bubble Sort (XXX)
- All O(N^2)
- Sorting Complex Objects
- What Are Some Other big-Ohs?
- Can O(...) be so Large as to make answer Impossible?
- Towers of Hanoi, Computer Chess
- Noncomputability: Can Solutions to Everything be Programmed?
- Programs that Read Programs
- Trying to Solve the Halting Problem
- Proofs by Contradiction (Indirect Proof)
- Assume Existence of Function
halts():
- Now write function: void contrary()
- Leads to contradiction
- Whole classes of programs on program behavior are non-computable.
- Existence of Noncomputable Functions
- Approach: Matching up Programs and Functions
- Have: Uncountable Infinity of Functions Mapping int To int
- All Programs Can be Ordered
- Try to Draw Lines Between Functions and Programs
- (Hard to identify function that computer can't produce)
- 12. Dynamic Data, List, & Class Templates
- Motivation for Pointers
- Pointer Definition Syntax
- Pointer uses (conceptual)
- Tag Sorts, Sort list by more than one key
- Pointers as Parameters
- The
new Operator
- The Selector Operator
->
- Implementing a Tag Sort
- Linked Lists
- The Null Pointer
- The Stack
- Delete
- Compare to Vector (sequential) Implementations
- Constructors Revisited
- The Destructor Member Function
- Inheritance
- What is it?
- Motivating Simple Example
- Base Class Syntax
- Derived Class Syntax
- Overriding Member Functions
- The Payoff