CSE 2231 Midterm 2 Stuff

Heap

A binary tree of T that satisfies two properties:
- Global shape property: it’s a complete binary tree
- Local ordering property: the label in each node is “smaller than or equal to” the label in each of its child nodes

Complete Binary Tree

A binary tree in which all levels are “full” except possibly the bottom level, with any nodes on the bottom level as far left as possible Z

HeapSort

A heap can be used to represent the values in a SortingMachine, as follows:
- In changeToExtractionMode, arrange all the values into a heap
- In removeFirst, remove the root, and adjust the slightly mutilated heap to make it a heap again

SiftDown Algorithm

1. Remove the root

2. Find the right most element in the bottom of the heap (last element in the array)

3. Promote that element to the root of the heap

4. Look at the two children, find the smallest of the two, then check to see if the root is less than or equal to or greater than or equal to

5. From there, sift down and repeat

Heapify

Makes a complete binary tree into a heap

Fixed Size

means the size/length of a collection is “inflexible”, in other words it is determined at initialized of the collection and cannot be incrementally adjusted
- synonym is static, this term unfortunately means other things in java

Dynamic Size

means the size/length of a collection is “flexible”, in other words it can be incrementally adjusted by “adding” and “removing” entries

Direct Access

means the entries of a collection may be accessed by providing an int position/index of any entry in the collection

Sequential Access

means the entries of a collection may be accessed in increasing order of position by accessing the “next” entry in the collection

Singly Linked List

A sequence of nodes where each node stores data and a link (or reference) to the next node in the list, called a singly because each node only knows about the next node, not the previous

Node Class

A … class is declared as a nested class inside the kernel implementation that uses it in a data representation of a linked list

Smart Node

A special node at the front of a linked list that doesn’t store real data, it just makes the list operations simpler and more consistent. also referred to as a dummy or sentinel node

advance

Advances the position in this by one

Moving a pointer or reference from the current node to the next node in the list

retreat

Retreats the position in this by one

Moving a pointer or reference from the current node to the previous node in the list

Doubly Linked List

A sequence of nodes where each node stores data and a link (or reference) to the next node in the list as well to the previous

Tree

A … can be thought of as a structure comprising of zero or more nodes, each with a label of some mathematical type, say T, called the label type

Is either:
- the empty tree which has no nodes
- a non-empty tree, which consists of a root node and a string of subtrees of the root

Tree newSequenceOfTree

Creates and returns an empty Sequence<Tree<T>> of the dynamic type needed in assemble and disassemble

Tree assemble

assembles in this a tree with root label root and subtrees children

Tree disassemble

disassembles this into its root label, which is returned as the value of the function, and subtrees in children.

Tree addSubtree

Adds st at position pos in the subtrees of this

Tree removeSubtree

Removes and returns the subtree at position pos of this

Tree numberOfSubtrees

Reports the number of subtrees of the root of this

BugsWorld Simulator

The BugsWorld game is played on a system consisting of:
- Server
- Clients
- Displays

Server

Keeps track of “the world”, processes client requests, resolves conflicts.

Clients

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

Displays

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

BL Compiler

Consists of:
- Tokenizer
- Parser
- Code Generator

Abstract Syntax Tree

A tree model of an entire program or a certain “program structure”

“Abstract” in the sense that some of the characters used in the “concrete” program text do not appear in the AST

AST Node Labels

An AST for BL is a tree of…what?
Each node has some kind of the following:
- The kind of statement (BLOCK, WHILE)
- The test condition (NEXT_IS_EMPTY, TRUE)
- The call of an instruction (infect, move), realizing that this may be an instruction defined elsewhere in the program

Statement

Allows you to manipulate values that are ASTs for BL statements

mathematical model of a … is a tree of STATEMENT_LABEL

Enumerations

Java has a special construct, enum, that easily allows you to use meaningful, symbolic names where you might otherwise be inclined to declare int variables and give them arbitrary values to participate just in equality tests

Statement No Argument Constructor

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

Statement Kind

Reports the kind of statement this is

Statement addToBlock

Adds the statement s at position pos in this BLOCK statement

Statement removeFromBlock

Removes and returns the statement at position pos of this BLOCK statement

Statement lengthOfBlock

Reports the number of statements in this BLOCK statement

Statement assemble

Depending on the type of condition, assembles in this a statement with root label (Type of condition, condition, ?) and only subtree the BLOCK s

Statement disassemble

Depending on the type of condition, disassembles the Type of Condition statement this into its test Condition, which is returned as the value of the function, and its only subtree, the BLOCK statement s

Program

Allows you to manipulate values that are models of complete BL programs

The mathematical model of a … includes that of a Statement (Specifically a BLOCK) for its body, plus:
- the program name
- the new user-defined instructions, each of which also has a body

Program No-argument Constructor

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

Program name

Returns the name of this

Program setName

Replces the name of this with n

Program newContext

Creates and returns an empty Map<String, Statement> of the dynamic type needed in swapContext

Program swapContext

Exchanges the context of this with that of c; c must have the dynamic type returned by newContext

Program newBody

Creates and returns a Statement with a default initial value, of the dynamic type needed in swapBody

Program swapBody

Exchanges the body of this with that of b; b must have the dynamic type returned by newBody

Context Free Grammar

used to specify syntactically valid BL programs

use the grammar to implement a recursive descent parser

Rewrite Rule

describes how strings in the language may be formed

Non Terminal Symbol

A placeholder in a grammar that can be replaced by other symbols or groups of symbols according to the grammar’s rules

Represents a category that still needs to be broken down into smaller during parsing

Start Symbol

Non terminal symbol in the first rewrite rule

Terminal Symbol

A symbol in grammar that cannot be broken down any further — it appears directly in the final program or input

Derivation

A … of a string of terminal symbols consists of a sequence of specific rewrite rule applications that begin with the start symbol and continue until only terminal symbols remain

Tokenizer

The job of this is to transform a string of characters into a string of tokens

Parsing

Generally refers to this last step, going from a string to its derivation tree or for programming language perhaps to an AST for the program

{} (parsing)

Signifies a while loop

| (parsing)

Signifies an if-else statement