Exam 1 Flashcards
Reversed Card
A formula in which some number in a sequence depends on the previous numbers in a sequence.
What is a recurrence relation?
How does a skip list search work?
A search proceeds along the list with the greatest span until two references are found that enclose the required key. Then the search proceeds at the next level down until the required key found, or is deemed to be not present.
Reversed Card
LIFO
Stacks are sometimes known as ______ lists.
What is the findMin algorithm?
- FindMin(BinaryNode t)
- if(t==null) return null;
- if(t.left==null) return t;
- return findMin(t.left);
What is the Preorder traversal algorithm?
- DFSPre(Node X)
- If(X!=null)
- Do Work at Node
- DFSPre(x.left)
- DFSPre(x.right)
- If(X!=null)
Reversed Card
it allows GenericClass m = new GenericClass(); to be written simply as GenericClass m = new GenericClass<>();
What does the diamond operator do?
What four methods make up the simplest linked list interface?
Addathead
RemoveAtHead
Clear
isEmpty
How much space does merge sort require?
2n
Reversed Card
One takes only an object as an argument
One takes an object and a nextNode as arguments
When making a linked list, we use two constructors, what are their differences?
What a wrapper class?
A data type that stores a primitive type and adds extra functionality and methods to be used on the primitive type.
What is the PostOrder traversal algorithm?
- DFSPost
- If(X!=null)
- DFSPost(x.left)
- DFSPost(x.right)
- Do work
- If(X!=null)
Reversed Card
Finding the insertion point.
What is the first step to doing an insertion or deletion in a probabilistic skip list?
Classes that extend the iterable interface can implement what?
The enhanced for loop.
Reversed Card
- Guess the result and prove it by induction.
- Expand the recurrence by repeatedly substituting it into itself.
- The general solution method.
What are the three main ways to solve recurrence relations?
Reversed Card
An amortized runtime means that the runtime could be as large as O(n), but if m consecutive calls are made to the member functions, the runtime is MO(logN).
What is amortized runtime?
Reversed Card
It enables additions and deletions at either end of the list.
How is a deque different?
What is the linear time algorithm for the positive max subsequence problem?
Public static int maxsubsum(int[] a)
Int max sum = 0, this sum =0;
For (int I =0, I < a.length, i++)
Thissum += a[i];
If(thissum > maxsum ) maxsum = thissum;
Else if (thissum < 0) thissum = 0;
Return maxsum;
What are the two modes of insert in a red-black tree?
Top down insert and bottom up insert
Reversed Card
Reading the data (from disk)
When using an efficient algorithm, what is generally the bottleneck?
Reversed Card
A perfect binary tree of all black nodes.
What is embedded in every Red-Black tree?
What is a doubly linked list?
A list in which every node maintains a link to its previous and next node.
What is the suggested probabilistic variable value for a probabilistic skip list?
.25
Reversed Card
2n+2
What is the T(n) of a for loop from 1-n?
Reversed Card
When the work at a ndoe is performed before its children are processed.
What is preorder traversal?
What is autoboxing/ unboxing?
Compiler features that allow primitive types to be passed as wrapper classes and vice versa.
What is a full binary tree?
A tree in which every node, other than the leaves, has two children.
Reversed Card
sqrt(N)
What is the average depth of a binary tree?
Reversed Card
return root == null;
What is the IsEmpty algorithm?
Reversed Card
one in which the numbers are in the sequence are a product of the previous number and some k.
What is a geometric recurrence?
Reversed Card
A tree with the lowest amount of nodes needed to obtain a tree of height h.
What is a skinny AVL tree?
What does returning a value count as for time complexity?
One unit to return.
When we are speaking of trees, N always represents what?
How are nested loops analyzed?
inside out; the total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the loops.
What is the wild card operator?
?
What is the recursive maxim?
“Don’t compute anything more than once.”
Reversed Card
An in order traversal is used
What kind of traversal is used to evaluate an expression tree?
Reversed Card
Path length = 0.
What is the path length from every node to itself?
What is the first and most crucial thing we do when creating Binary search tree functions?
Test for an empty tree first.
Reversed Card
depth = 0.
What is the depth of the root?
What are the four fundamental rules of recursion?
- You must have some base case that can be solved without recursion.
- The recursive call must always be with a case that makes some progress toward the base case.
- Assume that all recursive calls work.
- Never duplicate work by solving the same instance of a problem in a recursive call.
Reversed Card
?
What is the wild card operator?
What kind of list is required for a sufficient implementation of a deque?
A doubly linked list.
Reversed Card
- Contains(x, BinaryNode t)
- if(t == null) return false;
- if(x.compareTo(t.Object) < 0) return contains(x, t.left);
- if(x.compareTo(t.Object) > 0) return containts(x, t.right);
- else return true;
What is the contains algorithm?
Reversed Card
A tail node, insert at tail, remove at head
What extra variable and operations are used in a queue?
Stacks are sometimes known as ______ lists.
LIFO
Every red black tree with N nodes has a height less than or equal to what?
2log2(n+1)
Reversed Card
They are not necessarily adjacent.
What can be said about the nodes of a linked list’s position in memory?
Reversed Card
Log A + Log B
Log(A*B) = ?
What is the T(n) of a for loop from 1-n?
2n+2
Reversed Card
the current partition to be sorted drops below 25 (approximately).
The most efficient implementations of QuickSort revert to Insertion Sort when
Reversed Card
O(log N) this is worst
What is the worst case tree height of an AVL tree?
Reversed Card
this is the case that two Insertion took place in the right subtree of the right child.
Let x be the out of balance node, and k be the key that was inserted what is the case that x.rightChild.value < k ?
Reversed Card
1 unit to initialize i, n+1 units for comparisons, and n units for all increments.
What is a for loops cost?
What is the runtime of all operations in an AVL tree when lazy deletion has not occured?
O(log N)
Reversed Card
get, set, add, remove, isempty, clear, size, and capacity increase.
What are the ArrayList’s 8 basic operations?
What is the Euclid algorithm?
Long(long m, long n)
while(n!=0)
long rem = m % n;
m = n;
n = rem;
return m;
What is the time complexity of Euclids algorithm?
O(logn), solved by noticing that after two iterations the remainder is less than n/2.
What are the four fundamental properties of Red-Black Trees?
- Every node is either red or black.
- The root of the tree is black.
- A red node must have no children or exactly two black children.
- Every path from a node x to a descendent null-link must have the same number of black nodes.
Reversed Card
Get and Set take constant time.
What is the advantage of the built in ArrayList?
What is the advantage of the built in ArrayList?
Get and Set take constant time.
The minimum number of nodes in an AVL tree of height h is given by what recurrence relation?
S(h) = S(h-1) + S(h-2) + 1
Reversed Card
Recursion.
What is commonly used when writing the operations of a Binary search tree?
Let x be the out of balance node, and k be the key that was inserted what is the case that x.leftchild < k < x.value?
this is the case that insertion took place in the right subtree of x’s left child.
Reversed Card
Primitive types, Wrapper classes must be used.
What type of objects cannot be used in place of generic type parameters?
What part of the java library includes an implementation of common data structures?
The java collections API
What are skip lists made of?
Ordered Linked Lists
Reversed Card
inside out; the total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the loops.
How are nested loops analyzed?
If an outer class is called outer, what is the implicit reference to the outer class object that created the inner class called?
outer.this
What is the average depth of a binary tree?
sqrt(N)
Reversed Card
When the work at a node is done after its children have been evaluated.
What is postorder traversal?
What are the two steps for proving something by induction?
The first step is proving a base case, that is, showing the theorem is true for some small value.
It is shown that if k is true, the theorem must also be true for k+1.
What is the time unit of a simple operation or assignment?
One time unit.
What is the length of a path?
The number of edges on the path, namely k-1 if k are the nodes of the path.
Reversed Card
The unbalanced node’s child is swapped with the unbalanced node’s grandchild.
What happens first in a double rotation?
Describe the “model” computer that is used for time complexity analysis
- simple instructions: addition, multiplication, comparison, and assignment
- takes exactly one time unit to do any simple instruction.
- has infinite memory
What is a recurrence relation?
A formula in which some number in a sequence depends on the previous numbers in a sequence.
What is the algorithm for fast exponentiation?
Long power(long a, int b)
if(b == 0) return 1;
if(b == 1) return a;
if(b%2 == 0) return power(a*a, b/2);
else return power(a*a, b/2)*a;
Reversed Card
if(head is null) head = new Node(x, head)
else:
if(head>x) head = new Node(x, head)
else:
Node prev = head;
Node ref = head.next;
while(ref!=null && ref.val > x) move prev and ref up
prev.setNext(new Node(x, ref));
What is the insertInorder Algorithm?
Reversed Card
Nested inside of the Binary tree class.
Where is the binary node class usually located?
Reversed Card
The worst case time complexity.
What is generally the quantity searched for when analyzing an algorithms runtime?
If an array is ever used to implement a list, what must we keep track of?
The front and end indices, and the size.
Reversed Card
A height variable.
What extra information do AVLNodes have that BSTNodes do not?
What is amortized runtime?
An amortized runtime means that the runtime could be as large as O(n), but if m consecutive calls are made to the member functions, the runtime is MO(logN).
What is the path from nodes N1 to Nk?
A sequence of nodes such that leads from n1 to nk
Reversed Card
B*Log(A)
Log(AB) = ?*
What are the add and remove operations called in a queue?
Enqueue, dequeue
What two implementations are there of the built in List interface?
ArrayList, and LinkedList
Reversed Card
A list in which 50% of nodes have just one reference, 25% have just two, etcetera.
What is a probabilistic skip list?
Xn + Xn = ?
2Xn
What is a probabilistic skip list?
A list in which 50% of nodes have just one reference, 25% have just two, etcetera.
Reversed Card
An arbitrary number, possibly zero.
A tree that is not binary may have how many children?
What is a perfect binary tree?
A full binary tree in which all the leaves are at the same depth or level.
Reversed Card
the running time of the test plus the larger of the running times of either statement.
What is the runtime of an if/else statment?
What is Euclid’s algorithm used for?
Finding the GCD of two numbers.
What are the AVL tree properties?
- Abides by the Binary search tree property.
- The heights of the left and right subtrees of any node differ by no more than 1.
Reversed Card
rotate with left child
What function is called when Insertion took place in the left subtree of the left child of X(out-of-balance node).
Reversed Card
The type of object that will replace the parameter type.
When instantiating a class, what goes inside of the angle brackets?
Reversed Card
When the division into regions of size equal to powers of two is maintained.
When can insertion and deletion in a skip list take O(N)?
A rotate with left child causes the Node X to replace it’s left child with what?
The left child’s right subtree.
Reversed Card
A list in which insertion is done at one end and removal is done at the other end.
What is a queue?
What is the runtime of an if/else statment?
the running time of the test plus the larger of the running times of either statement.
What extra information do AVLNodes have that BSTNodes do not?
A height variable.
Reversed Card
For every node X in the tree, the values of all the items in its left subtree are smaller than teh item in X, and values of all the items in its right subtree are larger than the item in X.
What is the Binary search tree property?
Reversed Card
The length of the longest path from the root to a leaf.
What is the height of a tree?
Reversed Card
If Logx B = a
Xa = B if and only if what?
Reversed Card
The information saved on a stack when a method is called and the registers must be cleared.
What is a stack frame, or activation record?
When using an efficient algorithm, what is generally the bottleneck?
Reading the data (from disk)
Reversed Card
A postorder traversal.
What kind of traversal is used to convert an expression tree into a postfix expression?
Collections add or remove return what?
True or false.
Reversed Card
O(logn), which is given by the number of multiplications computed.
What is the runtime of fast exponentiation?
Reversed Card
An object, NOT a node.
What does the remove from head function return?
What is a full binary tree sometimes called?
A proper tree, or a 2 tree.
Reversed Card
A perfect Binary tree.
A Red-Black tree where all nodes are black is what?
Reversed Card
The front and end indices, and the size.
If an array is ever used to implement a list, what must we keep track of?
What is the new size of an ArrayList after capacity expansion?
2(size) + 1
Reversed Card
log_(1/p)(n) where p is the probability fraction one has chosen.
How is the maximum level a probabilistic skip list chosen?
How does merge sort work?
sorts an array by partitioning the array into blocks of size one, then pairs of these are merged into blocks of size 2 values, then pairs of those blocks are merged into size four. This behavior continues until the entire array is enclosed in a single block.
How can we determine the relative growth of two functions f(n) and g(n)?
In a tree, the root of each subtree is said to be what?
A child of the whole tree’s root.
What are not compatible with the Object data type?
Primitive types are not compatible.
How many rotations maybe required to restore the balance condition of an AVL tree?
Only one rotation is ever needed.
What is the runtime of adding an removing from a linked list?
O(1), it is constant.
Reversed Card
references to the nodes with the smallest and larges elemetns in a tree or subtree.
What do findMin and FindMax return?
Reversed Card
The height of the left and rigth subtrees of any node can differ by no more than 1.
What is the AVL tree balance condition?
What is an Abstract Data Type?
a set of objects together with a set of operations.
A binary tree consists of what?
A root and two subtrees, both of which could be empty.
Reversed Card
By downcasting the object to the proper type.
How can a generic object of Object type be accessed and used properly?
What do findMin and FindMax return?
references to the nodes with the smallest and larges elemetns in a tree or subtree.
The GCD of three or more positive numbers is equal to what?
the product of the prime factors common to all of the integers.
Reversed Card
The directory structure is a popular application.
What is a popular application of trees in operating systems?
Reversed Card
To the base case.
All recursive functions must eventually reduce to what?
Reversed Card
A double rotation.
What restores the balance from an inside insertion?
What is the least common multiple algorithm?
- Break each number down into its prime numbers.
- Multiply together each factor the greatest number of times it occurs in any of the numbers.
- The product is the LCM.
What is generally considered an error in the stack adt?
A pop or peek on an empty list.
What is a type bounds?
it specifies the properties that the parameter types must have and goes inside of the angle brackets after the type parameter.
Reversed Card
The node is a unary operator, such as a unary minus (negative)
What does it mean if a node has only one child in an expression tree?
Reversed Card
A doubly Linked List.
What kind of implementation is the built in Linked List?
the running time of all operations in a binary search tree is what?
O(d) where d is the depth of the node containing the accessed item.
Reversed Card
- BinaryNode Insert(x, BinaryNode t)
- if(t==null) return new BinaryNode(x, null, null);
- int compare = x.compareTo(t.element);
- if(compare < 0) t.left = insert(x, t.left)
- else if(compare > 0 ) t.right = insert(x, t.right);
- else do nothing;
- return t;
What is the binary tree insertion algorithm?
Reversed Card
2(size) + 1
What is the new size of an ArrayList after capacity expansion?
What is the double rotate with left child algorithm?
- DoubleRotateWLeft(Node x)
- x.left = rotateWRight(x.left);
- Return rotateWithLeftChild(x);
Reversed Card
“Don’t compute anything more than once.”
What is the recursive maxim?
How is the maximum level a probabilistic skip list chosen?
log_(1/p)(n) where p is the probability fraction one has chosen.
Reversed Card
A collection of nodes that is either empty or consists of a distinguished root node and zero or more subtrees each of whose roots are connected by a directed edge from r.
What is a tree?
Reversed Card
- DoubleRotateWLeft(Node x)
- x.left = rotateWRight(x.left);
- Return rotateWithLeftChild(x);
What is the double rotate with left child algorithm?
What is the height of an empty AVL tree defined as?
height = -1
Reversed Card
- FindMin(BinaryNode t)
- if(t==null) return null;
- if(t.left==null) return t;
- return findMin(t.left);
What is the findMin algorithm?
A rotate with right child causes the Node X to become what
It’s right child’s left subtree.
What is the diamond operator?
<>
Reversed Card
When n < 25.
When is insertion sort generally faster?
Reversed Card
outer.this
If an outer class is called outer, what is the implicit reference to the outer class object that created the inner class called?
Reversed Card
2n
How much space does merge sort require?
Reversed Card
Top down insert and bottom up insert
What are the two modes of insert in a red-black tree?
What is an AVL tree?
A balanced search tree where the heights of the left and right subtrees of any node differ by no more than 1.
What should the last node in a linked list always point to?
null.
Reversed Card
Any node other than a null link.
In a Red-Black tree, an internal node is considered to be what?
Reversed Card
O(N)
What is the runtime of operations that must search linked lists?
Reversed Card
It goes in angle brackets after the class name.
When creating a generic class, where does a generic type parameter go?
How is a proof by contradiction done?
A statement is assumed false, it is then shown that this assumption implies that some known property is false.
Reversed Card
sorts an array by partitioning the array into blocks of size one, then pairs of these are merged into blocks of size 2 values, then pairs of those blocks are merged into size four. This behavior continues until the entire array is enclosed in a single block.
How does merge sort work?
We say that A is congruent to B modulo N, if
N divides A - B, this intuitively means that the remainder is the same when N divides either A or B.
All insertions in a red black tree create a new what?
A new red node with null links.
In a Red-Black tree, an internal node is considered to be what?
Any node other than a null link.
How do we prove the property of the worst case height of an AVL tree to be O(log N)?
We construct the AVL tree of height h that contains the fewest nodes, we call these the skinniest AVL trees.
We deduce a recurrence relation for the minimum number of nodes in an AVL tree of height h.
We solve this recurrence relation and then rearrange the result to get an equation for the maximum height of an AVL tree with N nodes.
Reversed Card
Nodes without children.
What are leaf nodes?
Reversed Card
An if/else statement in the else of an outer if/else statement.
What is the structure of the InsertInOrder algorithm for a linked list?
What restores the balance from an inside insertion?
A double rotation.
Reversed Card
a reference that is assigned to the left or right child of the current node. i.e. t.right = insert(x, t.right);
Each recursive call to insert returns what?
Each recursive call to insert returns what?
a reference that is assigned to the left or right child of the current node. i.e. t.right = insert(x, t.right);
Reversed Card
The left child’s right subtree.
A rotate with left child causes the Node X to replace it’s left child with what?
Xa = B if and only if what?
If Logx B = a
If a tree has N nodes, how many edges does it have?
N-1
What does the delete function do if a value is not found?
It does nothing.
Reversed Card
The first step is proving a base case, that is, showing the theorem is true for some small value.
It is shown that if k is true, the theorem must also be true for k+1.
What are the two steps for proving something by induction?
Reversed Card
- Break each number down into its prime numbers.
- Multiply together each factor the greatest number of times it occurs in any of the numbers.
- The product is the LCM.
What is the least common multiple algorithm?
Reversed Card
printList, makeEmpty
What are some popular but not required linked list operations?
Reversed Card
Anywhere in the class where the type of an object can be anything.
Where is the parameter type used in a class definition?
What does it mean if a node has only one child in an expression tree?
The node is a unary operator, such as a unary minus (negative)
Reversed Card
LinkedList
Node
What are the minimal two classes needed to implement a linked list?
Reversed Card
The parent node sets its child node to its grandchild.
How is a node with one child deleted?
Reversed Card
MO(logN)
What is the runtime of find, insert, and delete in a skip list?
Reversed Card
An insertion took place in the right subtree of teh rigth child, or the left subtree of the left child.
What is meant by an outside insertion?
What are the two most commonly used methods for proving statements in data structure analysis?
Proof by induction, and proof by contradiction.
Why must we use the static keyword when nesting a class inside of a class?
To allow the nested class to use the members of the outer class.
What are the two special cases dealt with first in most list operations?
Head is Node,
List is Empty.
Reversed Card
2n+1
2n + 2n = ?
Reversed Card
this is the case that insertion took place in the left subtree of the right child.
Let x be the out of balance node, and k be the key that was inserted what is the case that x.value < k < x.rightChild.value?
Reversed Card
- You must have some base case that can be solved without recursion.
- The recursive call must always be with a case that makes some progress toward the base case.
- Assume that all recursive calls work.
- Never duplicate work by solving the same instance of a problem in a recursive call.
What are the four fundamental rules of recursion?
When is using an inner class useful?
when each inner class object is associated with exactly one instance of an outer class object.
What can be said about the nodes of a linked list’s position in memory?
They are not necessarily adjacent.
What is the essential class variable of the Linked List class?
the head node
Reversed Card
Enqueue, dequeue
What are the add and remove operations called in a queue?
Reversed Card
Linked lists are used to implement these data structures.
What data structure is used to implement stacks, queues and deques?
What is the Binary search tree property?
For every node X in the tree, the values of all the items in its left subtree are smaller than teh item in X, and values of all the items in its right subtree are larger than the item in X.
Why does deletion cause the average runtime of O(log N) to not always hold?
Because deltion will always faovr making one sides subtree shorter, therefore making all insertion sequences no longer equally likely.
Reversed Card
A binary search tree with a balance condition.
What is an AVL Tree?
Reversed Card
The number of edges on the path, namely k-1 if k are the nodes of the path.
What is the length of a path?
How is a deque different?
It enables additions and deletions at either end of the list.
Reversed Card
A recursive call at the last line of a method, and an example of bad recursion.
What is tail recursion?
Reversed Card
the product of the prime factors common to all of the integers.
The GCD of three or more positive numbers is equal to what?
How is a generic array created?
(Anytype []) new Object[];
What is the structure of the InsertInOrder algorithm for a linked list?
An if/else statement in the else of an outer if/else statement.
When making a linked list, we use two constructors, what are their differences?
One takes only an object as an argument
One takes an object and a nextNode as arguments
When implementing recursion, what ADT is usually used?
A stack
What is the runtime of operations that must search linked lists?
O(N)
What is generally the quantity searched for when analyzing an algorithms runtime?
The worst case time complexity.
What is a for loops cost?
1 unit to initialize i, n+1 units for comparisons, and n units for all increments.
Reversed Card
Object element
Node next
What two data members make up a linked list node?
How can Euclids algorithm be used for finding the GCD of 3 or more positive numbers?
by repeatedly taking the GCDs of pairs of numbers: gcd(gcd(a, b), c)
Reversed Card
<>
What is the diamond operator?
Reversed Card
an algorithm that can correctly give an answer for the data it has read at any given time.
What is an online algorithm?
Reversed Card
A sequence of nodes such that leads from n1 to nk
What is the path from nodes N1 to Nk?
Reversed Card
O(nlogn).
What is the average case time complexity of quicksort?
Reversed Card
A function that is defined in terms of itself.
Waht is a recursive function?
What does a collection do?
stores identically typed objects
What can a red node never have?
A red node can never have a red child, or just one child.
What are the three cases which the delete algorithm must address?
- Deleting a leaf Node.
- Deleting a node with one child.
- Deleting a node with two children.
Reversed Card
Finding the GCD of two numbers.
What is Euclid’s algorithm used for?
What is a tree?
A collection of nodes that is either empty or consists of a distinguished root node and zero or more subtrees each of whose roots are connected by a directed edge from r.
Waht is a recursive function?
A function that is defined in terms of itself.
Reversed Card
It’s right child’s left subtree.
A rotate with right child causes the Node X to become what
Reversed Card
O(log N)
What is the average depth of a binary search tree?
Reversed Card
Test for an empty tree first.
What is the first and most crucial thing we do when creating Binary search tree functions?
What does the remove from head function return?
An object, NOT a node.
Reversed Card
The sum of the depths of all nodes in a tree.
What is the intenal path length?
What is the InOrder Traversal Algorithm?
- DFSIn(Node X)
- If(X!=null)
- DFSIn(x.left);
- Do work
- DFSIn(x.right);
- If(X!=null)
Reversed Card
Proof by induction, and proof by contradiction.
What are the two most commonly used methods for proving statements in data structure analysis?
What is the insertInorder Algorithm?
if(head is null) head = new Node(x, head)
else:
if(head>x) head = new Node(x, head)
else:
Node prev = head;
Node ref = head.next;
while(ref!=null && ref.val > x) move prev and ref up
prev.setNext(new Node(x, ref));
What is the divide and conquer strategy?
split the problem into two roughly equal subproblems, which are then solved recursively and then patched together.
What is lazy deletion?
When nodes have a deleted marker that is turned on when they are deleted.
A rotate with left child causes the Node X to become what?
It’s left child’s right subtree.
What is a skinny AVL tree?
A tree with the lowest amount of nodes needed to obtain a tree of height h.
Reversed Card
Keep a record of frequency in each node and update it when a duplicate is added or removed.
What is one way to handle a tree that will have duplicates inserted?
What is the runtime of find, insert, and delete in a skip list?
MO(logN)
Reversed Card
The java collections API
What part of the java library includes an implementation of common data structures?
Reversed Card
N-1
At worst case, a binary tree can have a depth of what?
Reversed Card
O(d) where d is the depth of the node containing the accessed item.
the running time of all operations in a binary search tree is what?
Reversed Card
O(log N)
What is the runtime of all operations in an AVL tree when lazy deletion has not occured?
What is the path length from every node to itself?
Path length = 0.
Reversed Card
rotate with right
What function is called when Insertion took place in the right subtree of the right child?
Reversed Card
Object, left child, right child.
What are the variables of a BinaryNode?
Reversed Card
A tree in which no node can have more than two children.
What is a binary tree?
What does the structural condition of balance mean?
That no node is allowed to get too deep.
LogA B = ?
(Logc B)
(Logc A)
Reversed Card
A data type that stores a primitive type and adds extra functionality and methods to be used on the primitive type.
What a wrapper class?
Reversed Card
a set of objects together with a set of operations.
What is an Abstract Data Type?
What is the intenal path length?
The sum of the depths of all nodes in a tree.
Reversed Card
An edge from one directory node to the other.
In a path name, each slash indicates what?
What are the ArrayList’s 8 basic operations?
get, set, add, remove, isempty, clear, size, and capacity increase.
Reversed Card
- Abides by the Binary search tree property.
- The heights of the left and right subtrees of any node differ by no more than 1.
What are the AVL tree properties?
What time unit do declartions count for?
They count for no time unit.
Reversed Card
AddAtHead
RemoveAtHead
These two linked list operations are identical to a stack push and pop…
What is the rotateWithLeftChild() algorithm?
RotateWithLeft(Node n)
- Node leftPoint = n.left;
- n.left = leftPoint.right;
- leftPoint.right = n;
- n.height = Math.max(height(n.left), height(n.right)) + 1;
- leftPoint.height = Math.max(height(leftpoint.left), height(leftPoint.right)) + 1;
- Return leftPoint;
Reversed Card
An underlying array, the array capacity, and the current number of items in the array.
The ArrayList class contains what data variables?
Reversed Card
One unit to return.
What does returning a value count as for time complexity?
Reversed Card
Selection sort, bubble sort, insertion sort.
What are three examples of simple sorting algorithms?
Reversed Card
An extra operation for a stack that returns a value without popping the node at the head of the list.
What is the peek routine?
Reversed Card
split the problem into two roughly equal subproblems, which are then solved recursively and then patched together.
What is the divide and conquer strategy?
Reversed Card
the head node
What is the essential class variable of the Linked List class?
Let x be the out of balance node, and k be the key that was inserted what is the case that x.rightChild.value < k ?
this is the case that two Insertion took place in the right subtree of the right child.
When is an algorithm O(logn)?
when it takes constant time to cut the problem size by a fraction, usually 1/2.
What is an AVL Tree?
A binary search tree with a balance condition.
What fixes the balance after an outside insertion?
A single rotation
What happens first in a double rotation?
The unbalanced node’s child is swapped with the unbalanced node’s grandchild.
Reversed Card
When insertions and deletions occur throughout the list.
When is an array not a good option for a list?
Reversed Card
Base 2
In computer science, all logarithms are to what base?
What is commonly used when writing the operations of a Binary search tree?
Recursion.
Reversed Card
- simple instructions: addition, multiplication, comparison, and assignment
- takes exactly one time unit to do any simple instruction.
- has infinite memory
Describe the “model” computer that is used for time complexity analysis
Reversed Card
That no node is allowed to get too deep.
What does the structural condition of balance mean?
How can we determine the relative growth of two functions f(n) and g(n)?
Reversed Card
- Scan the infix expression from left to right.
- If the scanned character is an operand, output it.
- Else,
1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.) - If the scanned character is an ‘(‘, push it to the stack.
- If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
- Repeat steps 2-6 until infix expression is scanned.
- Print the output
- Pop and output from the stack until it is not empty.
What is the algorithm for converting an infix expression to postfix?
What is embedded in every Red-Black tree?
A perfect binary tree of all black nodes.
What are the three main ways to solve recurrence relations?
- Guess the result and prove it by induction.
- Expand the recurrence by repeatedly substituting it into itself.
- The general solution method.
Reversed Card
the running time of the statements inside the for loop multiplied by the number of iterations.
The running time of a for loop is at most what?
What is the base case of a recursive function?
It is the value for which the function is known without having to resort to recursion.
Reversed Card
A statement is assumed false, it is then shown that this assumption implies that some known property is false.
How is a proof by contradiction done?
What is the AVL tree balance condition?
The height of the left and rigth subtrees of any node can differ by no more than 1.
Reversed Card
Add and remove at head take constant time.
What is the advantage of a LinkedList over an ArrayList?
Reversed Card
Only one rotation is ever needed.
How many rotations maybe required to restore the balance condition of an AVL tree?
What kind of implementation is the built in Linked List?
A doubly Linked List.
What are the only two operations besides, peek, makeEmpty, and isEmpty, that you can do to a stack?
Pop, Push
Reversed Card
A single rotation
What fixes the balance after an outside insertion?
Reversed Card
True or false.
Collections add or remove return what?
Reversed Card
Pop, Push
What are the only two operations besides, peek, makeEmpty, and isEmpty, that you can do to a stack?
Reversed Card
N-1
If a tree has N nodes, how many edges does it have?
Reversed Card
A balanced search tree where the heights of the left and right subtrees of any node differ by no more than 1.
What is an AVL tree?
Reversed Card
the right childs left subtree.
A rotate with right child causes the Node X to replace it’s right child with what?
The most efficient implementations of QuickSort revert to Insertion Sort when
the current partition to be sorted drops below 25 (approximately).
When is an array not a good option for a list?
When insertions and deletions occur throughout the list.
What are leaf nodes?
Nodes without children.
How is a leaf node deleted?
The parent node’s child node is set to null.
Reversed Card
it divides at least one of the two numbers.
If a prime number N divides a product of two numbers, then
What is the height of a tree?
The length of the longest path from the root to a leaf.
Let x be the out of balance node, and k be the key that was inserted what is the case that K < x.leftChild.Value?
this is the case that insertion took place in the left subtree of x’s left child.
Reversed Card
RotateWithLeft(Node n)
- Node leftPoint = n.left;
- n.left = leftPoint.right;
- leftPoint.right = n;
- n.height = Math.max(height(n.left), height(n.right)) + 1;
- leftPoint.height = Math.max(height(leftpoint.left), height(leftPoint.right)) + 1;
- Return leftPoint;
What is the rotateWithLeftChild() algorithm?
Reversed Card
To pass functions as parameters.
What are function objects used for?
What is the average running time of most operations in a binary search tree?
O(logN)
Reversed Card
A child of the whole tree’s root.
In a tree, the root of each subtree is said to be what?
What does the contains function do?
It returns true if a node in tree T has item x, or false if not.
Reversed Card
The parent node’s child node is set to null.
How is a leaf node deleted?
When creating a generic class, where does a generic type parameter go?
It goes in angle brackets after the class name.
Trees are actually what?
Graphs
Log(AB) = ?*
B*Log(A)
What is an expression tree?
A tree in which the leaves are operands, such as constants or variable names, and the internal nodes contain operators.
What is the average case time complexity of quicksort?
O(nlogn).
Reversed Card
It becomes its right child’s left child.
When an outer insertion occurs to the right, what does the imbalanced node become?
What does the diamond operator do?
it allows GenericClass m = new GenericClass(); to be written simply as GenericClass m = new GenericClass<>();
Reversed Card
Primitive types are not compatible.
What are not compatible with the Object data type?
Reversed Card
When using a generic Collections, a wild card goes inside of the angle brackets after Collection along with the extends keyword to allow a class and any of its subclasses to be used in the collection.
When and for what are wildcards used?
Reversed Card
height = -1
What is the height of an empty AVL tree defined as?
What is the peek routine?
An extra operation for a stack that returns a value without popping the node at the head of the list.
Where is the binary node class usually located?
Nested inside of the Binary tree node.
What does an AVL tree ensure?
It ensures that the depth of a tree is O(log N)
What is the algorithm for converting an infix expression to postfix?
- Scan the infix expression from left to right.
- If the scanned character is an operand, output it.
- Else,
1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.) - If the scanned character is an ‘(‘, push it to the stack.
- If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
- Repeat steps 2-6 until infix expression is scanned.
- Print the output
- Pop and output from the stack until it is not empty.
What is the Big Oh time of a simple sorting algorithm?
O(N2)
What are the three variables of a treeNode?
Object element;
TreeNode firstChild;
TreeNode secondChild;
Reversed Card
Addathead
RemoveAtHead
Clear
isEmpty
What four methods make up the simplest linked list interface?
Reversed Card
By enclosing the body in a while loop and replacing the recursive call with one assignment per method argument.
How can tail recursion be eliminated?
Reversed Card
Classes built with no data and one single method.
What are function objects?
Reversed Card
A tree in which the leaves are operands, such as constants or variable names, and the internal nodes contain operators.
What is an expression tree?
Reversed Card
Let the Node be N.
N.Object = findMin(N.right).Object;
Delete(findMin(N.right);
How is a node with two children deleted?
Reversed Card
Long(long m, long n)
while(n!=0)
long rem = m % n;
m = n;
n = rem;
return m;
What is the Euclid algorithm?
When an outer insertion occurs to the right, what does the imbalanced node become?
It becomes its right child’s left child.
Where is the insertion point in a probabilistic skip list?
The point in the list after the previous node.
What function is called when Insertion took place in the left subtree of the left child of X(out-of-balance node).
rotate with left child
Reversed Card
double rotate with left.
What function is called when Insertion took place in the right subtree of the left child?
What function is called when Insertion took place in the right subtree of the right child?
rotate with right
What interface does the Collections interface extend?
The iterable interface
What type of objects cannot be used in place of generic type parameters?
Primitive types, Wrapper classes must be used.
Reversed Card
A root and two subtrees, both of which could be empty.
A binary tree consists of what?
What is one way to shorten code for assignments?
making multiple assignments in one line right to left.
What is a directory in the UNIX File System?
A file with a list of all its children.
Reversed Card
Long power(long a, int b)
if(b == 0) return 1;
if(b == 1) return a;
if(b%2 == 0) return power(a*a, b/2);
else return power(a*a, b/2)*a;
What is the algorithm for fast exponentiation?
Reversed Card
O(log N) assuming all insertion sequences are equally likely.
What is the average depth over all nodes in a binary search tree assuming that all insertion sequences are equally likely?
These two linked list operations are identical to a stack push and pop…
AddAtHead
RemoveAtHead
What data structure is used to implement stacks, queues and deques?
Linked lists are used to implement these data structures.
Reversed Card
A queue
What ADT is used in operating systems and algorithm design?
Reversed Card
ArrayList, and LinkedList
What two implementations are there of the built in List interface?
Reversed Card
O(N2)
What is the Big Oh time of a simple sorting algorithm?
When is the maximum level of a probabilistic skip list chosen?
At construction
Reversed Card
A stack
When implementing recursion, what ADT is usually used?
What two data members make up a linked list node?
Object element
Node next
What is an online algorithm?
an algorithm that can correctly give an answer for the data it has read at any given time.
Reversed Card
head = new Node(object, head);
The addAtHead function has only one line of code. What is it?
The running time of a for loop is at most what?
the running time of the statements inside the for loop multiplied by the number of iterations.
The ArrayList class contains what data variables?
An underlying array, the array capacity, and the current number of items in the array.
What is the advantage of a LinkedList over an ArrayList?
Add and remove at head take constant time.
A rotate with right child causes the Node X to replace it’s right child with what?
the right childs left subtree.
Log(A*B) = ?
Log A + Log B
What is postorder traversal?
When the work at a node is done after its children have been evaluated.
Reversed Card
Graphs
Trees are actually what?
What is a queue?
A list in which insertion is done at one end and removal is done at the other end.
Reversed Card
We construct the AVL tree of height h that contains the fewest nodes, we call these the skinniest AVL trees.
We deduce a recurrence relation for the minimum number of nodes in an AVL tree of height h.
We solve this recurrence relation and then rearrange the result to get an equation for the maximum height of an AVL tree with N nodes.
How do we prove the property of the worst case height of an AVL tree to be O(log N)?
Reversed Card
A reference that points to itself, and another entry that points to the parent of the directory.
Besides a list of its children, what else does a Unix directory have?
Reversed Card
Head is Node,
List is Empty.
What are the two special cases dealt with first in most list operations?
What kind of traversal is used to evaluate an expression tree?
An in order traversal is used
Reversed Card
the process performed by the compiler that turns generic classes into non-generic classes.
What is type erasure?
What is preorder traversal?
When the work at a ndoe is performed before its children are processed.
Reversed Card
- DoubleRotateWRight(node x)
- x.right = rotateWLeft(x.right);
- Return rotateWRight(x);
What is the double rotate with right child algorithm?
Reversed Card
infix.
An expression that is in standard form is said to be____
Reversed Card
this is the case that insertion took place in the right subtree of x’s left child.
Let x be the out of balance node, and k be the key that was inserted what is the case that x.leftchild < k < x.value?
Reversed Card
it specifies the properties that the parameter types must have and goes inside of the angle brackets after the type parameter.
What is a type bounds?
Reversed Card
O(logn), solved by noticing that after two iterations the remainder is less than n/2.
What is the time complexity of Euclids algorithm?
How is a node with two children deleted?
Let the Node be N.
N.Object = findMin(N.right).Object;
Delete(findMin(N.right);
What is a popular application of trees in operating systems?
The directory structure is a popular application.
What is the worst case tree height of an AVL tree?
O(log N) this is worst
Reversed Card
Object element;
TreeNode firstChild;
TreeNode secondChild;
What are the three variables of a treeNode?
All recursive functions must eventually reduce to what?
To the base case.
What else may be used besides the Object class for genericity, and how?
An interface may be used as the parameter type and return type to create a generic function.
What ADT is used in operating systems and algorithm design?
A queue
When is insertion sort generally faster?
When n < 25.
Reversed Card
They count for no time unit.
What time unit do declartions count for?
Reversed Card
null checks
When compound logical statements are used in linked list traversals, what should always be done first?
Reversed Card
A new red node with null links.
All insertions in a red black tree create a new what?
Reversed Card
when each inner class object is associated with exactly one instance of an outer class object.
When is using an inner class useful?
Reversed Card
2h+1-1
A perfect binary tree has how many nodes?
Reversed Card
double rotate with right
What function is called when Insertion took place in the left subtree of the right child?
When can insertion and deletion in a skip list take O(N)?
When the division into regions of size equal to powers of two is maintained.
Reversed Card
The iterable interface
What interface does the Collections interface extend?
Reversed Card
Public static int maxsubsum(int[] a)
Int max sum = 0, this sum =0;
For (int I =0, I < a.length, i++)
Thissum += a[i];
If(thissum > maxsum ) maxsum = thissum;
Else if (thissum < 0) thissum = 0;
Return maxsum;
What is the linear time algorithm for the positive max subsequence problem?
Where is the parameter type used in a class definition?
Anywhere in the class where the type of an object can be anything.
Reversed Card
S(h) = S(h-1) + S(h-2) + 1
The minimum number of nodes in an AVL tree of height h is given by what recurrence relation?
What extra variable and operations are used in a queue?
A tail node, insert at tail, remove at head
When creating a generic method, where do the angle brackets go?
Before the return type.
In a path name, each slash indicates what?
An edge from one directory node to the other.
Reversed Card
- An insertion into the left subtree of the left child of unbalanced node.
- An insertion in to the right subtree of the left child of unbalanced node.
- An insertion into the left subtree of the right child of unbalanced node.
- An insertion into the right subtree of the right child of the unbalanced node.
What are the four cases that may cause a balance violation?
What function is called when Insertion took place in the right subtree of the left child?
double rotate with left.
Reversed Card
2Xn
Xn + Xn = ?
What two kind of rotations is a double rotation?
- a rotate with right, followed by a rotate with left
or
- a rotate with left, followed by a rotate with right.
Reversed Card
- Deleting a leaf Node.
- Deleting a node with one child.
- Deleting a node with two children.
What are the three cases which the delete algorithm must address?
What is an inside insertion?
an insertion into the right subtree of the left child, or the left subtree of the right child.
Reversed Card
After the class name, before the object reference.
When instantiating a generic class, where do the angle brackets go?
Reversed Card
(Anytype []) new Object[];
How is a generic array created?
Reversed Card
Stores a current position starting at the beginning.
HasNext();
Next();
Remove();
What is the basic implementation of an iterator?
Reversed Card
stores identically typed objects
What does a collection do?
Let x be the out of balance node, and k be the key that was inserted what is the case that x.value < k < x.rightChild.value?
this is the case that insertion took place in the left subtree of the right child.
What is a rooted Binary tree?
A tree with a root node in which every node has at most two children.
Reversed Card
O(logN)
What is the average running time of most operations in a binary search tree?
What is a geometric recurrence?
one in which the numbers are in the sequence are a product of the previous number and some k.
What is the basic implementation of an iterator?
Stores a current position starting at the beginning.
HasNext();
Next();
Remove();
What are the minimal two classes needed to implement a linked list?
LinkedList
Node
Reversed Card
O(1), it is constant.
What is the runtime of adding an removing from a linked list?
A tree that is not binary may have how many children?
An arbitrary number, possibly zero.
Reversed Card
The point in the list after the previous node.
Where is the insertion point in a probabilistic skip list?
In computer science, all logarithms are to what base?
Base 2
What is the runtime of fast exponentiation?
O(logn), which is given by the number of multiplications computed.
Reversed Card
N divides A - B, this intuitively means that the remainder is the same when N divides either A or B.
We say that A is congruent to B modulo N, if
When instantiating a generic class, where do the angle brackets go?
After the class name, before the object reference.
Besides a list of its children, what else does a Unix directory have?
A reference that points to itself, and another entry that points to the parent of the directory.
Reversed Card
if(head ==null) throw error
Object result = head.value;
head = head.next;
return result;
What is the removeFromHead algorithm?
Reversed Card
A list in which every node maintains a link to its previous and next node.
What is a doubly linked list?
When instantiating a class, what goes inside of the angle brackets?
The type of object that will replace the parameter type.
Reversed Card
A search proceeds along the list with the greatest span until two references are found that enclose the required key. Then the search proceeds at the next level down until the required key found, or is deemed to be not present.
How does a skip list search work?
What is the contains algorithm?
- Contains(x, BinaryNode t)
- if(t == null) return false;
- if(x.compareTo(t.Object) < 0) return contains(x, t.left);
- if(x.compareTo(t.Object) > 0) return containts(x, t.right);
- else return true;
Reversed Card
by repeatedly taking the GCDs of pairs of numbers: gcd(gcd(a, b), c)
How can Euclids algorithm be used for finding the GCD of 3 or more positive numbers?
When and for what are wildcards used?
When using a generic Collections, a wild card goes inside of the angle brackets after Collection along with the extends keyword to allow a class and any of its subclasses to be used in the collection.
What kind of traversal is used to convert an expression tree into a postfix expression?
A postorder traversal.
Reversed Card
It returns true if a node in tree T has item x, or false if not.
What does the contains function do?
Reversed Card
It’s left child’s right subtree.
A rotate with left child causes the Node X to become what?
The addAtHead function has only one line of code. What is it?
head = new Node(object, head);
What is the average depth of a binary search tree?
O(log N)
Reversed Card
Before the return type.
When creating a generic method, where do the angle brackets go?
Reversed Card
- a rotate with right, followed by a rotate with left
or
- a rotate with left, followed by a rotate with right.
What two kind of rotations is a double rotation?
What are the variables of a BinaryNode?
Object, left child, right child.
Reversed Card
Because deltion will always faovr making one sides subtree shorter, therefore making all insertion sequences no longer equally likely.
Why does deletion cause the average runtime of O(log N) to not always hold?
Reversed Card
A preorder traversal.
What kind of traversal is used to convert an expression tree into a prefix expression?
Reversed Card
null.
What should the last node in a linked list always point to?
Reversed Card
It ensures that the depth of a tree is O(log N)
What does an AVL tree ensure?
When we are speaking of trees, N always represents what?
Reversed Card
making multiple assignments in one line right to left.
What is one way to shorten code for assignments?
Reversed Card
The path from the root to the farthest null-link is no more than twice as long as the path from the root to the nearest null link.
What is the fundamental Red-Black Tree Property?
Reversed Card
The enhanced for loop.
Classes that extend the iterable interface can implement what?
What is the fundamental Red-Black Tree Property?
The path from the root to the farthest null-link is no more than twice as long as the path from the root to the nearest null link.
How can tail recursion be eliminated?
By enclosing the body in a while loop and replacing the recursive call with one assignment per method argument.
What is the IsEmpty algorithm?
return root == null;
What is a stack frame, or activation record?
The information saved on a stack when a method is called and the registers must be cleared.
What kind of traversal is used to convert an expression tree into a prefix expression?
A preorder traversal.
Reversed Card
Compiler features that allow primitive types to be passed as wrapper classes and vice versa.
What is autoboxing/ unboxing?
Reversed Card
2log2(n+1)
Every red black tree with N nodes has a height less than or equal to what?
Reversed Card
To allow the nested class to use the members of the outer class.
Why must we use the static keyword when nesting a class inside of a class?
Reversed Card
A pop or peek on an empty list.
What is generally considered an error in the stack adt?
What are function objects?
Classes built with no data and one single method.
Reversed Card
A file with a list of all its children.
What is a directory in the UNIX File System?
Reversed Card
O(n2), different from its average case.
What is the time complexity of Quick sort?
Reversed Card
An interface may be used as the parameter type and return type to create a generic function.
What else may be used besides the Object class for genericity, and how?
Reversed Card
- Every node is either red or black.
- The root of the tree is black.
- A red node must have no children or exactly two black children.
- Every path from a node x to a descendent null-link must have the same number of black nodes.
What are the four fundamental properties of Red-Black Trees?
Reversed Card
a clearly specified set of simple instructions to be followed to solve a problem.
What is an algorithm?
When compound logical statements are used in linked list traversals, what should always be done first?
null checks
Reversed Card
When every node that is inserted is larger or smaller than the one before, ie, they are inserted in order.
When does the worst case depth happen in a binary search tree?
What is a binary tree?
A tree in which no node can have more than two children.
At worst case, a binary tree can have a depth of what?
N-1
What is the binary tree insertion algorithm?
- BinaryNode Insert(x, BinaryNode t)
- if(t==null) return new BinaryNode(x, null, null);
- int compare = x.compareTo(t.element);
- if(compare < 0) t.left = insert(x, t.left)
- else if(compare > 0 ) t.right = insert(x, t.right);
- else do nothing;
- return t;
What are the three steps to creating an expression tree from a postfix expression?
- We read our expression one symbol at a time. If the symbol is an operand, we create a one node tree and push it to a stack of trees.
- If the symbol is an operator, we pop two trees from the stack and form a new tree whose root is the operator.
- The new tree is then pushed onto the stack, and the process continues until it is complete.
Reversed Card
2 constructors, right child, left child, object, height.
What is the AVL node implemenation?
What is the performance time of a degenerate tree?
The same as that of a linked list. O(n)
2n + 2n = ?
2n+1
What is tail recursion?
A recursive call at the last line of a method, and an example of bad recursion.
What is a complete binary tree?
A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
What is the first step to doing an insertion or deletion in a probabilistic skip list?
Finding the insertion point.
A Red-Black tree where all nodes are black is what?
A perfect Binary tree.
Reversed Card
A red node can never have a red child, or just one child.
What can a red node never have?
When does the worst case depth happen in a binary search tree?
When every node that is inserted is larger or smaller than the one before, ie, they are inserted in order.
What is the time complexity of Quick sort?
O(n2), different from its average case.
Reversed Card
- We read our expression one symbol at a time. If the symbol is an operand, we create a one node tree and push it to a stack of trees.
- If the symbol is an operator, we pop two trees from the stack and form a new tree whose root is the operator.
- The new tree is then pushed onto the stack, and the process continues until it is complete.
What are the three steps to creating an expression tree from a postfix expression?
Reversed Card
Ordered Linked Lists
What are skip lists made of?
A perfect binary tree has how many nodes?
2h-1
Reversed Card
Operands are pushed onto a stack until an operator is encountered.
Two operands are then popped and the operator is applied to them and saved in a result variable.
The result is pushed back onto the stack, and this is continued until the end of the expression.
What is the algorithm for evaluating a postfix expression?
Reversed Card
It is the value for which the function is known without having to resort to recursion.
What is the base case of a recursive function?
Reversed Card
(Logc B)
(Logc A)
LogA B = ?
Reversed Card
One time unit.
What is the time unit of a simple operation or assignment?
What is the average depth over all nodes in a binary search tree assuming that all insertion sequences are equally likely?
O(log N) assuming all insertion sequences are equally likely.
Reversed Card
At construction
When is the maximum level of a probabilistic skip list chosen?
If a prime number N divides a product of two numbers, then
it divides at least one of the two numbers.
What are the four cases that may cause a balance violation?
- An insertion into the left subtree of the left child of unbalanced node.
- An insertion in to the right subtree of the left child of unbalanced node.
- An insertion into the left subtree of the right child of unbalanced node.
- An insertion into the right subtree of the right child of the unbalanced node.
Reversed Card
when it takes constant time to cut the problem size by a fraction, usually 1/2.
When is an algorithm O(logn)?
What is an algorithm?
a clearly specified set of simple instructions to be followed to solve a problem.
What is the double rotate with right child algorithm?
- DoubleRotateWRight(node x)
- x.right = rotateWLeft(x.right);
- Return rotateWRight(x);
What is the removeFromHead algorithm?
if(head ==null) throw error
Object result = head.value;
head = head.next;
return result;
Reversed Card
The length of the unique path from the root to it.
What is the depth of a node?
What function is called when Insertion took place in the left subtree of the right child?
double rotate with right
An expression that is in standard form is said to be____
infix.
How can a generic object of Object type be accessed and used properly?
By downcasting the object to the proper type.
What is the depth of the root?
depth = 0.
Reversed Card
this is the case that insertion took place in the left subtree of x’s left child.
Let x be the out of balance node, and k be the key that was inserted what is the case that K < x.leftChild.Value?
What are some popular but not required linked list operations?
printList, makeEmpty
Reversed Card
.25
What is the suggested probabilistic variable value for a probabilistic skip list?
What is the depth of a node?
The length of the unique path from the root to it.
What is type erasure?
the process performed by the compiler that turns generic classes into non-generic classes.
How is a node with one child deleted?
The parent node sets its child node to its grandchild.
What are function objects used for?
To pass functions as parameters.
What is meant by an outside insertion?
An insertion took place in the right subtree of teh rigth child, or the left subtree of the left child.
Reversed Card
It does nothing.
What does the delete function do if a value is not found?
What is one way to handle a tree that will have duplicates inserted?
Keep a record of frequency in each node and update it when a duplicate is added or removed.
What are three examples of simple sorting algorithms?
Selection sort, bubble sort, insertion sort.
Reversed Card
When nodes have a deleted marker that is turned on when they are deleted.
What is lazy deletion?
Reversed Card
A doubly linked list.
What kind of list is required for a sufficient implementation of a deque?
What is the algorithm for evaluating a postfix expression?
Operands are pushed onto a stack until an operator is encountered.
Two operands are then popped and the operator is applied to them and saved in a result variable.
The result is pushed back onto the stack, and this is continued until the end of the expression.
Reversed Card
an insertion into the right subtree of the left child, or the left subtree of the right child.
What is an inside insertion?
What is a degenerate tree?
a tree where, for each parent node, there is only one associated child node.
What is the AVL node implemenation?
2 constructors, right child, left child, object, height.
