# CSCE 156: Computer Science II

## Lecture 0

### Goals

• Data Structures
• Algorithms
• Complexity Analysis
• A little Java

The actual goals:

• Learn about some computational problem solving skills. (In freaking Java no less!)
• Become a smart and careful problem solver.
• Learn to do smart thinking.
• Learn to use new approaches, including OOP. (Perl OOP is better.)

1. Assume a problem related to data storage, retrieval and processing.
2. Three part plan:
• Solution Model
• OOP
• Data Structures
• Solution Analysis
• Algorithms and Complexity Analysis (Big O notation!)
• Data Storage
• Databases
• Relational (MySQL/JDBC)
• In Memory
3. Build it!

### Motivation

• I find it interesting and natural.
• The purpose is as follows: “This class is applicable to software engineering and development practices worldwide.”
• Learn
• Enjoy
• Create

### High-Level intro to OOP

• You are a “creator”, creating various types of objects.
• You enable, in various ways, the various objects to interact.
• Objects are reusable if a class is properly created.
• Inheritance! (Demonstrated with “Shaun the Sheep” characters.)
• Objects have the following properties:
• Attributes and Methods

### Java Vs PHP

• Java
• More general purpose
• A bit more complex for simple things.
• PHP
• Primarily server-side
• Much simpler compared to Java
• Both will be taught in the first 3 labs.
• Java is used for lab 4 on.
• Only the first assignmentt can be done en iether Java or PHP.

### Take a proper approach

There are 3 possible approaches, but be able to look at it from the level of complexity.

• Designer
• Coder
• Theoretician

There is Top Down, Bottom Up, or Middle Out.

Design questions will be asked first, things such as modeling, interactions and the like when using the bottom-up approach.

### Approximate Schedule

1-3
Java/PHP
3-6
OOP
7-8
DB Designe and SQL
9
DB connectivity
10

### Assignments

1
Individual. 3 basic programs in either language.
2-5
Group. Java based, written incrementally, and based on a project.
6
Individual. Written Mathematical problems.

Assignment Criteria:

• Applications will be themed.
• Each phase is graded based on correctness and design.
• AA Living Design Document will be maintained and updated in each phase of the main porojct
• Due 1 wee kprior to the assignment
• Each iteration is graded, feedback given
• Only the final iteration’s grade counts.
• Expected to follow IEEE template.

### Working in Pairs

• May discuss at a high-level, with other teams, but all work must be original
• Devolpment of “soft skills”:
• Communication
• Team work
• Conflict resolution
• Careful of parters mooching, flaking out and disappearing.
• You are responsible for both you and your partner.
• Labs are setup for pair programming.
• You will not be able to choose the other student.
• One will drive, the other will navigate.
• Navigator will be responsible for reading instructions and telling the driver what to do.
• Driver ill be in charge of keyboard.

### Check Blackboard Regularly

• Check Schedule
• Office hours, TAs and help sessions are listed.
• Materials will be posted
• Lab info will be available

### Resources

• Recommended Text: Data Structures # Problem Solving Using Java
• Lecture Slides
• Lab handouts
• Help Sessions
• Student Resource Center
• Office Hours

### Labs

• Weekly Labs
• Materials will be available at least 1 week prior to the lab meeting time.
• Labs start this Wednesday.
• TA must sign off on work sheet.
• Must be finished by end of scheduled lab time.

### Email

• Don’t Email from Blackboard
• Mention the actual Subject
• Include Name and NUID

## Lecture 1: Introduction to Java and PHP

### Java

#### What is Java?

• A programming language, but more
• Defined by Gosling, Joy and Steele.
• A platform (the JVM).
• The JVM is the Java Virtual Machine
• A Class Library providing GUI, data storage, processing, IO and networking.
• An OOP language. in which we will design classes and instantiate objects.

#### OOP

• A Class is a blueprint, which does not actually exist within the memory, rather exists as instances.
• Objects from the same class are similar, they share the same set of properties but they can have different values within the properties themselves.
• There are methods that allow objects to interact with each other and with the outside world.
• In Java, we deal with classes, variables and methods, but it is not a pure OO language, which allows us to write simple programs without OOP. This can be done with a single method MAIN.

#### How do we write a simple Java program?

// package unl.cse;

public class HelloWorld {
public static void main(String args[]) {
System.out.println("Hello World!");
}
}

Package Definition
Defines the package.
• Should be all lower case, from general to specific
Class Definition
This defines a class.
• This is not always used for OOP, but everything belongs to a class.
• This is generally CamelCased
Function Definition
This defines the main method, used to drive a program.
• Includes access specifier, public or private
• static is used to denote that an object is not connected
• A type specifier, in this case void which means that there is no return value.
• A name.
• A list of arguments taken. This takes an array of strings.
The Body
A list of statements, which are instructions terminated by a semicolon.
• These are various commands and are used relatively simply.

#### Libraries

• Contains a variety of libraries and APIs
• The Java Runtime Environment. This is just the VM and a few bits of support.
• This includes a variety of tools used to develop Java programs.

#### We will use Eclipse for Java

• Java is Compile Once, run anywhere.
• Compiled with the javac command, run with the java command in the JVM.

### PHP

• Web Based, on the webserver, remote.
• Interpreted language, not compiled.
• Stands for “PHP: Hypertext Preprocessor”
• Generates HTML that is sent to the client.
• Relatively easy to use, and thus very popular.
• C style.
• Allows OOP.
• Weakly, but dynamically typed.
• Automatic GC! WOOO!!
• Basic PHP program
<?php

print "Hello World!\n";

?>


## Lecture 2

### Announcements

Assignment 1 has been posted, and is due by september 9 12:30. Bring hard copy rubric and submit at start of lecture. Submit source and test via webhandin.

### Variables and Data Types in Java

• progrems often must store and minpulate data.
• Variables represent the memory area where a datum is stored.
• It has a name, a value and a data type.
• name is symbolic, this is how you refer to the actual location of the data, the value.
• in some languages, you can only store one type of information within a given variable. This is done by specifying the data type.
• Java has two different data types: primitives and references (objects/ADTs)
• primitives are just that, primitives and are built into the language.
byte
Byte
short
Short
int
Integer
long
Long
float
Float
double
Double
boolean
Boolean
char
Character (these are really just a number, represented by unicode (UTF-16 (NOOOOOOO!!!)))
• reference types are composed of othe data types (thus objects/ADTs)
• types must be declared (damn strong and static typing!)
• variable names follow common rules, but cannot begin with a digit.
• names should follow lowerCamelCase conventions (yuck!!)
• constants are all caps with words seperated by underscores
• Lexical scoping rules are followed.
• Data types can be converted, but it ain’t pretty!!
• doubles don’t convert to integers well.
• Integers, convert to doubles quite well.
• Java allows upcasting (int $$\rarr$$ double) implicitly, but not downcasting.
• Downcasting must be done explicitly (placing the new type in parens before the value).
• Primitives are not objects and thus have no method and belng to no class.
• Sometimes, however, you must convert primitives into objects (NOOOOO!!!!).
• wrapping is done by putting the primitive into the objects, this includes various utility functions.
• Object types are not stored at the same place as the variable name. This comes in ugly when dealing with equality checking!!

### Variables and Data Types in PHP

• similar types
• numerics have no quotes
• strings and char literals are surrounded by quotes
• null is either zero or the empty string depending on context
• similar identifier rules, case sensitive and variables must begin with a dollar sign (woo Perl!!).
• PHP is dynamicallly typed
• Type is implicet given the value that is held
• Type changes based on the value.
• There is such a thing as a constant, but they are defined using define('const', 'value');. They are case sensitive. They are used without a dollar sign.
• reserved words are available from http://php.net/manual/en/reserved.php or http://php.net/manual/en/reserved.keywords.php

### Arrays

• A way of storing identically type entities.
• Not a primitive type, but rather is a reference type.
• Size can be implicit or explicit.
• They can be declared dynamically using new and the number of element.
• Arrays are indexed from 0 (can-not be configured).
• Multidimensional arrays are supported.
• ArrayLists are used for dynamic collections.
• There is something called Map (an interface) for key-value pairs (a hash). This is not ordered, and does not allow duplicate keys (no, really). Keys and values can be of different types, and they can be specified.

## Lecture 3

### Conditionals in Java

• If, if-then-else, if-else-if-else or switch
• If lets you use check with complex boolean expressions
• switch lets you check an expression against multiple, discrete values.
• Switch only works with short, char, byte, int and as of Java 7, strings

### PHP

• Numeric arrays (use a numeric index) (like arraylist)
• associative array (Perl’s hash)
• Multi-dimensional array
• Looping in PHP
• for
• while
• do while
• foreach is used for non-contiguous or non-integer keyed arrays. (uses the keyword as).
• Associative arrays are like a map. Keys are either strings or ints. the big arrow comma is used to seperate keys and values.
• unset is used to remove items or delete an entire array.
• adding items is done simply by indexing
• accessing is simpler
• print_r() prints
• array_keys, array_values and count
• standard conditionals.
• content and type can be compared seperately.
• type conversion is implicit, to the point of adding strings and numerics correectly.

### Java: Loops, Operators and Strings

• for, while, do while, enhanced for
• for is for iteration.
• While is used for when values don’t change as easily. condition is at the beginning
• do while is used for the same as while, but the condition is at the end
• special for loops: the enhanced for loop:

int[] squares = {0,1,4,9,16,25};
for(int j : squares)
{
system.out.println(j);
}

• Only works if Iterable interface is implemented
• Operators
• unary
• arithmetic
• logical

#### Strings

• Not like char arrays of C, although these are used for some things.
• String is a class, but a standard given by the language.
• Provides a standardized interface that gives things such as efficient string manipulation functions.
• Concatenation is done with +
• StringBuilder is a mutable string.
• StringBuffer is thread safe, but otherwise like stringbuilder.
• the == operator does not work for string comparison, as it does not check based on content. use the .equals() method.
• Strings are naturally ordered.
• Unicode is used internally, though for most stuff ASCII will be used.
• charAt
• substring
• replaceAll

## Lecture 4

### Java

#### IO

• Standard Streams
• System.in
• System.out
• System.err
• File based streams
• (Input|Output)Stream – Bytes only
• And the related subclasses
• This is really ugly in java!!!
• There are buffered subclasses of readers and writers

#### File IO

• Scanner interface, using regular expressions for reading formatted input.
• includes basic tokenizer
• includes the following methods:
• nextLine
• next
• nextInt
• nextDouble
• hasNextLine
• hasNext
• hasNextInt
• hasNextDouble
• useDelimeter
• use \\Z to get the entire file.
• Must be imported (java.util.Scanner)
• Command line args are all strings.
• args[0] is not the name of the program as in c/php/most sane languages.
• arguments must be parsed into other types.

#### Sorting and Searching

• Arrays
• arrays.sort()
• arrays.sort(T a[], Comparator<? super T> c)
• Or just write your own damn implementation
• Collections
• Similar to arrays
• Comparators can be written by other users.
• Binary searches
• contains (collection)
• indexOf (collection)

### PHP

#### IO

• arguments are passed as with java.
• in $argv, and$argv[0] includes the name of the script
• Standard Input uses fgets(STDIN[, length])
• print, echo, printf

#### File IO

• open with \$h = fopen(name, mode)
• mode for read is r, writing w
• fgets is used for reading.
• feof to test for file end.
• close with fclose
• get the entire thing with filegetcontents(filename)

#### Function definition

• defined as follows

function name(args-list)
{
body;
}

• pass by value and by reference specifically. (use an ampersand (just like perl!))
• no return type is specified.
• you must explicitly return a value (no implicit progn)
• Default values are possible.

### Announcements

• Don’t forget to print a hard copy
• Individual work
• 2 and beyond will be don in pairs
• must submit typed doc containing following
• name and ID for both
• fave movie
• fave book
• fave singer
• two interesting things
• why chosen.

## Lecture 5: OO in Java/PHP

• 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.

## Lecture 6: More Intro to Java & PHP, Exceptions

### Exceptions

• user entered invalid data
• file can’t be found
• network connection problems
• jvm out of memory
• Exceptions can be anticipated
• Throwable is the parent class of all exceptions.
• Exceptions can be caught.
• checked and unchecked expceptions
• checked are during compile tiem
• unchecked are during run-time
• arithmetic
• array indexing
• null pointer issues
• thrown exception:
• halt execution
• stack trace
• where
• what kind
• hopefully a meaningful message
• compile time
• IO
• Errors are not exceptions, but problems above the user and the programmer
• rarely can anything be done.
• stack overflow

### Exception handling

• throw or catch/handle
• handling with try/catch/finally
• When an error is caught, you need to be able to throw and handle the exceptions
• The exception will smash the stack and go up until it finds a handler
• use finally to make sure to release resources
• remember, exceptions are a special class

### More Intro to OOP

• encapsulation
• operates at higher level of abstraction.
• less internals stuff
• thinking about the problem itself
• seperation of internals and interfaces
• message-passing for communicating between objects
• can make software design easier
• can make maintenance easier
• think in the problem space, not in the machine’s internals
• can make software more reusable
• key ideas
• modularity
• encapsulation
• abstraction
• hierarchical organization and inheritance
• polymorphism

## Lecture 7

### Motivation

• Can I use Eiffel?
• Or SmallTalk?
• machine code -> assembly -> imperative language
• this requires thinking in terms of a computer’s structure
• other languages for their paradigm on the development
• Computers should serve our needs
• OOP versus imperative or declaritive
• imperative
• series of statements that change state.
• things are not encapsulated
• fortran, c
• declarative
• tell it what I want, not how I want it done
• logic of computation, not control flow
• SQL, Prolog
• History
• Lisp
• Simula
• Smalltalk
• C++
• Objective C
• Java
• Design Patterns
• Portland Patterns Repository
• Anti-patterns
• Design-by-contract
• Modeling tools
• This allows us to represent more than just the basic data, and can store structured data.
• stacks
• queues
• maps
• strings
• Objects:
• identity
• state
• behavior
• Message passing
• provide services
• this is how most modern OO is done
• complex data types
• mixed types
• varying visibility
• Objects must be constructed

### Object Design

• decompose an entity into it’s component parts
• keep it simple
• semantics dictate design.
• Avoid God-objects

### Principles

• abstraction
• makes it so that only some things are obvious
• means that you don’t need to know how it works, just that it does.
• don’t just hide the functionality, hide the data storage too.
• encapsulation
• restricts access
• groups related data and methods
• information hiding
• best practices:
• make it all private and use getters/setters
• don’t use static, it belongs to the class, not an object
• inheritance
• polymorphism

### Second Assignment Expectations

• Design Document due next friday
• must be hard copy
• only discuss issues related to the 2nd assignment
• Continue to update the design document
• implement objects that will form a basis for the system
• create parsers
• export function
• XML
• JSON
• design the classes

## Lecture 8

### Inheritance

• allows you to create classes that have the properties of other objects
• extends the definition of objects
• Why?
• reusing things
• can make things more modular
• classify things and use hierarchical structure
• hierarchy of related objects
• inherit behavior and/or fields from superclasses
• liskov substitution
• Benefits is that you can use subtype/inclusion polymorphism
• Robin is-a bird
• Multiple Inheritance
• In java, it ain’t pretty, nor is it possible

### Polymorphism

• allows for abstraction
• allows methods to have multiple forms
• on the fly
• functions have different implementations.
• things are created as needed
• overriding – changes in terms of arguments passed

## Lecture 9: Polymorphism

• 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.

## Lecture 10: Yet More Polymorphism

• 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
• can call methods, interact with it.
• created and destroyed indepentently

### Relationships between classes.

• aggregation
• has another as a member.
• does not imply ownership
• has as an attribute.
• Composition
• one object owns another
• should be private
• destroyed upon destruction of owner.
• Composition is a technique for reusing classes.
• inheritance is also used for reusability.
• Ex:
• point
• line
• line is-a set of points: inheritance
• line has many points: composition
• Inheritance is good for rigid hierarchy.
• frigile as changes up-stream affect everything downstream
• composition is more extensible and flexible.
• mixins
• multiple inheritance
• interfaces provide specifications, but not behavior.
• ducktyping
• python’s type behavior
• object type defined by what it can do, not by what it is.
• if it walks like a duck and talks like a duck, it’s a duck.
• copy constructors
• A way of creating different copies of objects.
• This can be used to convert between classes.
• make sure to use a deep copy, not just copy of reference.

## Lecture 11: Still more OO in Java

• 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

## Lecture 12: Better OO

• 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

## Lecture 13: Still More Polymorphism

• Java supports different types of polymorphism
• no behavioral polymorphism (no strict inheritance)
• method overriding
• @Override annotation
• covariant return types in method overriding
• 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

## Lecture 14: Even More Polymorphism

• 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.

## Assignment 3 Discussion

• Approach
• design new classes
• Understand the problem in english (or greek, or esperanto, or spanish or whatever…)
• Do hand computation (NOOOOO!!!!!)

## Lecture 15: Copying existing objects

• 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

## Lecture 15: Databases

• 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

## Lecture 16: More databases

• 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)

### Database management systems

• SQL and SQL:2001
• a collection of programs used for managing a db
• defining includes specifiying data types, structures and constraints of the data.
• database definition is stored as data within the database. this is the meta-data. (Codd’s 4th rule)
• often includes a networking component to allow multiple users to use the data.
• a transaction is an atomic entity that includes reading, writing and deletion.
• you store the semantics of the data, not just the data itself
• remember that you can relate records in different tables.

### The Relational Model

• Edgar Frank “Ted” Codd
• Originally System R
• Had to convince the customers of IBM to be able to build the system.
• Uses the concepts of relations, set theory and first order logic.
• A database is a collection of relations, informally, a table of values where each row is a collection of related data values.
• You must define the type of data that can be in a column.
• Values must be atomic.
• each row may have a unique primary key, which can be automatically incremented.
• you can have external identifiers
• you can use foriegn keys to relate different data in different tables/rows
• data must be consistent
• constraints can be used to ensure consistency
• non-null primary-keys are not allowed
• rows that are related to other rows must exist.
• constraints can be very particular, including basic format.
• ACID
atomicity
can occur or cannot occur, no in-between
consistency
transactinos retain a state of consistency. constraints, triggers and cascades can be used to ensure this
isolation
To transaction interferes with or in even aware of another. Serial trasactions are equivalent to serial transactions.
durability
once commited, a transaction remains so. Data is to be protected from catastrophic error (such as power loss or crash)

## Lecture 17: Still more Databases, Structured Query Language

• 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

### MySQL: Getting Started

• You can use the CLI or MySQL Workbench along with a few others
• you cannot create new databases
• DDL:
• CREATE
• ALTER
• DROP
• DML:
• INSERT
• SELECT
• UPDATE
• DELETE
• DCL:
• GRANT
• REVOKE
• Constraints
• not null
• unique
• primary key
• foreign key
• check
• default

## Lecture 18: Still More Databases

• A Review of SQL syntax and some basic sequences.

## Lecture 19: Yet More Databases

• 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.

## Lecture 20: Databases, continued

• 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.
• CREATE INDEX name ON table(column)

## Midterm Review

• From Lecture 0 to lecture 15
• Must bring number 2 pencils

## Lecture 21: Database Design

• 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)

### Database Normalization

• Normalization is the process of efficiently organizing data within a database.
• eliminate redundant data
• 5 main rules (but primarily the first 3)
• 1NF
• 2NF
• 3NF
• BCNF
• 4NF
• 5NF
• 1NF eliminates duplicate columns
• 2NF meets 1NF and cannot have rows in the same table wth the same values (this requires the use of foreign keys)
• 3NF meets 2NF and has all columns removed from the table that aren’t dependent on the PK

## Lecture 22: Hooking up to the DB with JDBC

• 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.
• 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

## Lecture 23: More JDBC

• 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.
• remember to log things! consider log4j

## Lecture 24: Collections of Objects

• 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
• retrieving
• removing
• automatic resizing
• other functions
• determine size and emptiness
• iterate over elements
• batch operations
• then decide how you want to implement them
• this can be done by creating new arrays every time something is added/removed

## Lecture 25: More collection ADTs

• 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

## Lecture 26: Comparator Classes

• 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

## Lecture 27: Comparator

• 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

## Lecture 28: Computation

• 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
• poor pseudocode
• gives too many details
• is implementation or language specific
• Algorithmic design
1. Understand the problem
3. choose the appropriate data structure
5. prove the correctness of the algorithm
6. evaluate complexit
7. test it
• Algorithmic analysis
1. running time (depends on)
• processor
• 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

## Lecture 29: Continued Algorithmic Analysis

• 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)$$
$$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)$$

## Lecture 30: Recursion

• 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

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

• 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

(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))))


## Lecture 31: More Recursion!

• 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

## Lecture 32: More Big-O Analysis

• 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

## Lecture 33: Sorting Algorithms

• 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)$$

## Lecture 34: Complexity of Recursive Algorithms

• 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.$

## Lecture 35: Stacks, queues and dequeues

• 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)

## Lecture 36: Time Complexity and Trees

### Efficiency

• array:
• insertion/deletion linear
• indexed-retireval constant
• linear search linear
• binary search if sorted is iterated log
• insertion/deletion of arbitrary is linear
• binary search not possible
• stacks and queues
• push/pop is constant depending on type

### Trees

• a type of acyclic graph
• a collection of nodes and edges
• parents have children
• leafs have no children
• the root has no parents
• a path is a sequence of nodes that are connected by edges
• a path is simple if it does not traverse nodes more than once.
• depth is the minimum distance from the root
• height of a tree is the maximum depth of any node.
• a binary tree can have at max 2 children
• A binary tree is called full or perfect if all nodes are present at all levels 0 up to the height of the tree
• A tree is called complete if it is completely filled exept possibly the last level, and all nodes are as far left as possible
• In a tree al nodes are onnected by exactly one unique path
• The maximum number of nodes at any level k is 2k
• thus the maximum number of nodes for any binary tree of depth d is $$2^{d+1} - 1$$
• the minimum depth of a tree is shown as $$\log_2(n + 1) - 1$$
• pre-order traversal starts on the root, then goes left, then right, recursing as it goes.
• in-order is left, root, right
• post-order is left, right, root

## Lecture 37: More Trees

• 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

## Lecture 38: Trees, continued: Heaps

• 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

### Two important algorithms

• linear search
• binary search
• iterative
• recursive
• search variations
• find the first/last element
• find the index
• key versus equality
• find all such items
• find extremal items
• handle failed searches
• on types
• arrays
• lists
• sets
• solution spaces (optimization)

## Lecture 39: Search Algorithms

• 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

## Lecture 40: Finals

• Tuesday 1530, Hamilton 112
• open book, open note