cse 2231 final exam

abstract class

"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

"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 two Stacks, left and right
Sequence = rev(left) + right
Representation of Sequence is "two 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 the instance variable 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

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

collection type examples

Array, queue, set, sequence, stack, map, SortingMachine

Array pros

- direct access
- constant time access (regardless of length)

array cons

- fixed size; can run out of room
- fixed size; instantiation might be expensive if entries go unused
- adding/removing other entries in the middle requires moving entries around, which is slow

What's an array 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
- can be non-empty consisting of root node and two subtrees
- mathematical type: binary trees with any label of type T

pre-order

root, left, right

in-order

left, root, right

post-order

left, right, root

Binary Search Tree (BST)

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

SortingMachine

- 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 SortingMachine 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 runtime 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 the initial setup of the linked list faster

false

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

true

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

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

TF

type family interface whose kernel is being implemented

What does the standard method this.newInstance() do?

returns a new object with the same DYNAMIC type as this, having an initial value (usually 0 or empty)

Server (BugsWorld)

each display shows the current state of the world, plus some statistics about the simulation

Client (BugsWorld)

each client program simulates creature (bug) behavior for all creatures of one species

Displays (BugsWorld)

each display shows the current state of the world, plus some statistics about the simulation

3 Compiler Parts

Tokenizer -> Parser -> Code Generator

Abstract Syntax Tree (AST)

- tree model of an entire program or certain "program structure" (ex: a statement or expression)
- "abstract" because the characters used in the concrete program do not appear in this representation
- mathematical model: 3-tuple {KIND of statement, TEST of condition, CALL of instruction}
NOTE: either test or call is relevant information, depending on what kind of statement it is

Statement

- component family which allows for manipulation of ASTs for BL statements

block (for Statement)

child can be anything except block

if (for Statement)

child must be block

while (for Statement)

child must be block

If_Else (for Statement)

two children, both must be blocks

call (for Statement)

zero children

T/F: you can use == to check equality of enums

true

Enumerations (or enums)

special construct, allows for meaningful symbolic names (the kinds in Statement, for example)

Statement no-arg constructor

this = compose((BLOCK, ?, ?), <>)

Program

- component family that allows for the manipulation of values representing entire BL programs

mathematical model of Program

{name: IDENTIFIER, context: CONTEXT, body: STATEMENT_MODEL}

mathematical model of Statement

tree of statement_label

Program no-arg constructor

this = ("Unnamed", {}, compose((BLOCK, ?, ?), <>))

refactoring

restructuring code without changing its behavior for the purpose of improving readability, making small syntax changes, etc.

Context-Free Grammar (CFG)

- a set of formation rules for strings in a language that satisfies certain technical conditions
- used to implement a recursive-descent parser

Recursive-Descent Parser

an algorithm to parse a BL program and construct the corresponding Program object

Terminal symbols

terminates at the point, stop writing when you hit that symbol, typically bolded in the CFG

Non-terminal symbols

only appears on left side of a production, typically italicized

Metagrammar

used to define the CFG itself, not part of the alphabet

Derivation

- a series of specific rewrite-rule applications that begin with the start symbol and continue until only terminal symbols remain
- can be depicted in a derivation tree

ambiguity

when some strings in the language of the CFG have more than one derivation tree, which makes it harder to evaluate the correct outcome

Token

a single entity in a language

T/F: purpose of a tokenizer is to transform source code into machine/object code the computer can more easily understand or interpret

false

T/F: purpose of a tokenizer is to remove whitespace and separate the source code into small, meaningful units

true

T/F: purpose of a tokenizer is to construct an abstract representation of a program that holds information about its intended meaning

false

BL Tokenizer

treats string of consecutive whitespace characters as separators between tokens, since the tokens are the words

main uses of CFGs

- generate strings in a language
- detect if a given string is in the language

parsing

going from a string to its derivation tree/AST

5 rules of a Recursive-Descent Parser

1. One parse/method/non-terminal symbol
2. Non-terminal symbol on RHS of rewrite rule --> Call parse method for that non-terminal symbol
3. Terminal symbol on RHS of rewrite rule --> Consume token from input token string
4. "|" (vertical bar) in CFG --> "If-else" in parser
5. "{ }" in CFG --> "While" in parser

CFG Symbols { }

- indicates that the enclosed sequence of symbols can occur 0+ times
- Helps turn a left-recursive CFG into an equivalent CFG that can be parsed by recursive-descent

parsing an arithmetic expression

the parser evaluates it by turning the string of tokens (in the language of the CFG) to the value of that expression as an int

facts recognized by modern software

- modern software consists of potentially large number of components that are composed into larger components / systems
- a class is a component with its client-visible specifications in the interface it implements

how many interfaces can an interface extend?

one or more

T/F: interfaces can be generic

true

what contains a description of WHAT the software does?

interface

what contains a description of HOW the software does it?

class

all instance methods in an interface are automatically...

public abstract

T/F: it is useful for an interface to define variables

false

T/F: constructors are instance methods

false; constructors can't be defined in an interface, which is where instance methods are defined

Kernel interface defines...

1. mathematical model
2. contract(s) for constructors
3. contract(s) for kernel methods
4. contract(s) for methods from Java library
5. interfaces without their own contract specifications (ex. iterator, comparator)

Enhanced interface defines...

contract(s) for all other methods for the type

Kernel methods should be a ____ of ____ that is ____.

a) minimal set
b) methods
c) functionally complete

a functionally complete set of kernel methods is powerful enough to...

1. give variable of the type ANY allowable value
2. determine the value of a variable of the type
3. implement "equals" and "toString"
4. check every Kernel method's precondition
(GDI-chick)

circularity

Interface A extends something of general type interface B in initialization, and interface B extends interface A

A Java interface defines a ___ ____ along with its set of ____ ____

a) type name
b) instance methods

T/F: an interface type may be used in Java even if there is no implementation of it in scope

true

interfaces are ____-____ construct

compile-time

Declared (Static) Type

interface type (left side)

Object (Dynamic) Type

Class type (right side)

T/F: the declared type of a variable may be an interface type

true

What happens if the declared type is an interface type?

the object type (a class) MUST implement the declared type (an interface)