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

### 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

Progress

1/46

Click to flip

### 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 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 value ELTYPE left/right BinaryTree Why capitalized ?? 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