EECS 233 Final Exam Cheat Sheet PDF

Static storage: region of memory automatically allocated at the start of the program, used for class variables, fixed
during class lifetime. Stack Storage: stores method parameters and local variables, for each method call a new stack frame is added to the top
of the stack, the stack pointer indicates the current pointer of stack memory allocation, when a method completes, its stack frame is removed and the values stored there are not preserved. Heap Storage: allocated using the new operator, referred to as
dynamic memory allocation because it is specified as part of the program and is determined at runtime, new returns the memory address of the start of the created object and is stored in the variable that represents the array/object. Abstract data type is
the model of a data structure that specifies: what operations can be performed on the data but not how these operations are implemented. n!, 2^n, 2^(n-1), (3/2)^n, n- n^2+5n^3, n^3+ log n, n^3, n^2, n log n, n, sqrt(n), (log n)^2, log n, log log n, 6
Pre: 7 5 2 4 6 9 8
post: 4 2 6 5 8 9 7
in: 2 4 5 6 7 8 9
level: 7 5 9 2 6 8 4
Theorem: A connected graph contains an

Eulerian cycle if and only if every
vertex has even degree. If exactly two
vertices have odd degree, it contains
an Eulerian path but not an Eulerian
cycle.
In order to cross each edge once, any
time that we arrive at a vertex along
a particular edge, we must depart on a
different edge.
d with each vertex
must come in arrival/departure
pairs, Therefore, the degree of each
vertex must be even!
t
for starts or stops that must have an
odd number unless they coincide (in
which case the path is a cycle).
averse
every edge once and only once are
known as Eulerian paths. If the path
is a cycle, it is known as an Eulerian
cycle.
searching a binary
search tree:
best case: O(1)
worst case: O(h)
average case: O(h)
not balanced, an
extreme case:
height = n 1, and
worst-case time
complexity = O(n)
For a balanced tree
with n nodes: height =
O(log2n): worst-case
time complexity
=O(log2n)
What if, instead of traversing each

edge once and only once, we looked for
a path that visited each vertex once
and only once?
Hamiltonian path (or cycle if the
start and end vertices coincide.
-century Scientist
Sir William Rowan Hamilton
Icosian game where the object is to
walk around the edges of dodecahedron
while visiting each vertex once and
only once.
SiftUp and SiftDown Height

h = log2N Running time
O(log2N) in the worst case
findMax O(1) removeMax() O(logN)

insert() O(logN) delete() O(logN)
update() the priority O(logN)
buildHeap() O(N) merge() O(N)
sum is O(N), where N is

the number of nodes
In the best case, search and insertion are O(1). In

the worst case, search and insertion are linear.
open addressing: O(m), where m = the size of the
hash table separate chaining: O(n), where n = the
number of keys With a good choice of hash
function and table size, the time complexity is
generally better than O(log n) and approaches O(1).
As the load factor increases, performance tends to
decrease. Open addressing: try to keep the load
factor < Separate chaining: try to keep the load
factor < 1 Time-space tradeoff: bigger tables tend
to have better performance, but they use up more
memory.
Knuths sequence: 1093, 364, 121, 40, 13, 4, 1 incr =

incr/3; Sedgewicks sequence: 109, 41, 19, 5, 1
interleave 9*4i - 9*2i + 1 and 4i - 3*2i + 1 worst-case
running time O(n4/3)
static int partition(int[] arr, int first,

int last) {
int pivot = arr[(first + last)/2];
int i = first - 1;
// index going from left to right int j =
last + 1;
// index going from right to left while
(true) {
do { i++;
} while (arr[i] < pivot); do {
j--;
} while (arr[j] > pivot);
if (i < j) swap(arr, i, j);
else return j;
// arr[j] = end of left array } }
A tree is a special type of graph. it is

connected and undirected it is
acyclic: there is no path containing
distinct edges that starts and ends at
the same vertex we usually single out
one of the vertices to be the root of the
tree, although graph theory doesn't
require this
bfTrav(origin)
origin.parent = null
create a new queue q
q.insert(origin)
while (!q.isEmpty()) v = q.remove()
visit v
for each vertex w in v's neighbors
if w is not encountered
mark w as encountered
w.parent = v;
q.insert(w);

EECS 233 Final Exam Cheat Sheet PDF

Uploaded by

Copyright:

Available Formats

EECS 233 Final Exam Cheat Sheet PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

EECS 233 Final Exam Cheat Sheet PDF

Uploaded by

Copyright:

Available Formats

Static storage: region of memory automatically allocated at the start of the program, used for class variables, fixed

Theorem: A connected graph contains an

What if, instead of traversing each

SiftUp and SiftDown Height

findMax O(1) removeMax() O(logN)

sum is O(N), where N is

In the best case, search and insertion are O(1). In

Knuths sequence: 1093, 364, 121, 40, 13, 4, 1 incr =

static int partition(int[] arr, int first,

A tree is a special type of graph. it is

You might also like