CSE 2231 Midterm 1 Stuff

Mathematical Type

Every program type in a program has this, ex: integer, real

Precondition

Otherwise known as the requires clause, it characterizes the responsibility of the program that calls (uses) that method. In other word, it’s the responsibility of the client using the code.

Postcondition

Otherwise known as the ensures clause, it characterizes the responsibility of the program that implements that method. In other words, it’s the responsibility of the implementer making the program.

Universal Quantification

Used when you want to say something is true for every combination of values that satisfy a certain property.

Example:
for all quantified-variables
where (restriction-assertion)
(main-assertion)

Existential Quantification

Used when you want to say something is true for some combination of values

Example:
there exists quantified-variables
(assetrion)

Object Class

A special built in class that provides default implementations for the following instance methods:
boolean equals(Object obj)
int hashCode()
String toString()

Abstract Class

A kind of “partial” or incomplete class that contains bodies for some but (typically) not all of the methods of the interfaces it claims to implement

Convenience Methods

Methods implemented in JUnit Kernel testing that are meant to help you create test cases or handle other busy work

Version Control

In team projects, software engineers:
- Share and extend a common code base
- Work concurrently with each other

Best practice is for a team to use a … system

Central Repository

Keeps all files and a history of all modifications to them
- A new team member can check out their own private copy from the …
- Each member can update their own copy to reflect the changes in the …
- Each member can commit changes from their own private copy to the …

Implementing a Kernel

Two major questions to address:
1. What data representation (data structure) should be used to represent a value of the new type being implemented?
2. What algorithms should be used to manipulate that data representation to implement the contracts of the kernel methods?

Two-Level Thinking

Restrict your attention to exactly two adjacent levels in the tower:
- One is the level for which you ae implementing a new kernel class
- The other is the level directly below the level for the new kernel class you are creating

Client View (Kernel)

Can see the mathematical model and method contracts

Implementer View (Kernel)

Can see the data representation and algorithms

Abstract State Space

The set of all possible math model values as seen by a client

Concrete State Space

The set of all possible math model values of the data representation

One Step Thinking

Restrict your attention to the states just before and just after a method call

Commutative Diagram

Shows the relationships between the concrete state space and the abstract state space before and after the method calls

Abstract Transition

For each state before the call, where it might end up according to the method’s contract.

Concrete Transition

For each state before the call, where it might end up according to the method’s body

Representation Invariant

Which “configurations” of values of the instance variables can ever arise?

Characterizes the values that the data representation (instance variables) might have at the end of each kernel method body, including the constructor(s)

Made to hold by the method bodies’ code, and it is recorded in the convention clause in a javadoc comment for the kernel class

Abstraction Function

How are the values of the instance variables to be interpreted to get an abstract value?

Describes how to interpret any concrete value (that satisfies the representation invariant) as an abstract value

Not computed by any code, but is merely recorded in the correspondence clause in a javadoc comment for the kernel class

Kernel Purity Rule

No constructor or method body in the kernel class should call any public method from the same component family

Linear Search

The algorithm that examines - potentially - every item in a collection until it finds what it is looking for

Constant Time

Runtime does not change with input size

Log Time

Runtime grows very slowly as input size grows

Linear Time

Runtime grows directly with input size

n Log n Time

runtime slightly worse than linear; divide and conquer style

Quadratic Time

Runtime grows with the square of the input size

Exponential Time

Runtime doubles with each extra input element

Hashing Thought

Instead of searching through all of the items, store the items in many smaller buckets and search through only one bucket that:
1. Can be quickly identified
2. Must contain the item you’re looking for

Hashing Identification

Suppose you need to search through n items of type T, and you decide to organize the items into m buckets

Given x of type T, compute from it some integer value h(x)

Look in bucket number h(x) mod m

Hashing Procedure

1. Create hashTable by declaring something like a set of arrays

2. Get the hashCode value of a certain integer in given data set

3. Take that hashCode value and mod it by the hashTable size

   1. Put the value in that bucket

Binary Tree

Can be thought of as a structure containing zero or more nodes, each with a label of some mathematical type, say T, called the label type

Is either:
- an empty tree which has no nodes at all
- a non empty tree, which has a root node and two subtrees of the root

Size

The total number of nodes in a tree (binary tree)

Height

The number of nodes on the longest path from the root to an empty subtree of t

Labels

The set whose elements are labels of a tree (binary tree)

Binary Tree Assemble

assembles in this a binary tree with root label root and subtrees left and right

Binary Tree Disassemble

Disassembles this into its root label, which is returned as the value of the function, and subtrees left and right

Pre-order

Root is visited before left and right

In-Order

Root is visited between left and right

Post-Order

Root is visited after left and right

Binary Tree ReplaceRoot

Replaces the root of this with x and returns the old root

Binary Search Tree

A common arrangement of labels, which supports searching that is much faster than linear search

Total Preorder

A binary relation on T that is total, reflexive and transitive

Binary Relation

May be viewed as a set of ordered pairs of T, or as a boolean valued function R of two parameters of type T that is true iff that pair is in the set

Total Relation

The binary relation R is … whenever:
for all x, y: T
(R(x, y) or R(y, x))

Reflexive Relation

The binary relation R is … whenever:
for all x: T (R(x, x))

Transitive Relation

The binary relation R is … whenever:
for all x, y, z: T
(if R(x, y) and R(y, z) then R(x, z))

Binary Search Tree Arrangement

A binary tree is a BST whenever the arrangement of node labels satisfies these two properties:
1. For every node in the tree, if its label is x and if y is that node’s left subtree, then y < x

2. For every node in the tree, if its label is x and if y is that node’s right subtree, then y > x

SortingMachine

Component family that allows you to add elements of type T to a collection of such elements, and then to remove them one at a time in sorted order according to a client-supplied ordering

SortingMachine Mathematical Model

An ordered triple (or a three tuple of a boolean, a binary relation on T, and a finite multiset of T)

SORTING_MACHINE_MODEL is {
insertion_mode: boolean,
ordering: binary relation on T,
contents: finite multiset of T

Finite Multiset

Essentially a finite set with multiple copies of elements allowed, so there are effectively “counts” of all values of the element type T

SortingMachine Add

Adds x to the contents of this

SortingMachine changeToExtractionMode

Changes the mode of this from insertion to extraction

SortingMachine removeFirst

Removes and returns some “first” (smallest) element from this

SortingMachine isInInsertionMode

Reports whether this is in insertion mode

SortingMachine order

Reports Comparator<T> being used for sorting of this

SortingMachine size

Reports the number of elements in this.contents

Insertion Sort

Sorting algorithm where it divides the array into two parts: a sorted portion and unsorted portion. It then takes the first element from the unsorted portion and inserts it into the correct spot in the sorted portion, and does this until it’s all sorted (add method does all of the work)

Quick Sort

Sorting algorithm that selects a pivot and arranges it so that the elements smaller than the pivot are on its left and larger on its right and will repeat this until the array is sorted (changeToExtractionMode does all of the work)

Selection Sort

Sorting algorithm where it will find the smallest element from the unsorted portion of the list and swapping it with the first unsorted element, which is repeated until sorted (removeFirst does all of the work)