CSC152 2005S, Class 56: The End 

Admin:
* Exam 3 due
* Goodbyes
* Extra credit for hearing Elizabeth in Sebring-Lewis at noon
* Extra credit for hearing David in Sebring-Lewis at 4ish
* Extra credit for hearing David in the Jazz Band saturday at 7:30 p.m. in S-L

Overview:
* What (I hope) you've learned in CS152

* Discussion of problem 1: Removing values from linear-probe hash tables
* Discussion of problem 2: Dynamic arrays
* Discussion of problem 3: Testing sorting
* Discussion of problem 4: Stability of sorts

What you've learned in CS152

The Java Programming Language
* Primitive types
* Arrays
* Classes
* Generics: Parameterized classes
* Control structures:
  * Method calls
  * Conditionals
  * Loops
* Exceptions
* Packages
* Various annoying nitty-gritty details
  * E.g., extension vs. implementation
    * Classes extend other classes
    * Classes implement interfaces
    * Interfaces extend other interfaces

Object-Oriented Programming:
* Encapsulation
  * Group data and methods that operate on those data
  * Protect data (and some methods) from "outsiders"
* Inheritance:
  * Automatically gain the methods and properties of another class.
  * May add new methods and properties (extension)
  * May override methods 
* Polymorphism:
  * Write one method that can be applied to multiple related data types (e.g., your testers)

General CS Skills:
* More practice programming
* Separation of interface and implementation
* Writing of pre/post for algorithms

Abstract Data Types:
* Key aspects: 
  * Purpose/Philophy
  * Applications
  * Methods
  * (Implementation)
* Common ADTs:
  * Arrays/Vectors
  * Linear Structures
    * Queues, Stacks, Priority queues
  * Lists
    * Simple
    * Sequenced
    * Sorted
  * Dictionaries
  * ...

Data Structures (Implementing ADTs)
* Common implementation technques:
  * Linked nodes
  * Arrays
* Strategies for implementing
  * Divide and conquer
* Lots of common DSs
  * Heaps
  * Search trees
  * Array-based implementations of most ADTs
  * Hash tables
  * ...

Algorithms
* Analysis (big O)
  * Primarily informal
* Design techniques
  * Divide and conquer
  * Dynamic programming
  * Greed
  * Randomization
* Key algorithms
  * Sorting
  * Searching

General Thinking/Academic Skills
* Ability to respond to questions that you have not necessarily had adequate preparation to consider
* ***** Correcting grammar and spelling
* Formal thought that is central to most of CS

"Moral Modeling"
* It is important to treat others as people and not just as objects
* Sympathy is good
* "There's more to life than CS"
* There's more to academic life than classes
* Make fun of people who are discourteous to you
* "Have fun"

* Discussion of problem 1: Removing values from linear-probe hash tables
* Discussion of problem 2: Dynamic arrays
* Discussion of problem 3: Testing sorting
* Discussion of problem 4: Stability of sorts

Stability of Sorts
* As written, Insertion, Selection, Merge, and Quicksort are all unstable
  * In insertion sort: When you insert the element, you should stop when you hit an *equal* or smaller element, rather than just a smaller element.
  * In selection sort: Make sure that you select the *first* small element, rather than the *last* small element
    * That's not enough.  Swapping makes it inherently unstable.
    * We could shift instead of swapping (slower, but stable)
    * We could insert a dummy value (slightly slower, also stable)
      * Must be out-of-place
  * In merge sort: Make sure that we always take from the first half when two things are equal.
  * In Quicksort: 
     Normal:
       * Find the pivot
       * Put the pivot at the front of the subarray
       * Partition the rest to smallerequal vs. larger
       * Swap the pivot to the border
       * Recurse
     Improved:
       * Pick a pivot
       * Find the *rightmost* equal element in the subarray; use that as a replacement pivot
       * Still sucks
       * Probably not easily fixable (in place)

Advance warning for the final:
* Make in-place Quicksort stable!
  * With some hints