Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key


Play button


Play button




Click to flip

46 Cards in this Set

  • Front
  • Back
assert.pre(condition,"message when not met");
specifies the condition under which the method will work correctly
/** */ For method comments
/*@author For author name
/*@pre precondition
/*@post poscondition
/*@param parameters
class description
What it does
What structure it uses
In plain English
method description
What it does
What structure it uses if necessary
@post commenting style
say what gets changed and what gets returned
@pre commenting style
specify the condition under which the method will run correctly
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)
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
no vector
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!
A normal tree upside-down
Top is root
Convert a math expression into tree to show precedence
Do it now!
each dot in the tree
parent node
a node that branches out
child node
the node connected to a node above it
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
A collection of non-connecting trees
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> ??
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