CSE 2231 Final Flashcards
100 Questions
100 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

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?

<p>Unit under testing.</p> Signup and view all the answers

How do you achieve single-point control over change in constructor calls?

<p>By re-routing all UUT constructor calls to another method that then calls the UUT constructor.</p> Signup and view all the answers

What type of class ends with 'L'?

<p>Kernel class that directly represents the new type using a component from Java libraries.</p> Signup and view all the answers

What is an instance variable?

<p>A variable that has a distinct value for each instance of the class in which it is declared.</p> Signup and view all the answers

Criteria for kernel implementation include __________ and __________.

<p>easy to understand and write, more efficient</p> Signup and view all the answers

What does Sequence3 on Stack refer to?

<p>Sequence represented as two stacks: left and right, where Sequence = rev(left) + right.</p> Signup and view all the answers

What is the client view in software?

<p>Mathematical models, method contracts showing WHAT the software does.</p> Signup and view all the answers

What is the implementer view in software?

<p>Data representation and algorithms showing HOW the software does it.</p> Signup and view all the answers

What is the abstract state space?

<p>The set of all possible math model values as seen by the client.</p> Signup and view all the answers

What is a concrete state space?

<p>The set of all possible math model values of the data representation.</p> Signup and view all the answers

What is the abstraction function?

<p>It defines how to interpret any concrete value as an abstract value.</p> Signup and view all the answers

What is the representation invariant?

<p>It describes what configurations of values of the instance variables can arise.</p> Signup and view all the answers

Why hashing?

<p>It allows quick identification and must contain the item.</p> Signup and view all the answers

Nodes in a linked list must always have consecutive memory addresses?

<p>False</p> Signup and view all the answers

Nodes in a linked list can be accessed in constant time?

<p>False</p> Signup and view all the answers

Nodes in a linked list require at least one smart node?

<p>False</p> Signup and view all the answers

Nodes in a linked list can be accessed sequentially in linear time?

<p>True</p> Signup and view all the answers

The process of building a heap will completely sort its elements?

<p>False</p> 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.

<p>True</p> Signup and view all the answers

Heaps are parameterized by a type and an ordering process?

<p>True</p> Signup and view all the answers

A heap is a binary tree with extra constraints on its shape and organization?

<p>True</p> Signup and view all the answers

What is a collection type?

<p>Any type whose abstract mathematical model involves: string, set, multiset, tree, binary tree.</p> Signup and view all the answers

What are some examples of collection types?

<p>Array, queue, set, sequence, stack, map, sorting machine.</p> Signup and view all the answers

What are the pros of using arrays?

<p>Direct access and constant time access regardless of length.</p> Signup and view all the answers

What are the cons of using arrays?

<p>Fixed size; can run out of room, fixed size; initialization might be expensive if entries go unused, adding/removing entries in the middle requires moving other entries.</p> Signup and view all the answers

How is an array represented?

<p>By a contiguous block of memory locations with consecutive memory addresses.</p> Signup and view all the answers

What does JVM stand for?

<p>Java Virtual Machine.</p> Signup and view all the answers

What is a binary tree?

<p>A tree that can be empty or consist of a root node and two subtrees.</p> Signup and view all the answers

List the traversal orders for binary trees.

<p>Pre-order: root, left, right; In-order: left, root, right; Post-order: left, right, root.</p> Signup and view all the answers

What is a Binary Search Tree (BST)?

<p>A binary tree where the left node is less than the root, and the right node is greater than the root.</p> Signup and view all the answers

What is a sorting machine?

<p>A structure that allows adding elements and then removing them in sorted order.</p> Signup and view all the answers

Why is a sorting machine better than a regular sort?

<p>Because if all elements are already sorted by the end, no elements need to be removed.</p> Signup and view all the answers

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

<p>False</p> Signup and view all the answers

Smart nodes can provide faster performance when manipulating elements of a linked list?

<p>False</p> Signup and view all the answers

Smart nodes can make initial setup of the linked list faster?

<p>False</p> Signup and view all the answers

Smart nodes can aid removal of special cases from some methods that work with a linked list?

<p>True</p> Signup and view all the answers

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

<p>Two references per node: one to the next node and one to the previous node.</p> Signup and view all the answers

What is TF in relation to interfaces?

<p>Type family interface whose kernel is being implemented.</p> Signup and view all the answers

What does the standard method newInstance() do?

<p>Returns a new object with the same dynamic type as this, having an initial value.</p> Signup and view all the answers

What is the role of the server in BugsWorld?

<p>Keeps track of 'the world' and processes client requests.</p> Signup and view all the answers

What is the role of the client in BugsWorld?

<p>Each client simulates creature (bug) behavior for all creatures of one species.</p> Signup and view all the answers

What do displays show in BugsWorld?

<p>The current state of the world and some statistics about the simulation.</p> Signup and view all the answers

What are the 3 parts of a compiler?

<p>Tokenizer, Parser, Code Generator.</p> Signup and view all the answers

What is an Abstract Syntax Tree (AST)?

<p>A tree model of an entire program or certain program structure.</p> Signup and view all the answers

What is a statement in the context of ASTs?

<p>A component family which allows manipulation of ASTs for BL statements.</p> Signup and view all the answers

What are the 5 kinds of statements?

<p>Block, If, While, If_Else, Call.</p> Signup and view all the answers

You can use == to test equality of enums?

<p>True</p> Signup and view all the answers

What is an Enumeration (Enum)?

<p>A construct that allows the use of meaningful symbolic names instead of arbitrary int variables.</p> Signup and view all the answers

What is a statement no-arg constructor?

<p>this = compose((BLOCK, ?, ?), ).</p> Signup and view all the answers

What is a program in the context of BL?

<p>A component family which allows manipulation of values modeling complete BL programs.</p> Signup and view all the answers

What are the 3 components of a program model?

<p>Name, context, body.</p> Signup and view all the answers

What is refactoring?

<p>Restructuring code without changing its behavior for the purpose of improving readability.</p> Signup and view all the answers

What is a Context-Free Grammar (CFG)?

<p>A set of formation rules for strings in a language that satisfies certain technical conditions.</p> Signup and view all the answers

What is a Recursive-Descent Parser?

<p>An algorithm to parse a BL program and construct the corresponding Program object.</p> Signup and view all the answers

What are terminal symbols?

<p>Symbols that terminate writing; when hit, stop writing.</p> Signup and view all the answers

What are non-terminal symbols?

<p>Symbols that only appear on the left side of a production.</p> Signup and view all the answers

What is a metagrammar?

<p>Used to define the context-free grammar itself.</p> Signup and view all the answers

What is a derivation?

<p>A sequence of specific rewrite-rule applications that begins with the start symbol.</p> Signup and view all the answers

What is ambiguity in the context of CFG?

<p>When some strings in the language have more than one derivation tree.</p> Signup and view all the answers

What is a token?

<p>A single entity in the language.</p> Signup and view all the answers

The purpose of a tokenizer is to transform source code into machine/object code?

<p>False</p> Signup and view all the answers

The purpose of a tokenizer is to remove whitespace and separate the source code into small, meaningful units?

<p>True</p> Signup and view all the answers

The purpose of a tokenizer is to construct an abstract representation of a program?

<p>False</p> Signup and view all the answers

What does a BL tokenizer do?

<p>Treats string of consecutive whitespace characters as separators between tokens.</p> Signup and view all the answers

What are the two main uses of CFGs?

<p>To generate strings in the language and detect if a string is in the language.</p> Signup and view all the answers

What is parsing?

<p>Going from a string to its derivation tree/AST.</p> Signup and view all the answers

What are the 5 rules of a recursive-descent parser?

<p>One parse/method/non-terminal symbol, non-terminal symbol on RHS of rule calls parse method, terminal symbol on RHS consumes token, '|' indicates 'if-else', '{ }' indicates 'while'.</p> Signup and view all the answers

What do CFG symbols { } indicate?

<p>They indicate that the enclosed sequence of symbols can occur 0+ times.</p> Signup and view all the answers

How does the parser evaluate an arithmetic expression?

<p>By turning the string of tokens to the value of that expression as an int.</p> Signup and view all the answers

What is an expression?

<p>It starts with a term followed by 0+ add-ops and terms.</p> Signup and view all the answers

What is a term?

<p>It starts with a factor followed by 0+ mult-ops and factors.</p> Signup and view all the answers

What is a factor?

<p>It starts with '(' followed by an expression and ends with ')', or it is a number token.</p> Signup and view all the answers

What are the 2 facts recognized by modern software?

<p>Modern software consists of potentially large number of components, and a class is a component with its client-visible specifications in the interface it implements.</p> Signup and view all the answers

How many interfaces can an interface extend?

<p>One or more.</p> Signup and view all the answers

Can an interface be generic?

<p>True</p> Signup and view all the answers

What contains a description of WHAT the software does?

<p>The interface.</p> Signup and view all the answers

What contains a description of HOW the software does it?

<p>The class.</p> Signup and view all the answers

What can interfaces define?

<p>Instance methods and static final variables.</p> Signup and view all the answers

What can't interfaces define?

<p>Constructors, instance variables, and static methods (with exceptions in Java 8).</p> Signup and view all the answers

All instance methods in an interface are automatically public abstract?

<p>True</p> Signup and view all the answers

Is it usual for an interface to define variables?

<p>False</p> Signup and view all the answers

Are constructors instance methods?

<p>False</p> Signup and view all the answers

What does Kernel Interface define?

<p>Mathematical model, contracts for constructors, methods, and methods from Java library interfaces.</p> Signup and view all the answers

What does Enhanced Interface define?

<p>Contracts for all other methods for the type.</p> Signup and view all the answers

Kernel methods should be a __________ set of __________ that is __________.

<p>minimal, methods, functionally complete</p> Signup and view all the answers

What is a functionally complete set of kernel methods powerful enough to do?

<p>To give variable of the type any allowable value, determine the value of a variable, implement 'equals' and 'toString', and check every kernel method's precondition.</p> Signup and view all the answers

What is circularity in interfaces?

<p>Interface A extends something of general type interface B, and interface B extends interface A.</p> Signup and view all the answers

A Java interface defines a ______ ____ along with its set of ________ ________.

<p>type name, instance methods</p> Signup and view all the answers

An interface type may be used in Java even if there is no implementation of it in scope?

<p>True</p> Signup and view all the answers

Interfaces are ______- constructs.

<p>compile-time</p> Signup and view all the answers

After a Java program compiles, object types are kept at ______- constructs.

<p>run-time</p> Signup and view all the answers

What is a declared (static) type?

<p>Interface type (left side).</p> Signup and view all the answers

What is an object (dynamic) type?

<p>Class type (right side).</p> Signup and view all the answers

The declared type of a variable may be an interface type?

<p>True</p> Signup and view all the answers

The object type can be an interface type?

<p>False</p> Signup and view all the answers

What happens if the declared type is an interface type?

<p>The object type (a class) must implement the declared type.</p> Signup and view all the answers

What happens to declared types once a Java program compiles?

<p>They disappear in the JVM.</p> 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.

Quiz Team

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!

More Like This

Untitled
22 questions

Untitled

ProblemFreeGalaxy avatar
ProblemFreeGalaxy
Clase Abstracta y Herencia en Programación
24 questions

¿Qué es una Clase Abstracta en Java? Prueba tu conocimiento con este q...

MatchlessAstatine avatar
MatchlessAstatine
Abstract Class Overview in Programming
9 questions

Abstract Class Overview in Programming

RapturousSunflower avatar
RapturousSunflower
Classe Abstraite en Programmation
10 questions

Classe Abstraite en Programmation

MesmerizingDragon1965 avatar
MesmerizingDragon1965
Use Quizgecko on...
Browser
Open
Browser
Browser