cse 2231 final copy

Abstract class

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

Factoring out common code

Method bodies that can be written once— and work for any implementation of NaturalNumberKernel because they are programmed to that interface—have been factored out into an abstract class

Can you instantiate an abstract class?

No - You can't use an abstract class like a normal class and create objects from it

UUT

Unit under testing

How to achieve single-point control over change in this situation

"Re-route" all UUT constructor calls to another method, which then calls the UUT constructor, so only the body of that one method needs to be changed to accommodate a different UUT

Class ending with "L"

Kernel class that directly represents the new type using a component from Java libraries

Instance variable

There is a distinct variable (with the same name) for each instance of the class in which it is declared

Criteria for kernel implementation

1. Easy to understand and write

2. More efficient

Sequence3 on Stack

Sequence represented as 2 stacks, left and right. Sequence = rev(left) + right

Representation of sequence is 2 stacks "facing each other" in the middle of sequence

Client view

Mathematical models, method contracts

Kernel interface shows WHAT the software does

Implementer view

Data representation, algorithms

Kernel class shows HOW the software does it

Abstract state space

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

Concrete state space

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

Abstraction function

How to interpret any concrete value (that satisfies the representation invariant) as an abstract value?

@correspondence

Representation invariant

What configurations of values of the instance variables can arise?

@convention

Why hashing?

1. Can be quickly identified

2. Must contain the item

T/F: Nodes in a linked list must always have consecutive memory addresses?

False

T/F: Nodes in a linked list can be accessed in constant time?

False

T/F: Nodes in a linked list require at least one smart node?

False

T/F: Nodes in a linked list can be accessed sequentially in linear time?

True

T/F: The process of building a heap will completely sort its elements?

False

T/F: A subroutine is needed to adjust the root of a subtree to its proper position, assuming the subtree is a heap except for its root

True

T/F: Heaps are parameterized by a type and an ordering process?

True

T/F: A heap is a binary tree with extra constraints on its shape and organization

True

Collection type definition

Any type whose abstract mathematical model involves: string, set, multiset, tree, binary tree

Collection type examples

Array, queue, set, sequence, stack, map, sorting machine

Array pros

-Direct access

-Constant time access (regardless of length)

Array cons

-Fixed size; can run out of room

-Fixed size; initialization might be expensive if entries go unused

-Adding/removing entires in the middle requires moving other entries, which is slow

Array is represented by…

A contiguous block of memory locations with consecutive memory addresses so the memory address of the entry at index i can be directly calculated from the memory address of the first entry, by using simple arithmetic

JVM

Java Virtual Machine

Binary tree

-Can be empty tree

-Or can be non-empty tree consisting of root node and 2 subtrees

-Mathematical type: Binary trees with any label of type T

Traversal Orders

1. Pre-order: Root, left, right

2. In-order: Left, root, right

3. Post-order: Left, right, root

Binary Search Tree (BST)

A binary tree where the left node < root, and right node > root

Sorting Machine

-Allows adding elements of type T to a

collection of such elements, and then removing them one at a time in sorted order

-Mathematical model: 3-tuple

{insertion_mode: boolean,

ordering: binary relation on T,

contents: finite multiset of T}

Why is sorting machine better than sort?

-If all elements are already sorted by the end of "changeToExtractionMode", then there is no difference in performance

-If elements are not already sorted by the end of "changeToExtractionMode", then the performance advantage is that you don't need to remove all the elements

T/F: Smart nodes can prevent run-time errors arising from the code managing of a linked list?

False

T/F: Smart nodes can provide significantly faster performance when manipulating the elements of a linked list

False

T/F: Smart nodes can make initial setup of the linked list faster

False

T/F: Smart nodes can aid removal of special cases from some methods that work with a linked list

True

What is the data structure of a doubly-linked list?

2 references per node: one to the "next" node and one to the "previous" node