Questions and Answers
What is an abstract class?
A partial or incomplete class that contains bodies for some but not all of the methods of the interfaces it claims to implement.
What does it mean to factor out common code?
It means that method bodies that can be written once and work for any implementation of NaturalNumberKernel have been moved into an abstract class.
Can you instantiate an abstract class?
False
What does UUT stand for?
Signup and view all the answers
How do you achieve single-point control over change in constructor calls?
Signup and view all the answers
What type of class ends with 'L'?
Signup and view all the answers
What is an instance variable?
Signup and view all the answers
Criteria for kernel implementation include __________ and __________.
Signup and view all the answers
What does Sequence3 on Stack refer to?
Signup and view all the answers
What is the client view in software?
Signup and view all the answers
What is the implementer view in software?
Signup and view all the answers
What is the abstract state space?
Signup and view all the answers
What is a concrete state space?
Signup and view all the answers
What is the abstraction function?
Signup and view all the answers
What is the representation invariant?
Signup and view all the answers
Why hashing?
Signup and view all the answers
Nodes in a linked list must always have consecutive memory addresses?
Signup and view all the answers
Nodes in a linked list can be accessed in constant time?
Signup and view all the answers
Nodes in a linked list require at least one smart node?
Signup and view all the answers
Nodes in a linked list can be accessed sequentially in linear time?
Signup and view all the answers
The process of building a heap will completely sort its elements?
Signup and view all the answers
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.
Signup and view all the answers
Heaps are parameterized by a type and an ordering process?
Signup and view all the answers
A heap is a binary tree with extra constraints on its shape and organization?
Signup and view all the answers
What is a collection type?
Signup and view all the answers
What are some examples of collection types?
Signup and view all the answers
What are the pros of using arrays?
Signup and view all the answers
What are the cons of using arrays?
Signup and view all the answers
How is an array represented?
Signup and view all the answers
What does JVM stand for?
Signup and view all the answers
What is a binary tree?
Signup and view all the answers
List the traversal orders for binary trees.
Signup and view all the answers
What is a Binary Search Tree (BST)?
Signup and view all the answers
What is a sorting machine?
Signup and view all the answers
Why is a sorting machine better than a regular sort?
Signup and view all the answers
Smart nodes can prevent run-time errors arising from the code managing of a linked list?
Signup and view all the answers
Smart nodes can provide faster performance when manipulating elements of a linked list?
Signup and view all the answers
Smart nodes can make initial setup of the linked list faster?
Signup and view all the answers
Smart nodes can aid removal of special cases from some methods that work with a linked list?
Signup and view all the answers
What is the data structure of a doubly-linked list?
Signup and view all the answers
What is TF in relation to interfaces?
Signup and view all the answers
What does the standard method newInstance() do?
Signup and view all the answers
What is the role of the server in BugsWorld?
Signup and view all the answers
What is the role of the client in BugsWorld?
Signup and view all the answers
What do displays show in BugsWorld?
Signup and view all the answers
What are the 3 parts of a compiler?
Signup and view all the answers
What is an Abstract Syntax Tree (AST)?
Signup and view all the answers
What is a statement in the context of ASTs?
Signup and view all the answers
What are the 5 kinds of statements?
Signup and view all the answers
You can use == to test equality of enums?
Signup and view all the answers
What is an Enumeration (Enum)?
Signup and view all the answers
What is a statement no-arg constructor?
Signup and view all the answers
What is a program in the context of BL?
Signup and view all the answers
What are the 3 components of a program model?
Signup and view all the answers
What is refactoring?
Signup and view all the answers
What is a Context-Free Grammar (CFG)?
Signup and view all the answers
What is a Recursive-Descent Parser?
Signup and view all the answers
What are terminal symbols?
Signup and view all the answers
What are non-terminal symbols?
Signup and view all the answers
What is a metagrammar?
Signup and view all the answers
What is a derivation?
Signup and view all the answers
What is ambiguity in the context of CFG?
Signup and view all the answers
What is a token?
Signup and view all the answers
The purpose of a tokenizer is to transform source code into machine/object code?
Signup and view all the answers
The purpose of a tokenizer is to remove whitespace and separate the source code into small, meaningful units?
Signup and view all the answers
The purpose of a tokenizer is to construct an abstract representation of a program?
Signup and view all the answers
What does a BL tokenizer do?
Signup and view all the answers
What are the two main uses of CFGs?
Signup and view all the answers
What is parsing?
Signup and view all the answers
What are the 5 rules of a recursive-descent parser?
Signup and view all the answers
What do CFG symbols { } indicate?
Signup and view all the answers
How does the parser evaluate an arithmetic expression?
Signup and view all the answers
What is an expression?
Signup and view all the answers
What is a term?
Signup and view all the answers
What is a factor?
Signup and view all the answers
What are the 2 facts recognized by modern software?
Signup and view all the answers
How many interfaces can an interface extend?
Signup and view all the answers
Can an interface be generic?
Signup and view all the answers
What contains a description of WHAT the software does?
Signup and view all the answers
What contains a description of HOW the software does it?
Signup and view all the answers
What can interfaces define?
Signup and view all the answers
What can't interfaces define?
Signup and view all the answers
All instance methods in an interface are automatically public abstract?
Signup and view all the answers
Is it usual for an interface to define variables?
Signup and view all the answers
Are constructors instance methods?
Signup and view all the answers
What does Kernel Interface define?
Signup and view all the answers
What does Enhanced Interface define?
Signup and view all the answers
Kernel methods should be a __________ set of __________ that is __________.
Signup and view all the answers
What is a functionally complete set of kernel methods powerful enough to do?
Signup and view all the answers
What is circularity in interfaces?
Signup and view all the answers
A Java interface defines a ______ ____ along with its set of ________ ________.
Signup and view all the answers
An interface type may be used in Java even if there is no implementation of it in scope?
Signup and view all the answers
Interfaces are ______- constructs.
Signup and view all the answers
After a Java program compiles, object types are kept at ______- constructs.
Signup and view all the answers
What is a declared (static) type?
Signup and view all the answers
What is an object (dynamic) type?
Signup and view all the answers
The declared type of a variable may be an interface type?
Signup and view all the answers
The object type can be an interface type?
Signup and view all the answers
What happens if the declared type is an interface type?
Signup and view all the answers
What happens to declared types once a Java program compiles?
Signup and view all the answers
Study Notes
Abstract Classes and Interfaces
- An abstract class allows partial implementation, containing some defined methods while leaving others unimplemented.
- Factoring out common code into an abstract class enables reuse across implementations of a particular interface, such as NaturalNumberKernel.
- Abstract classes cannot be instantiated, meaning objects cannot be created directly from them.
Testing and Control
- Unit Under Testing (UUT) refers to the specific component or code being tested.
- To manage changes effectively, re-route UUT constructor calls to a single method, allowing modifications in one location instead of multiple.
Class Types and Variables
- A class ending with "L" is known as a kernel class, serving as a direct representation of a new type using existing Java library components.
- Instance variables are unique to each instance of a class and maintain their names across instances.
Kernel Implementation Criteria
- Effective kernel implementations should be easy to understand and more efficient.
Data Structures
- A Sequence3 is represented using two stacks: left and right, where the sequence can be viewed as
rev(left) + right
. - Client view focuses on the mathematical models and method contracts, while the implementer view deals with data representation and algorithms.
State Spaces
- Abstract state space consists of all potential mathematical model values from the client's perspective.
- Concrete state space represents all possible values within the data representation.
Functions and Invariants
- The abstraction function defines how to interpret a concrete value satisfying the representation invariant into an abstract value.
- Representation invariant describes valid configurations of instance variable values.
Hashing and Linked Lists
- Hashing allows for quick identification of items in data structures and ensures items are contained within the structure.
- Linked lists do not require nodes to have contiguous memory addresses and accessing nodes is done sequentially in linear time, not constant time.
Heaps and Trees
- Heaps are binary trees with constraints on their shape and organization, and they may not completely sort elements when built.
- A binary search tree (BST) requires that each left node is less than the root and each right node is greater than the root.
Sorting Machine
- A sorting machine adds elements to a collection and removes them in sorted order, described mathematically by a 3-tuple containing insertion mode, ordering, and contents.
Smart Nodes
- Smart nodes do not improve performance in linked list manipulations or setup times but can help simplify certain removal cases from linked list methods.
Compiler Components
- A typical compiler consists of three parts: Tokenizer, Parser, and Code Generator, abbreviated as TPC.
- The Abstract Syntax Tree (AST) represents program structure abstractly, omitting characters from the concrete program.
Parsing and Grammars
- Context-Free Grammar (CFG) defines formation rules for language strings and is implemented using a recursive-descent parser.
- Terminal symbols mark endpoints of productions, while non-terminal symbols appear only on the left side of productions.
Tokenization and Parsing
- A tokenizer splits source code into meaningful units and removes whitespace, while parsing converts string input to its derivation tree or AST.
Interface Characteristics
- An interface can extend one or more interfaces and must define an abstract type with instance methods.
- Interfaces cannot define constructors or instance variables but can declare static final variables.
Type and Object Relations
- Declared types can be interface types, but object types must be class types that implement the declared interface.
- After compilation, declared types are absent in the JVM, retaining only object types for runtime.
Miscellaneous
- Refactoring restructures code while preserving functionality for better readability and maintainability.
- Circularity occurs when interfaces define mutual dependencies, indicating a structural design flaw.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Prepare for your CSE 2231 final exam with these flashcards focusing on key concepts such as abstract classes and code factoring. Each card offers concise definitions to enhance your understanding of important programming principles and terminology. Master the material effectively and boost your confidence!