defines a set of common atributes and methods

defined with either generality or specificity

Ex dog

• color

• name

• breed

• wag

• bark

• eat

Contain fields with represent state

method define interactions

main method is not required. Only if it is the entry point for an application.

write a class for cars or bicycle

• define a vehicle class

  • Color

  • number of doors

  • wheel count

  • move and stop methods

  • constructors

• from that, subclass for cars and bicycles

project contains a package, includes classes, subclasses and other such things.

• private

• protected

• public

Classes should have accessors and Mutators.

• allows limited access to instance variables, prevents things from being messed up too much.

• allows a way to ensure that information stays consistent.

this is used to refer to the instance of the class.

don't forget about final, it prevents something from being changed.

Static on a method means that you don't need an object to actually call it.

static dispatch is when the correct method can be determined at compile time.

Operator overloading allows you to redefine built-in operators for different types of operands

• • works for string concatenation and for arithmetic with numbers

• • would work for union in arrays and graphs

• • could meen time arithmetic for date-time/interval types

• This should often be avoided.

  • because of various meanings this can become ambiguous, unclear or open to interpretation.

  • all compinations of operands must be thought of.

  • Don't do this. Java doesn't actually support this, butsome operators are implemented with basic polymorphism.

• Method overriding

  • changes something in a fundamentally different way.

  • this changes the definition of an inherited method.

  • A virtual function can be overridden. In java, all non-private functions are virtual by default. The keyword final can be used to make it non-virtual.

• overloading changes the type or number of parameters for a method belonging to the same class.

• overriding changes the implementation within a subclass

• binding:

  • the association between method definition and method call.

  • takes place at either compile or run time.

  • compile time

    • static binding

    • early binding

    • static dispatch

    • static polymorphism

  • run time

    • dynamic binding

    • late binding

    • dynamic dispatch

    • dynamic polymorphism

  • static, private and final methods are always bound at compile time

  • dynamic binding means that things must be bound at runtime, as the compile can get confused

• Type coerction is a form of type conversion.

  • covariant (ostrich to bird)

  • contravariant (ostrich to bird)

  • invariant (robin to ostrich)

• Universal polymporphism: handling types universally

  • inclusion

    • replacing the supertype's instance with a subtype's instance.

    • based on liskov substiution

    • happens at runtime

    • this is covariant

    • Behavioral subtyping

      • No new methods, invariants are guaranteed.

Inclusion/Subtype polymorphism

• replaces parent class with child class

• benefit is less coding.

• toString() can be re-used by subclass objects, is a static method.

Parametric polymorphism:

• A general broad type. works for any type.

• Allows you to choose which type is used.

• The weird angle bracket notation.

• <T> is the generic type. Where T is any uppercase letter. "T" is used by convention

    public static <T> void printList(Lint<T> aList) {
        for(T anElement: aList)
            System.out.println(anElement);
    }

• Examples include:

  • container class

  • print method

  • getMax method

  • Sorting Methods

• Bounded parametric Polymorphism:

  • there is a way to restrict datatypes.

• Recursion!

  • Using this or super

  • this, self, Me

  • super for the superclass.

  • association

    • knows about another object

    • can call methods, interact with it.

    • created and destroyed indepentently

Java is not a pure OO language.

• has primitive types.

OO requires practice

OO in java is classed based.

js uses prototype oo.

• cloning

• prototyping

• constructed from nothing.

Java has a final, super-super-super-*class, object.

• this allows you to inherit common behaviors.

  • clone

  • equals

  • finalize

  • getClass

  • hashCode

  • toString

Lifecycle

• Instantiation

  • new ObjectName()

  • multiple constructors allowed.

  • this() and super()

  • Inner classes. Can be public, private or protected.

  • Anonymous inline classes are allowed (comparator for collection's sort method).

• Encapsulation

  • Access Modifiers:

    • private

    • protected

    • public

    • static

• Inheritance

  • hierarchical design

  • avoid duplication and reduce redundancy.

  • final can be used to prevent inheritance.

  • use super. to call the superclass' methods, constructors and access variables.

  • If a subclass overrides, it can still call the superclass definition.

  • Subclasses do not inherit constructors of superclasses.

  • Single Vs Multiple Inheritance.

    • No multiple inheritance (no punnet squares)

    • Allows for more than one direct superclass (diamond inheritance problem)

  • is-a relationship

• Reuse with composition:

  • point is used to define line.

  • classes can have a class as a member (no, really)

  • composition is has-a relationship

Make sure to include useful methods.

when in doubt, override

abstract methods

abstract classes

interfaces

an abstract method has only the signature, use abstract to denote the fact that it truly is abstract.

an abstract class is a class that has one or more abstract methods. again, use abstract

you cannot create instances of an abstract class.

you must override abstract methods in the subclass

interfaces allow for clean upcasting thanks to the Liskov Substitution Principle

interfaces are different from a superclass. It has no attributes, but it does have method signatures.

use implements for interfaces.

all methods in an interface must be overridden.

interfaces are not classes.

they provide a contract for what classes can do.

they do not specify how the classes will do it.

named as adjectives, initial camel-case

you can implement multiple interfaces, but this is not multiple inheritance!!!!!!

interfaces define common behaviors, an API

Java supports different types of polymorphism

no operator overloading.

no behavioral polymorphism (no strict inheritance)

method overloading

method overriding

@Override annotation

covariant return types in method overriding

Overload methods:

• methods with the nsame name but a different lambda-list

• the compiler calls the appropriate method.

• no different return types

Overriding

• in public, non-final classes

• you should use the @Override annotation

• can change the return type (but must be covariant) or lambda-list

• the annotation ask s the compiler to make sure that this method can be overridden, used only by the compiler.

be careful with substitutability

upcasting is implied and always safe.

downcasting requires explicit type casting. Circle aCircle = new Cylinder(); Cylinder newCylinder = (Cylinder)aCircle; This is not always safe!

• can raise ClassCastException

• an Integer cannot become a String

intanceof operator, object instanceof Type

parametric polymorphism

• java generics!

• What makes your life in programming difficult?

  • Bugs

  • OO-Imperitve impedance mismatch

  • OO-Relational impedance mismatch

  • Java itself

• Reducing bugs in an application:

  • reduce pervasiveness

  • compile-time bugs are detected by the compiler.

  • runtime bugs cannot be detected on the surface.

• generics can add stability by making more bugs detectable at compile time

• generics allow types to be parameters.

  • this is a type of type-safety, and quite an ugly implementation at that.

  • introduced in JDK 1.5

  • This uses the <Type, ...> syntax.

  • also known as parameterized types.

  • Make sure to use single, majescule letters for a Type in a generic.

Approach

• add functionality to classes

• design new classes

• Understand the problem in english (or greek, or esperanto, or spanish or whatever…)

• Do hand computation (NOOOOO!!!!!)

two techniques

• clone

• copy constructors

cloning

• takes an exact copy, has similar state as the original object

• the clone method in the Object class

• this is by default a field-by-field copy

• does not create copy of reference objects in the cloned objects fields

• to correctly support, implement clonable interface and override clone method

• the clone method can be overridden to implement deep cloning

copy constructors

• A constructor that takes an object of the type that it is a constructor for.

• Again, by default, a shallow copy

a program doesn't run for long.

we use files to store our data.

this is not a good technique for many problem domains

why is a database more appropriate choice?

• structured data

• can allow for much more efficient storage as certain things do not need to be repeated

• there do exists advanced forms of ACLs

• reduces redundancy

• aggregation requires more processing

• data is related in some way

a database should have implicit meanings from the relationships between data.

Thanks Ted Codd!

represents some aspects of the real world, the miniworld or the Universe of Discourse

changes are reflected in the database

databases should be logically coherent in their collection of data.

they are designed, built and populated for a specific purpose.

keep the different types of users in mind.

the views of different groups are integrated during database design.

data should only be stored in only one place.

SQL is the Structured Query Language, a special purpose language used to query, define, and manipulate data in databases. (David Chamberlin and Raymond Boyce)

Special Purpose language

often called "sequel"

Thanks to David Chamberlin and Raymond Boyce.

SQL is a part of the DBMS

SQL uses the terms table, row and column for relation, tuple and attribute respectively.

Data Definition is done using the CREATE statements

A Review of SQL syntax and some basic sequences.

Relations are maintained with foreign keys.

Remember that referential integrity is important.

you can use triggers and cascade to insure that referential integrity is maintained.

ON DELETE CASCADE is what you use to remove referencing records.

compound queries with AND and OR in WHERE

LIKE performs partial matching % is the wildcard

IN lets you select for certain values within a given set. (this is particularly useful with CTEs).

ORDER BY ensures that things are in a particular order, allows for ordering on multiple columns.

Don't forget about Common Table Expressions

Aggregation in SQL:

COUNT

Number of rows in a query, can be specified as being unique

SUM

Total of a certain column

MAX

Maximum in a given column

MIN

Minimum in a given column

AVG

Average in a given column

FIRST

First row.

LAST

Last row.

The HAVING clause can be used for filtering

SELECT author, SUM(num_copies) AS quantity FROM Library GROUP BY author HAVING quantity < 20;

Joins combine records from two or more tables.

Inner Join

There is a match between the two columns in both tables. The same as a plain join. SELECT columns FROM tableA INNER JOIN tableB ON a = b;

Left Outer Join

Records in table 1 with matching rows from table 2, NULL values uesd to replace non-existent values.

Right Outer Join

Records from table 2 with matching rows from table 1, with null values used to replace non-existent values.

Full Outer Join

Get everything from table 1 and table 2 (not supported by mysql, use union all)

DISTINCT gets the unique values

Indexes can be used to help ensure that data can be searched efficiently. PKs are indexed by default

• Very similar to the index in the back of a book.

• can slow down insertion/updates

• CREATE INDEX name ON table(column)

From Lecture 0 to lecture 15

Must bring number 2 pencils

identify all entities in different tables.

What defines an entity will define columns and types.

almost every table should have a primary key.

relations between tables are to be identified and are defined by using foreign keys

remember to use integers for primary keys by using autoincrement (not always the best thing to do)

remeber to be consistent in naming conventions

foreign keys implement the relationships

• one-to-one (this is rarely used, and often this should just be one table)

• one-to-many (one author to many books)

• many-to-one (there are many books for one author) (or one book has many authors)

• many-to-many (requires a join table) (this is done using a mapping table)

JDBC provides an API and library for accessing relational databases with the same java syntax.

JDBC is not an acronym

provides a standard Java API dor rdbms connectivity.

make sure to have the correct db-specific drivers.

Provides the following interfaces and classes:

• DriverManager – matches connection requests and matches to the correct driver. class.

• Driver – manages communication with db server. interface.

• Connection – provides methods for contacting db. interface.

• Statement – submits sql statements to the db. interface.

• ResultSet – iterator class to hold data retrieved from db.

• SQLException – handle errors that occur in the application. class.

building the application

• import packages

    import java.sql.*;

• initialize driver

    Class.forName("com.mysql.jdbc.Driver");

  • Jar just needs to be in the build path

  • Register with the above source code block.

• create connection

    Connection conn = DriverManager.getConnection(URL, username, password);

• execute queries

    Statement stmt = conn.CreateStatement();

  • Statement

  • PreparedStatement

  • CallableStatement

• extract data

    ResultSet rs = stmt.executeQuery("query text");

  • executeUpdate is used for update, insert and delete.

• clean up the environment

create connection

create statement

execute query

close all objects

executeQuery executes a normal query

executeUpdate executes an update/delete/insert/create

executeBatch executes a list of update queries and returns row-changed counts

preparedStatements allow you to supply arguments dynamically.

callableStatements are similar, but are used for things like stored procedures and sql functions

Use question marks for parameter markers. indexed from 1.

remember to use prepared or callable statements for security purposes.

follow best practices and close your resources!!

remember to log things! consider log4j

our collections will need to be dynamic.

while arrays are useful, the size cannot be changed

A better solution is needed, this is a List (linked, or otherwise)

• this requires an ADT (abstract data type) (set of objects and their operations (which are not necessarily defined))

  • core functionality

    • adding

    • retrieving

    • removing

    • automatic resizing

  • other functions

    • determine size and emptiness

    • iterate over elements

    • batch operations

  • then decide how you want to implement them

  • Start with arrays

    • this can be done by creating new arrays every time something is added/removed

generalization

• use java generics

• remember to type cast when using generics

use of arrays requires resizing and this is very expensive. This is $O(n)$

there are then, linked lists

• only reference to head and possibly tail. however, each node knows the next.

• no fixed size and no resize

• nodes have data object and pointer to next node

• find place to insert item, between a and b.

• to retrieve objects at given index, you must iterate or recurse through the list

There is a common root class in java, Object

This provides a bunch of common methods

equals and hashCode must be overridden for collections libraries

when you override equals, be sure to override hashCode

Understand the use of a hashmap

relies on the equals method

the comparator class is used for the default sort function

comparable and comparator interfaces

there are some default comparators.

• alphabetical order for strings

• descending order for integers

• chronological order for dates

objects implement the comparable interface if there is a natural order

implement the comparable interface, and implement the compareTo method

returns integers: -1 for before, 0 for same, 1 for after

implements Comparable<ClassNameHere>

• requires that you implement the compareTo(Object) method

An alternative is the Comparator interface.

• This encapsulates orderin

• has a single method, compare

• A user defined class implements the interface

• implements Comparator<ClassNameHere>

• And over ride compare

• Can be done with anonymous classes/objects

• You don't implement this on the data class.

Anonymous inner classes are useful for comparators

• these are classes that are defined in-line

we use computers for handling large amounts of data quickly

our programs should terminate within a reasonable amount of time

This is the study of performance (Big O?)

we have to be able to choose algorithms effectively, this is based on various paramaters

• time

• number of iterations

• memory

many factors can go into this, including language and methodology. These can often times be safely ignored.

we must instead choose our algorithms carefully.

algorithms are a precise sequence of steps used to solve a problem.

• these must be unambiguous

• correct

• finite (that is to say, they must halt)

an algorithm is a feasible solution if it is efficient

• this includes time and memory

algorithms are traditionally expressed using psuedocode

• good psuedocode has the following properties

  • balances clarity and detail

  • abstract the algorithm

  • uses correct mathematical notation

  • is easy to read

• poor pseudocode

  • gives too many details

  • is implementation or language specific

Algorithmic design

1. Understand the problem

2. choose your approach

3. choose the appropriate data structure

4. choose your strategy

5. prove the correctness of the algorithm

6. evaluate complexit

7. test it

Algorithmic analysis

1. running time (depends on)

   • processor

   • read/write speed

   • 32/64 bit

   • input size – primary issue

Remember to use Bachmann-Landou notation

• $n$ is linear

• $n^2$ is quadratic

• $n^3$ is cubic

• $\log n$ is logarithmic

• $c^n$ is exponential

• $n!$ is factorial

• $c$ is constant

we will only ever look at time efficiency

remember that running time is a function of input size

we study the growth rate of the running-time of the function when input goes towards infinity. This is the asymptotic behavior.

We use for this Bachmann-Landau notation, "Big-O"

we consider on ly the leading term, ignoring the leading constant

Bachmann-Landau Notation:

$O(c)$

Constant

$O(\log n)$

Logarithmic

$O(\log^2 n)$

Log-squared

$O(n)$

linear

$O(\log^* n)$

Log-star/iterated logarithmic

$O(n^2)$

quadratic

$O(n^3)$

cubic

$O(c^n)$

exponential

Converting from $f(n)$ to Bachmann-Landau

• we find the function $g(n)$ that is an upper bound

• thus, $f(n) = O(g(n))$

Big $\Omega$ is used to find a lower bound

• we find the function $g(n)$ that is the lower bound

• thus $f(n) = \Omega(g(n))$

Big $\Theta$ is used for the tight bound.

• find a function $g(n)$ such that $c_1$ and $c_2$ grow as fast as $f(n)$

• $f(n) = \Theta(g(n))$

Big O is used to estimate the number of operations an algorithm uses as its input grows

we can use big O to compare grown of a function

we assume in Big O that all operations have the same cost

in general, we:

1. identify input

2. identify input size

3. identify elementary operations

4. determine how many times elementary operations get executed with respect to tlhe input size.

5. characterize using big-O

characterizing algorithms from running time functions

given a sorting algorithm that takes 0.5 μsec for an input size of 100.

• how long will it take for a n input size n = 1000000 if the running time is expressed as the following functions

Consider the function $f(x) = x^2 + 2x$

• $3x^2$

• this function is $O(n^2)$

Show that $f(x) = x^2 + 2x + 1$ is $O(x^2)$

• find $g(x)$ such that $f(x) \leq cg(x)$

• we see that the upper bound is $4x^2$, thus, this function is $O(x^2)$

Recursion (n): see Recursion

recursion allows us to break something down into smaller problems by repeatedly reducing the size of a problem

these are typically very simple

remember to have at least one base case

be careful of the difference of head and tail recursion

• head recursion

    (defun head-integer-sum (n)
      (if (= 1 n)
          1
          (+ n (head-integer-sum (1- n)))))

• tail recursion

    (defun tail-integer-sum (n total)
      (if (= n 0)
          total
          (tail-integer-sum (1- n) (+ total n)))

  • this can be rewritten to iteration

fibonacci

  (defun fibonacci-head (n)
    (cond
      ((= n 0)
       0)
      ((= n 1)
       1)
      (t
       (+ (fibonacci-head (1- n))
          (fibonacci-head (- n 2))))))

  (defun tail-fib-internal (d n1 n2 n)
    (if (= n d)
        (+ n1 n2)
        (tail-fib-internal (1+ d) n2 (+ n1 n2) n)))

  (defun fibonacci-tail (n)
    (cond
      ((= n 0)
       0)
      ((= n 1)
       1)
      (t
       (tail-fib-internal 2 0 1 n))))

the bad

• can be more code

• can cause problem with the stack (good compilers can recognize certain patterns and optimize (I'm looking at you lisp!))

the good

• not different in complexity

• better for some problems

Big o is about finding the upper bound of the running time function

upper bound analysis is used to determine how efficient and how appropriate a given algorithm is

always look for the closest upper bound of a running time function.

remember that big-O uses some standard functions, and does not describe a function perfectly

constants $C$ and $k$ are refered to as witnesses to the relationship $f(n)$ is $O(g(n))$

Always find the constants such that when $x > k$, $f(x) \leq g(x)$

there can be many pairs of witnesses

Show that $7x^2$ is $O(x^3)$:

• form a table for a few values, from 1 to $n$

• find what number $x$ must be greater than, this is $k$.

• remember that this is not necessarily the other way around

Use big-O to describe the growth rate of the factorial function

• $O(n^n)$

remember that intuition can often be used

when you have obviously multi-part functions, find big-O seperately, and take the max for addition, if product, take the product

selection sort

• iterate through the elements and find the minimal element, swapping that with the first. continue with the list length being equal to n-1

• is $O(n^2)$

insertion sort

• insert each element into the correct place.

• is $O(n^2)$

quicksort

• recursive, partition-exchange based

• is $O(n^2)$ worst-case, but $O(n \log n)$

first, if possible, analyze the iterative version of the algorithm.

remember that function call cost is defined recursively, such that the cost is a constant cost + the cost of the call for the next smaller call

• $T(n) = C + T(n - 1)$

• $T(0) = 1$

Binary search is $O(\log n)$

Merge Sort is $T(n) = 2T(\frac{n}{2}) + n$

three steps

1. Set up a recurrence relation for the solution

2. Solve the recurrence relation

3. analyze the complexity of the solution using big-O notation

Asymptotic behavior is discussed using the Master Theorem

• $$T(n) = aT\left(\frac{n}{b}\right)+ f(n), a > 0, b > 1$$

• $n$ is the size of the problem

• $a$ is the number of subproblems

• $\frac{n}{b}$ is the size of each subproblem

• $f(n)$ is the non-recursive cost

• Theorem: Let $T(n)$ be a monotonically increasing function that satisfies $$ T(n) = aT\left(\frac{n}{b}\right) + f(n), T(1) = c $$ Where $a \geq 1, b \geq 2, c > 0$. If $f(n) \in O(n^d)$ where $d \geq 0$, then: $$ T(n) = \left\{ \begin{array}{ll} O(n^d) & a < b^d \\ O(n^d\log n) & a = b^d \\ O(n^{\log_b a}) & a > b^d \\ \end{array}\right. $$

always add on the top of the list.

singly-linked lists are particularly useful as stacks

can be implemented however with an array, but this is technically a stack, with a linked-list being the most useful

stacks are last-in-first-out

stacks are used for backtracking, undo, with language processing and supporting recursion

queues are first-in-first-out, and also are best implemented with linked lists.

priority queues have a priority attached to each item.

stacks are used for the consumer-producer pattern, which is often used for asynchronous behavior (see the ppr)

Explore the nodes closest to you first, top to botom, left to right

trees are useful for searching

you can use a binary search tree

there are certain operations for trees, binary-trees can allow for this easily

understand both insertion, deletion and search.

remember, you can use breadth-first representation for trees in arrays.

you can also use pointers/containing nodes

trees are often used for the implementtation of priority queues

things like finidng the lowest cost product, the shortest duration of a flight

use a sorted tree for this

a priority queue is an ADT, not quite a queue, but instead based on some sort of priority

enqueue is based on priority (tree traversing insertion)

remember that a balanced 2-tree has $O(\log n)$ time

to maintain height balance, we use a heap

• 2-tree with the following properties

  • full/complete save the last row

  • full to the left on the last row

  • every node has either a greater or lesser value than both of the children

• it's not sorted, rather there is no definition of the relationship among the nodes descending from a node

• the max/min element is always the root

• these are used for a lot of algorithms:

  • heap sort

  • Prim's

  • Dijkstra's

  • Huffman Coding

• this is the optimal implementation of a p-queue

• Operations

  • Insertion

    • the priority item goes at the top of the tree.

    • preserve fullness and heap property

    • go to the last row and find the first free spot on the left

    • then use a heapifier/fix

      • compare with parent and swap, until correctly heapified

  • Removal

    • remove the priority item and replace with the next priority

    • replace root element with the last element in the heap (lowest, right most element)

    • redo-heapification:

      • compare with smallest child and swap

  • No arbitrary remove or find

  • All operations are $O(d) = O(\log n)$

Remember that you can use arrays for trees

remember that the algorithmic understanding is more important than knowing how to implement it in a specific language

remember to apply algorithmic complexity

Sorting is fundamental to data processing

algorithms are usually analyzed with regard to:

• comparison count in worst, best and average cases

• swap count

• whether or not extra memory may be required

most languages provide sorting functionality

know what type of ordered collections are supported by a language

be careful to consider multiple attributes when you sort

know the difference between satbel and unstable sort

Tuesday 1530, Hamilton 112

open book, open note