Computer Science 136 Vocabulary
Terms
undefined, object
copy deck
- Assertions
-
assert.pre(condition,"message when not met");
assert.post...
specifies the condition under which the method will work correctly - class description
-
What it does
What structure it uses
In plain English - method description
-
What it does
What structure it uses if necessary - Vector
-
A sizable data structure
ArrayList type
uses an array, gets to a bigger size when the array is full
Bad thing when adding an element to the beginning, O(n) - insertion sort
-
from left to right, get an element and move that in place
complexity: O(n^2) - selection sort
-
from left to right, get the biggest element, move that to the right
not as good as insertion sort
complexity: O(N^2)` - merge sort
-
break array into half, then half, then half, till trivial case.
Do n comparison each layer.
complexity: O(n*log n)
memory hungry - Quick sort
-
pick pivot, put pivot in place, and sort the two halves
complexity: O(n*log n) on random input, O(n^2) on almost sorted input
space efficient - radix sort
-
sort elements by first digit, then second, then third...
finally the array is sorted.
complexity: O(n) - binary search
-
find half, then half, then half...
complexity: O(log n) - Autoboxing
- Java 1.5 knows how to get the primitive data type from their object equivalents
- Tracing through Recursion
-
the Son method:
Look at the base case, look atw what called the base case, look at what call that. then you get the pattern
The Teresco method: try that on one element, try that on two elements, try that on three... until you see a pattern - Destructive method
-
A method that modifies the thing upon which it acts
In other words, do it to the thing being modified.
Ex: reversing the order of a list by swapping, not by creating a temp then reverse - queue implementation
-
array
no vector
CircularList - stack implementation
-
array (fixed size)
vector (double up is bad)
SinglyLinkedList (addFirst() and then remove()) both O(1) - Yo Jim, what do you and your TAs look for in a lab assignment and a test?
- Yo, ask him!
- Trees
-
A normal tree upside-down
Top is root - Convert a math expression into tree to show precedence
- Do it now!
- node
- each dot in the tree
- parent node
- a node that branches out
- child node
- the node connected to a node above it
- descendants
- all children on one level of the tree under one parent
- leaf node
- A node with no descendants
- Structure of one node
- has a nuique cominbation of a parent and a child
- Forest
- A collection of non-connecting trees
- Edge
-
connects a node with its subtrees.
a branch? - Simple path
- A series of connecting, non-repeating nodes
- Path length
- Number of edges in a path
- Height of node
- The number of nodes in the longest simple path from the leaf node to the current node
- Depth of a node
- The number of nodes in the longest simple path from the root node to the current node
- Degree of a node
- number of its children
- Binary Trees
- have all nodes degree <= 2
- Full Trees
- If a tree has height h, then it has leaves only on level h
- Complete Trees
- A full tree with some of the right most leave nodes removed
- Binary Tree representation
- Yes, let's go
- A node
-
parent BinaryTree<ELTYPE>
value ELTYPE
left/right BinaryTree<ELTYPE> - Why capitalized <ELTYPE> ??
- Ask!
- Empty Binary Tree
- All things about a node is null, except left = right = this
- Why use private constructor for an empty node?
- Don't want people to create an empty node
- Preorder Traversal
- See node, left subtree, right subtree, then another node
- In-order Traversal
- Each node is visited after all the left subtrees are visited and before the nodes of the right subtree
- Postorder traversal
- See all the left subtrees, see all the right subtrees, then the node itself (do this from the leave nodes)
- Level-order traversal
- level l is visited before level l+1