Computer Science 136 Vocabulary

Front 1

Assertions

Back 1

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

Front 2

Javadoc

Back 2

/** */ For method comments
/*@author For author name
/*@pre precondition
/*@post poscondition
/*@param parameters

Front 3

class description

Back 3

What it does
What structure it uses
In plain English

Front 4

method description

Back 4

What it does
What structure it uses if necessary

Front 5

@post commenting style

Back 5

say what gets changed and what gets returned

Front 6

@pre commenting style

Back 6

specify the condition under which the method will run correctly

Front 7

Vector

Back 7

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)

Front 8

insertion sort

Back 8

from left to right, get an element and move that in place

complexity: O(n^2)

Front 9

selection sort

Back 9

from left to right, get the biggest element, move that to the right

not as good as insertion sort

complexity: O(N^2)`

Front 10

merge sort

Back 10

break array into half, then half, then half, till trivial case.
Do n comparison each layer.
complexity: O(n*log n)
memory hungry

Front 11

Quick sort

Back 11

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

Front 12

radix sort

Back 12

sort elements by first digit, then second, then third...
finally the array is sorted.
complexity: O(n)

Front 13

binary search

Back 13

find half, then half, then half...

complexity: O(log n)

Front 14

Autoboxing

Back 14

Java 1.5 knows how to get the primitive data type from their object equivalents

Front 15

Tracing through Recursion

Back 15

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

Front 16

Destructive method

Back 16

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

Front 17

queue implementation

Back 17

array
no vector
CircularList

Front 18

stack implementation

Back 18

array (fixed size)
vector (double up is bad)
SinglyLinkedList (addFirst() and then remove()) both O(1)

Front 19

Yo Jim, what do you and your TAs look for in a lab assignment and a test?

Back 19

Yo, ask him!

Front 20

Trees

Back 20

A normal tree upside-down
Top is root

Front 21

Convert a math expression into tree to show precedence

Back 21

Do it now!

Front 22

node

Back 22

each dot in the tree

Front 23

parent node

Back 23

a node that branches out

Front 24

child node

Back 24

the node connected to a node above it

Front 25

descendants

Back 25

all children on one level of the tree under one parent

Front 26

leaf node

Back 26

A node with no descendants

Front 27

Structure of one node

Back 27

has a nuique cominbation of a parent and a child

Front 28

Forest

Back 28

A collection of non-connecting trees

Front 29

Edge

Back 29

connects a node with its subtrees.

a branch?

Front 30

Simple path

Back 30

A series of connecting, non-repeating nodes

Front 31

Path length

Back 31

Number of edges in a path

Front 32

Height of node

Back 32

The number of nodes in the longest simple path from the leaf node to the current node

Front 33

Depth of a node

Back 33

The number of nodes in the longest simple path from the root node to the current node

Front 34

Degree of a node

Back 34

number of its children

Front 35

Binary Trees

Back 35

have all nodes degree <= 2

Front 36

Full Trees

Back 36

If a tree has height h, then it has leaves only on level h

Front 37

Complete Trees

Back 37

A full tree with some of the right most leave nodes removed

Front 38

Binary Tree representation

Back 38

Yes, let's go

Front 39

A node

Back 39

parent BinaryTree<ELTYPE>
value ELTYPE
left/right BinaryTree<ELTYPE>

Front 40

Why capitalized <ELTYPE> ??

Back 40

Ask!

Front 41

Empty Binary Tree

Back 41

All things about a node is null, except left = right = this

Front 42

Why use private constructor for an empty node?

Back 42

Don't want people to create an empty node

Front 43

Preorder Traversal

Back 43

See node, left subtree, right subtree, then another node

Front 44

In-order Traversal

Back 44

Each node is visited after all the left subtrees are visited and before the nodes of the right subtree

Front 45

Postorder traversal

Back 45

See all the left subtrees, see all the right subtrees, then the node itself (do this from the leave nodes)

Front 46

Level-order traversal

Back 46

level l is visited before level l+1