# CSE 116 Study Guide - Final Guide: Merge Sort, Multiset, Quicksort

41 views9 pages
School
Course
Professor
CSE 116 Final Notes
1. List
a. void add(int i, E e);
b. E set(int i, E e);
c. E remove(int i);
d. int indexOf(Object o);
e. E get(int i);
// Methods in List that were inherited from Collection
g. boolean remove(Object o);
h. boolean contains(Object o);
i. // size(),isEmpty(),iterator()& other boring ones
2. JUnitTests
a. assertEquals(X expected, X actual)
b. assertEquals(float exp, float act, float tol)
c. assertEquals(double exp, double act,double tol)
d. assertTrue(boolean test)
e. assertFalse(boolean test)
f. assertNull(Object objTest)
g. assertNotNull(Object objTest)
h. fail()
3. Priority Queue/Heap
a. Fills each level of the tree from left to right and the node stores the lowest (most
important) element all the time.
b. Removal from the root, Heap’s height O(log n)
c. SiftUp(): Add the element at the end, then start by comparing it to its parent, if it is less
than its parent keep comparing till you reach the root or else stop.
d. SiftDown(): Find the rightmost element in the last level of the heap and swap it with the
root and then remove it from the tree. Then start the siftDown process by comparing it
with the 2 children and if it is larger than any of the child, swap it with the smaller child.
Keep doing this until you reach the leaf or the comparison fails.
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

4. Visitor Pattern
a. Binary Tree class has a function called visit():
public T visit(TreeVisitor<E,S,T> visitor){
S initVal= visitor.getInitialValue();
return root.apply(visitor,initVal);
}
b. Entry class has a function called apply():
public T apply(TreeVisitor<E,S,T> visitor, S data){
if(left==null&&right==null){
return visitor.visitLeaft(this,data);
}else{
return visitor.visitInterior(this,data);
}
c. Tree Visitor interface:
public interface TreeVisitor<E,S,T> {
S getInitialValue();
T visitLeaf(Entry<E> node, S data);
T visitInterior(Entry<E> node, S data){
//Pre-Order
if(node.getLeft()!=null){
node.getLeft.appply(this,data);
}
//In-Order
if(node.getRight()!=null){
node.getRight.apply(this,data);
}
//Post-Order
}
d. When data is passed up a tree, leaf returns a value and visitInterior and visitLeaf have
return types.
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

e. When data is passed down a tree, leaf sets its element to the data passed and the
return type for visitInterior and visitLeaf is void. (add return null statement in void
functions)
f. Three types of tree traversals:
f.i. Pre-Order: Root Left Right (Useful when nodes has data children need, Table of
Contents)
f.ii. In-Order: Left Root Right
f.iii. Post-Order: Left Right Root (Calculating the size of a folder)
5. Tress/Binary Tree
a. For every level i:
a.i. That level can have 2i nodes
a.ii. At most the tree can have 2(i+1) – 1 nodes
b. Height of a tree= level+1
c. Tree/Binary tree only stores the reference of Root entry
d. The entry class in binary tree has parent, left and right
e. The entry class in a tree has a parent and a list of entries
f. Array based binary tree:
f.i. Root at 0
f.ii. Left child at 2n+1
f.iii. Right child at 2n+2
g. Binary Search Tree:
g.i. Smaller elements to node’s left and larger elements to node’s right
g.ii. Search, insert, remove takes O(h) time (h-height)
g.iii. Successor():
private Entry<E> successor(Entry<E> e) {
if (e == null) {
return null;
} else if (e.right != null) {
// successor is leftmost Entry in right subtree of e
Entry<E> p = e.right;
while (p.left != null) {
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 9 pages and 3 million more documents.

## Document Summary

List: void add(int i, e e), e set(int i, e e), e remove(int i); d. int indexof(object o), e get(int i); // methods in list that were inherited from collection f. boolean add(e e): boolean remove(object o), boolean contains(object o); i. Then start the siftdown process by comparing it with the 2 children and if it is larger than any of the child, swap it with the smaller child. Keep doing this until you reach the leaf or the comparison fails: visitor pattern, binary tree class has a function called visit(): public t visit(treevisitor visitor){ S initval= visitor. getinitialvalue(); return root. apply(visitor,initval): entry class has a function called apply(): public t apply(treevisitor visitor, s data){ if(left==null&&right==null){ return visitor. visitleaft(this,data); }else{ return visitor. visitinterior(this,data): tree visitor interface: public interface treevisitor { Pre-order: root left right (useful when nodes has data children need, table of. Post-order: left right root (calculating the size of a folder: tress/binary tree, for every level i: a. i.