Final Exam

Question 1

What are the stats for sequential search

Answer 1

Worst Case Search:
N
Worst Case Insert:
N
Average Case Search:
N/2
Average Case Insert:
N
Efficiently Supported Ordered Operations:
No

Question 2

What are the stats for binary search

Answer 2

Worst Case Search:
lg(N)
Worst Case Insert:
N
Average Case Search:
lg(N)
Average Case Insert:
N/2
Efficiently Supported Ordered Operations:
Yes

Question 3

What are the stats for BST

Answer 3

Worst Case Search:
N
Worst Case Insert:
N
Average Case Search:
1.39lg(N)
Average Case Insert:
1.39lg(N)
Efficiently Supported Ordered Operations:
Yes

Question 4

What are the stats for 2-3 tree search/red-black BST

Answer 4

Worst Case Search
2lg(N)
Worst Case Insert
2lg(N)
Average Case Search
1.00lg(N)
Average Case Insert
1.00lg(N)
Efficiently Supported Ordered Operations:
Yes

Question 5

What are the memory requirements for different algorithms

Answer 5

Separate Chaining:
48N+32M
Linear Probing:
32N to 128N
BSTs
56N

Question 6

How do you implement heapsort?

Answer 6

private voidexch(Comparable[] a, int i, int j)
{Key t = a[i]; a[i] = a[j]; a[j] = t;}
private booleanless(Comparable[] a, int i, int j)
{return a[i].compareTo(a[j]) < 0;}
private void sink(Comparable[] a, int k, int N)
{
while (2k <= N)
{
int j = 2k;
if (j < N && less(a, j, j+1)) j++;
if (!less(a, k, j)) break;
exch(a, k, j);
k = j;
}
}

public static void sort(Comparable[] a)
{
int N = a.length;
for (int k = N/2; k >= 1; k–)
sink(a, k, N);
while (N > 1)
{
exch(a, 1, N–);
sink(a, 1, N);
}
}

Question 7

How do you implement 2-way quicksort

Answer 7

{// Partition into a[lo..i-1], a[i], a[i+1..hi].
int i = lo, j = hi+1;// left and right scan indices
Comparable v = a[lo];// partitioning item
while (true)
{// Scan right, scan left, check for scan complete, and exchange.
while (less(a[++i], v)) if (i == hi) break;
while (less(v, a[–j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);// Put v = a[j] into position
return j;// with a[lo..j-1] <= a[j] <= a[j+1..hi].
}
private static void sort(Comparable[] a, int lo, int hi)
{
if (hi <= lo) return;
int j = partition(a, lo, hi);// Partition (see page 291).
sort(a, lo, j-1);// Sort left part a[lo .. j-1].
sort(a, j+1, hi);// Sort right part a[j+1 .. hi].
}

Question 8

How do you implement 3-way quicksort

Answer 8

public class Quick3way
{
private static void sort(Comparable[] a, int lo, int hi)
{// See page 289 for public sort() that calls this method.
if (hi <= lo) return;
int lt = lo, i = lo+1, gt = hi;
Comparable v = a[lo];
while (i <= gt)
{
int cmp = a[i].compareTo(v);
if(cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt–);
elsei++;
}// Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
}

Question 9

How do you implement the priority queue implementation of heapsort

Answer 9

private Key[] pq;// heap-ordered complete binary tree
private int N = 0;//in pq[1..N] with pq[0] unused

public MaxPQ(int maxN)
{pq = (Key[]) new Comparable[maxN+1];}

public boolean isEmpty()
{return N == 0;}

public int size()
{return N;}

public void insert(Key v)
{
pq[++N] = v;
swim(N);
}
private voidexch(int i, int j)
{Key t = pq[i]; pq[i] pq[j]; pq[j] = t;}
private booleanless(int i, int j)
{return pq[i].compareTo(pq[j]) < 0;}
private void swim(int k)
{
while (k > 1 && less(k/2, k))
{
exch(k/2, k);
k = k/2;
}
}
public Key delMax()
{
Key max = pq[1];// Retrieve max key from top.
exch(1, N–);// Exchange with last item.
pq[N+1] = null;// Avoid loitering.
sink(1);// Restore heap property.
return max;
}
private void sink(int k)
{
while (2k <= N)
{
int j = 2k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}

Question 10

How do you implement sequential search

Answer 10

public class SequentialSearchST<Key, Value>
{
private Node first;// first node in the linked list

private class Node
{// linked-list node
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next)
{
this.key= key;
this.val= val;
this.next = next;
}
}

public Value get(Key key)
{// Search for key, return associated value.
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key))
return x.val;// search hit
return null;// search miss
}

public void put(Key key, Value val)
{// Search for key. Update value if found; grow table if new.
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key))
{x.val = val; return;}// Search hit: update val.
first = new Node(key, val, first); // Search miss: add new node.
}
}

Question 11

How do you implement binary search

Answer 11

public class BinarySearchST<Key extends Comparable<Key>, Value>
{
private Key[] keys;
private Value[] vals;
private int N;</Key>

public BinarySearchST(int capacity)
{// See Algorithm 1.1 for standard array-resizing code.
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}

public int size()
{return N;}

public Value get(Key key)
{
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) return vals[i];
elsereturn null;
}

public int rank(Key key){
int lo = 0, hi = N-1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if(cmp < 0) hi = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;
}

public void put(Key key, Value val)
{// Search for key. Update value if found; grow table if new.
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0)
{vals[i] = val; return;}
for (int j = N; j > i; j–)
{keys[j] = keys[j-1]; vals[j] = vals[j-1];}
keys[i] = key; vals[i] = val;
N++;
}