Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle
Toggle OnToggle Off
 Alphabetize
Toggle OnToggle Off
 Front First
Toggle OnToggle Off
 Both Sides
Toggle OnToggle Off
 Read
Toggle OnToggle 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
46 Cards in this Set
 Front
 Back
Assertions

assert.pre(condition,"message when not met");
assert.post... specifies the condition under which the method will work correctly 

Javadoc

/** */ 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


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 upsidedown
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 nonconnecting trees


Edge

connects a node with its subtrees.
a branch? 

Simple path

A series of connecting, nonrepeating 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


Inorder 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)


Levelorder traversal

level l is visited before level l+1
