INFS519 Final

Public class StackUnderFlowException extends RuntimeException
{
Public stackUnderFlowException()
{ } //will do nothing – just to invoke the exception method

Public stackUnderFlowException(String message)
{
Super(message);
}
}

Int a, b;
try
{
a = d.pop(); //get arguments from stack
b = d.pop(); //either pop will cause issue if stack is not there or empty
}
catch(StackUnderflowException e)
{
System.out.println(“Warning! Stack Underflow”);
System.exit(0);
}

try
{
d.push(a+b);
}
Catch(StackOverFlowException e)
{
System.out.println(“Warning! Stack Overflow”);
System.out.exit(0);
}

//inside D Stack class
Public double top()
{
//this will read the top of stack and return it w/o removing it
//need to make sure the stack is not empty
//first check to see if stack is empty:
If(sp == -1) //stack empty?
Throw new stackUnderFlowException();
Returnhold[sp];
}

1. A multi-way (or "n-way") search tree has nodes with n pointers (separated by) n number of keys.

2. A node can have up to n children

3. Keys should be arranged in ascending order

1. All non-root and non-leaf nodes have at least [n/2] children (rounded up) and heance at least [n/2]-1 keys
2. All the leaves also have at least [k/2]-1 leaves
3. Root can have as few as 2 children and 1 key
4. leaves are all at the same level (meaning that every leaf in a b-tree has the same depth)
5. There are special insert and delete operations which preserve these properties
6. B trees are (reasonably well) balanced multi-way search trees

1. All non-root and non-leaf nodes have at least [n/2] children (rounded up) and heance at least [n/2]-1 keys
2. All the leaves also have at least [k/2]-1 leaves
3. Root can have as few as 2 children and 1 key
4. leaves are all at the same level (meaning that every leaf in a b-tree has the same depth)
5. There are special insert and delete operations which preserve these properties
6. B trees are (reasonably well) balanced multi-way search trees

1. First search for k, if found, duplicate key error
2. else, locate the LEAF where we want to insert k (this involves several other steps!)
3. First see if an adjacent sibling has an "extra space"
4. IF yes (an adjacent sibling has an extra space):
4a. Move lowest/highest key from full node into parent's separator key (between the siblings)
4b. move the seperator key from parent into non-full sibling ("rotate through parent node")

The height of B-Trees grows at the root unlike Binary Trees (which grow at the leaves). This is due to the insertion process.

NOTE: This happens very infrequently which is good b/c when it does it is "costly" of time

1. For any key in a non-leaf it will also be the LAST key in the left child (ALLOWING FOR DUPLICATE KEYS)
2. Now we see that every key that appears ANYWHERE in the tree (also) appears exactly ONCE in a leaf
3. The tree is now divided into 2 parts, the leaves (data part) and non-leaves (index part)

If we want to store records, by using a B+Tree, each record will have a unique key.

1. We will store entire records in the data part (leaves), but KEYS ONLY in index part (non-leaves)
2. All of our data will be found in the data part (leaves)
3. Index provides a quick way to locate records given it's key.

4. THE LAST and MOST IMP. PART is that we will make the data part linked lists (add a pointer to each leaf and make the data part a singly linked list)

THUS now we have 2 ways to access records: Directly from key using index part OR sequentially through linked list.

A B+Tree example to store employee records:

-Directly - have to update an individual record
-Sequentially - have to print a monthly list for payroll

In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.

A recrod file stores records:
-there are several fields
-one field (key) - uniquely identifies the record

Common implementation of indexed sequential file is using a B+ tree using sectors for nodes. And sector numbers as “pointers”.

A transaction system is a computer system (or application) in which operations are short, involve little computation, but each operation requires at least one database access
-Transaction systems (among others) require FAST, DIRECT, access to individual records BY KEY.

-Implementation of index-sequential files using B+ trees (e.g. sectors for nodes, efficiency from large fan-out by just storing keys, and the balance you get from the B tree).

Recall: the table ADT - hashing is another very efficient implementation of tables (more widely used than BSTs), stores records (each record uniquely identified by a key field)

BOOK: Each element added to the table requires a unique identifying value called its key. A computation called the "hash function" maps key values to array indexes. Using the hash function to compute the correct array index is called hashing the key to an array index.

Set of all possible keys

when two different objects belong to the same index, for example we have keys k1 and k2 which are distinct however h(k1) = h(k2).

1. fast (and easy) to compute
2. minimize collisions

Depends on the application. E.g. storing GMU student records (30k) maybe 60k - 80k

1. Separate Chaining
2. Open Addressing
3. Linear Probing (which causes another issue: clustering).

CLASS: IDEA: create an array a[] of lists and store key in the list a[h(b)]

BOOK: in chaining, the hash table contains an array in which each component can hold mroe than one element of the hash table.

Allocate memory dynamically for each new key, store in the list at a[h(key)]

Advantages:
-The table is never full
-fast (as long as you don’t have overly long synonym chains – this is the fastest)
-EASY (even if you don’t use array, and just use linked lists – you can implement this in less than a page of code)

The idea of open addressing is to store the keys IN the array a[]. In open addressing, collisions are resolved by placing the object in the next OPEN spot of the array (using linear probing).

Linear probing is inserting key and we find that a[h(key)] is occupied, so we use the first available slot after h(key).

BOOK: e.g. suppose a new key hashes to location 330, but this location is full, then we will try location 331, then 332, then 333, and so on, searching for a vacant spot in this manner is called linear probing.

1. Conceptually simple
2. Easy to code

1. It doesn't work! If you remove a key (so now you have an empty spot) then when you search for k, when it hits an empty spot, it will think it's search is done (not realizing there is more after the empty spot) and will insert k again (even though it might exist down the line) - FAIL

Solution: Tombstone

Mark slots that were occupied and are now unoccupied with a “tombstone”

Now as slot in a [] can be in one of the following states:
• Free
• Occupied
• Tombstone

There is a problem with linear probing. When several different keys are hashed to the same array location, the results is a small cluster of elements, one after another. As the table approaches its capacity, these clusters tend to merge into larger and larger clusters.

Double Hashing. The technique uses a second hash function to determine how we move through an array to resolve a collision. (So now we have TWO hash functions)

H1: key space -> 0,…,SIZE-1 (primary hash function)
H2: keyspace -> non-negative integer reconciling hash function

(h1(key) + i*h2(key))%SIZE

NOTES:
oSIZE must be a prime
oRequire h2(key) < SIZE, for every key and h2(key) != 1
oDONE! Problem solved (double hashing solves the cluster problem)

oDivide slots of a[] into groups called buckets and have h(key) be the number of a bucket:

 I.E. to insert key first look for an empty slot in bucket h(key)
• Keys unordered in the bucket
 “Collision resolution” now becomes “dealing with full buckets”
 NOTE: we will still need tombstones here, if the bucket is full and you delete something from that bucket, don’t mark it as free, mark it as tombstone, that way if you go to bucket, and its not full, the tombstone will indicate you need to look somewhere else.

• Possibilities:
oCould put key in the next bucket (etc.)
-I.e. “bucket linear probing” (bucket version of linear probing)
-Similar issues to linear probing will arise…
-Could do “bucket double hashing”
-Set up a separate hash table for “overflow keys”
-Most common solution:
•Set up (unordered) overflow buckets
-When first bucket overflows:
•Allocate one overflow bucket and put key in it

Overflow buckets are unordered.
-When first bucket overflows:
• Allocate one overflow bucket and put key in it
-Each time a key hashes to a full bucket put it in the overflow bucket.
-When an overflow bucket overflows allocate a new overflow bucket, etc.
•(over flow buckets would be in a separate array)

o We want to generalize lists and trees
o But now instead of using “nodes & pointers” we will use….
o Definition: a graph G is a pair (V,E), of a vertex set (finite)
-V and the edge set E is a set of unordered pairs (v, w) of vertices

oNotice the pairs are unordered, so (v0, v1) and (v1,v0) represent the same edge

BOOK: A graph, like a tree, is a nonlinear data structure consisting of nodes and links between the nodes. Graph nodes can be linked in any pattern - or lack of pattern - depending on the needs of an application.

Very similar to our basic graph definition, except the pairs are ordered.

An undirected graph is a set of nodes and a set of links between the nodes. Each node is called a vertex, each link is called an edge, and an edge connects two vertices.

Undirected graphs are drawn by putting a circle for each vertex and a line for each edge.

When both sets (Vertices and edges) are empty, thus there are no vertices and no edges

A path is a sequence of joined edges

A cycle is a path from the vertex that makes it back to itself.

o A graph is connected if every pair of vertices can be joined by a path.
-A (connected) component of a graph is a maximal connected subgraph (a graph that is contained in another)
• Think of islands:

A graph is acyclic if it has no cycles. A connected, acyclic graph is called a Tree (we just havent picked a root yet).

A spanning tree is just a subgraph of a tree.

1. Adjacency Matrix
2. Adjacency Lists

An adjacency matrix is a square grid of true/false values that represent the edges of a graph. If the graph contains n vertices, then the grid contains n rows and n columns. For two vertex numbers i and j, the component at row i and column j is true if there is an edge from vertex i to vertex j; otherwise, the component is false.