comp 228 data structures

· Big Omega

o Ω(f(n)) means f(n) is a lower bound on the time to execute an algorithm

(best)

· Big O

o O(f(n))means f(n) is an upper bound(worst)

Big Theta

o Θ(f(n)) means f(n) is the time to execute an algorithm -but also used for average

(average)

· O(1 ); bounded time

o The amount of work is not dependent on the size of the problem

· O(log2N); logarithmic time;

o Algorithms that successively cu the amount of data to be processed in half at each step typically fall into this category

· •O(N); linear time

o Adding together the elements of an array is O(N)

· •O(Nlog2N); NlogN time

o Good sorting algorithms, such as quicksort, heapsort, and merge sort have NlogN complexity

· •O(N2); quadratic time

o Some simple sorting algorithms are O(N2)algorithms

· •O(2N); exponential time

o These algorithms are extremely costly!

Recursion

Recursion is a technique that leads to elegant solutions to problems that are difficult to program using simple loops

Recursion Terms

Recursive method

A method that calls itself directly or indirectly

Direct recursion

Recursion in which a method directly calls itself

Indirect recursion

Recursion in which a chain of two or more calls returns to the method that originated the chain

Selection Sort

Find the smallest element in the data set and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, ... continue in this way until the entire data set is sorted

SELECTION SORT IS O(N^2)

Bubble Sort

Smaller data values "bubble up" to the top of the array

There are N - 1 comparisons the first time, N- 2 comparisons the second time, and so on

Bubble Sort is O(N2)

Insertion Sort

Each successive element in the array is inserted into its proper place with respect to the already sorted elements

O(N^2), but when it is it's sorted it's N comparisons and 0 swaps

Merge Sort

If we can cut the array into two pieces, sort each segment, and then merge the two back together, we should end up sorting the entire array with a lot less work

Total cost of the merge operation is: O(Nlog2N)

Total cost of the sort is O(Nlog2N) + O(N)

Quick Sort

A divide-and-conquer algorithm

Inherently recursive

At each stage, the part of the array being sorted is divided into two "piles", with everything in the left pile less than everything in the right pile

Heap Sort

take the root (maximum) element off the heap, and put it into its place

reheap the remaining elements (next-largest element ends up in the root position)

repeat steps 1 and 2 until there are no more elements

BINARY SEARCH TREE

A binary tree in which the key value in any node is greater than or equal to the key value in its left child and any of its descendants - the nodes in the left subtree - and less than the key value in its right child and any of its descendants - the nodes in the right subtreE

Preorder traversal

Visit the root, visit the left subtree, visit the right subtree

(Triforce)

Inorder traversal

Visit the left subtree, visit the root, visit the right subtree

(Water)

Postorder traversal

Visit the left subtree, visit the right subtree, visit the root

(elegy of darkness)

TRAVERSAL IMPLEMENTATIONS

The application program passes the reset and getNext methods a parameter indicating which of the three traversal orders to use:

· The reset method

o public int reset(TraversalType orderType) {

// returns current number of nodes in the tree

switch (orderType) {

case INORDER :

inOrderQ = new ArrayQueue();

inOrder(root);

Break;

case PREORDER :

preOrderQ = new ArrayQueue();

preOrder(root);

Break;

case POSTORDER :

postOrderQ = new ArrayQueue();

postOrder(root);

break;

}

return size()

}

The inOrder Method

private void inOrder(BSTNode tree) {

if (tree != null) {

inOrder(tree.getLeft());

inOrderQ.enqueue(tree.getInfo());

inOrder(tree.getRight());

}

}

The getNext method

public T getNext (TraversalType orderType) {

/*

* preconditions

* - the BST is not empty

* - the BST has been reset for orderType

* - the BST has not been modified since the most recent reset

* - app code is responsible for not iterating beyond the end

* of the tree

*

* Returns the element at the current position on the BST for

* the specified traversal type and advances the value of the

* current position

*

*/

switch (orderType) {

case INORDER : return inOrderQ.dequeue();

case PREORDER : return preOrderQ.dequeue();

case POSTORDER: return postOrderQ.dequeue();

default: return null;

}

}

}

The SIZE Operation

The public facing Size method calls the private recursive method recSize , passing in the root of the entire tree

public int size() {

return recSize(root);

}

private int recSize(BSTNode tree) {

if (tree == null)

return 0;

Else

return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;

}

THE ADD OPERATION

Add invokes the recAdd recursive method, passing it the element to be added plus reference to the root of the tree

public void add (T element) {

root = recAdd(element, root);

}

The recAdd MEthod

if (element.compareTo(tree.getInfo()) <= 0) {

tree.setLeft(recAdd(element, tree.getLeft()));

}

else {

tree.setRight(recAdd(element, tree.getRight()));

}

}

return tree;

}

The Remove Operation

recRemove is invoked from the public facing remove method with arguments equal to the element to be removed and the subtree from which to remove it

How to remove a Leaf node

set the appropriate link of its parent to null

How to remove a node (with one child)

make the reference from the parent skip over the node and point instead to the removed node's child

How to remove a node with two children

replace the node's info with the info from another node in the tree so that the "left is less; right is more" property is retained - then remove this other node

The getPRedecessor METHOD

Given a tree's left subtree, we just keep moving right until the right child is null; then return the info reference of that node:

private T getPredecessor(BSTNode tree) {

while (tree.getRight() != null) {

tree = tree.getRight();

}

return tree.getInfo();

}

BALANCING A BINARY SEARCH TREE

Save the tree information in an array in order

Insert the information from the array back into the tree ... in the right order

TO ENSURE A BALANCED TREE

Even out as much as possible the number of descendants in each node's left and right subtrees: insert the middle item of the array insert the left half of the array insert the right half of the array

PRIORITY QUEUE

A priority queue is an ADT with the following accessing protocol: only the highest-priority element can be accessed

Heap

A binary tree implementation of a priority queue

Heap Enqueue

Add new item as the left-most leaf on the bottom level of the tree

Heap Dequeue

Root item is removed - item in rightmost leaf node on the bottom level is moved into the root

· Graph

o A data structure that consists of a set of nodes and a set of edges that relate the nodes to each other

· Vertex

o A node in a grape

· Edge

o A pair of vertices representing a connection between two nodes in a graph

· Undirected graph

o A graph in which the edges have no direction

· Directed graph (digraph)

o A graph in which each edge is directed from one vertex to another a graph G is defined as follows:

· Adjacent vertices

o Two vertices in a graph that are connected by an edge

· Path

o Two vertices in a graph that are connected by an edge

· Complete graph

o A graph in which every vertex is directly connected to every other vertex

· Weighted graph

o A graph in which each edge carries a value

· DEPTH-FIRST SEARCH

o Go down a path to its deepest point, backtracking when necessary. Use stacks

· BREADTH-FIRST SEARCH

o Visit all neighbors first, then systematically visit all of the neighbors' neighbors, and so on .. Use queues

GRAPH IMPLEMENTATIONS (Adjacency matrix)

§ N × N table that shows the existence, and weights, of all N edges in the graph

GRAPH IMPLEMENTATIONS (Adjacency list)

§ A linked list that identifies all the vertices to which a particular vertex is connected

· Dijkstra's Algorithm

an algorithm for finding the shortest paths between nodes in a graph,