Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

Princeton Algorithms P1W2 Stack and Queue, Basic Sorts

2017-01-03

stacks and queues

stack

stack: examine the item most recently added (last in; first out)
queue: examine the item least recently added (first in; first out)

Linked-list:

  • every operation takes constant time
  • use extra time and space to deal with links

Resizing array:

  • evray operation takes constant amortized time, total time is much less
  • less wasted space

linked-list representation

in section 1.3.

Every operation takes constant time in the worst case.
A stack with N items use \(\sim 40N\)

Node()

private Node first=null;
private class Node
{
    String item;
    Node next;
}

pop()

// save item to return
String item = first.item;
// delete first node
first = first.next;
// return saved item
return item;

push()

// save a link to the list
Node oldfirst = first;
// create a new node for the beginning
first = new Node();
// set the instance variables in the new node
firt.item = newitem;
first.next = oldfirst;

array implementation

  • use array s[ ] to store N items on stack
  • push(): add new item as s[N]
  • pop(): remove item from s[N-1]

Use between \(\sim 8N\) (when full) and \(\sim 32N\) (when one-quarter full) bytes to represent a stack with N items.
Defect: stack overflows when N exceeds capacity.

resizing arrays

How to grow and shrink array?

First try:

  • push(): increase size of array s[ ] by 1.
  • pop(): decrease size of array s[ ] by 1.

Too expensive.

  • need to copy all item to a new array.
  • inserting first N items takes time proportional to \(1+2+…+N \sim N^2/2\)

To grow array, if array is full, create a new array of twice the size, and copy items. Time proportional to N.

public ResizingArrayStackOfString()
{ s = new String[1]; }

public void push(String item)
{
    if (N == s.length) resize(2*s.length);
    s[N++] = item;
}

private void resize(int capacity)
{
    String[] copy = new String[capacity];
    for (i=0; i<N; i++) 
        copy[i] = s[i];
    s = copy;
}

To shrink the array: halve size of array s[ ] when array is one-quarter full.

public String pop()
{
    String item = s[--N];
    s[N] = null;
    if (N>0 && N == s.length/4) resize(s.length/2);
    return item
}

Every operation takes constant amortized time.

queues

maintain pointer to first and last nodes in a linked list;
insert/remove from opposite ends.

  • insert at end of linked list
  • remove from front of linked list

linked-list

dequeue

same code as linked-list stack pop()

String item = first.item;
first = first.next;
if (isEmpty()) last = null;
return item;

enqueue

// save a link to the last node
Node oldlast = last;
// create a new node for the end
Node last = new Node();
last.item = "not";
last.next = null;
// linke the new node to the end of the list 
if (isEmpty()) first = last;
else            oldlast.next = last;

full

public boolean isEmpty()
{ return first == null; }

resizing array

  • use array q[ ] to store items
  • enqueue(): add new item at q[tail]
  • dequeue(): remove item from q[head]
  • update head and tail modulo the capacity
  • add resizing array

generics

Want to implement StackOfURLs, StackOfInts, …

Avoid casting in client.

public class Stack<Item>
{
    private class Node
    {
        Item item;
        Node next;
    }
// ...
    public void push(Item item)
// ...
    public Item pop()
// ...
}

Generic array creation is not allowed in java. Use cast

public FixedCapacityStack(int capacity)
{ s = (Item[]) new Object[capacity]; }

declare and initialize a Stack of integers

Stack<Integer> stack = new Stack<Integer>();
// in java 7
Stack<Integer> stack = new Stack<>();

iterators

Support iteration over stack items by client, without revealing the internal representation of the stack. Make stack implement the Iterable interface.

Iterable: has a method that returns an Iterator

Iterator: has methods hasNext() and next()

public interface Iterable<Item>
{
    Iterator<Item> iterator();
}

public interface Iterator<Item>
{
    boolean hasNext();
    Item next();
    // void remove();
}
// foreach statement(shorthand)
for (String s : stack)
    StdOut.println(s);

Iterator in linked-list

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
...
    public Iterator<Item> iterator() 
    { return new ListIterator(); }
    
    private class ListIterator implements Iterator<Item>
    {
        private Node current = first;
        
        public boolean hasNext() 
        { return current != null; }
        public void remove()
        { /* not supported */ }
        public Item next()
        {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

Array iterator

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>
{
...
    public Iterator<Item> iterator() 
    { return new ReverseArrayIterator(); }
    
    private class ReverseArrayIterator implements Iterator<Item>
    {
        private int i = N;
        
        public boolean hasNext()
        { return i > 0; }
        public void remove()
        {/* not supported */ }
        public Item next()
        { return s[--i];    }
        
        
    }
}

bag API

Adding items to a collection and iterating (order doesn’t matter)
Implementation: Stack without pop or queue without dequeue.

  • Bag(): create an empty bag
  • void add(Item x): insert a new item onto bag
  • int size(): number of items in the bag
  • Iterable<Item> iterator(): iterator for all items in bag

applications

dangerous to use unfamiliar library.

java.util.list

java.util.Stack

java.util.Queue

Dijkstra’s two stack algorithm

elementary sorts

sorting introduction

Goal: sort any type of data (Double, String or java.io.File), without any information about the type of an item’s key.

Use callback = reference to executable code.

  • client passes array of objects to sort() function
  • the sort function calls back object’s compareTo() method as needed.

Call back implementation

  • Java: interfaces
  • C: function pointers
  • C++: class-typle functions
  • python, Javascript: first-class functions
// client
...
Insertion.sort(files);
...
// object implementation  
public class File implements Comparable<File>
{
    public int compareTo(File b) {...}
}
// sort implementation
public static void sort(Comparable[] a)
{
    ...
    if (a[i].compareTo(a[j-1]) < 0 )
    ...
}

comparable API

Implement compareTo() so that v.compareTo(w):

  • is a total order
  • returns a negative integer, zero or positive integer
  • throw an exception if incompatible types(or either is null)

example

public class Date implements Comparable<Date>
{
    private final int month, day, year;
    public Date(int m, int d, int y)
    {
        month = m;
        day = d;
        year = y;
    }
    public int compareTo(Date that)
    {
        if (this.year < that.year ) return -1;
        if (this.year > that.year ) return +1;
        if (this.month < that.month) return -1;
        if (this.month > that.month) return +1;
        if (this.day < that.day ) return -1;
        if (this.day > that.day ) return +1;
        return 0;
    }
}

two useful functions

// less 
private static boolean less(Comparable v, Comparable w)
{ return v.compareTo(w) < 0; }
// exchange
private static void exch(Comparable[] a, int i, int j)
{
    Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

selection sort

  1. In iteration i, find index min of smallest remaining entry.
  2. Swap a[i] and a[min]

Quadratic time \(\sim N^2/2\)

int N = a.length;
for (i = 0; i<N; i++)
{
    int min = i;
    for (j = i+1j<N; j++)
    {
        if (less(a[j],a[i])
            min = j;
    }
    exchange(a, min, i);
}
    

insertion sort

  1. In iteration i, swap a[i] with each larger entry to its left.

Best case: linear, linear for partially-sorted arrays;
Worst case: \(\sim N^2/2\) but slower than selection sort

int N = a.length;
for (int i = 0; i < N; i++)
    for (int j = i; j > 0; j--)
        if (less(a[j], a[j-1]))
            exch(a, j, j-1);
        else break;

shellsort

Move entries more than one position (h positions) at a time by h-sorting the array.

h-sorting

Insertion sort, with stride length h
h is an increment number like 7, 4, 1
A hm-sorted array remains hm-sorted after hn-sorted it.

increment sequence

\(3x+1\)
Sedgewick: 1,5,19,41,109,209…

code

worse case: \(O(N^{3/2})\)

int h = 1;
while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, ...

while (h >= 1)
{ // h-sort the array.
    for (int i = h; i < N; i++)
    {
        for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
            exch(a, j, j-h);
    }
    h = h/3;
}

shuffling

  • generate a random real number for each array entry
  • sort the array

Goal: rearrange array so that results is a uniformly random permutation in linear time.

Knuth shuffle

  • in iteration i, pick integer r between 0 and i uniformly at random
  • swap a[i] and a[r]
int N = a.length;
for (i = 0; i < N; i++)
{
    int r = StdRandom.uniform(i+1); // [0,i)
    exch(a,i,r);
}

convex hull

The convex hull of a set of N points it the smallest perimeter fence enclosing the points.
Output: sequence of vertices in counterclockwise order.

Graham scan

  1. choose point p with smallest y-coordinate
  2. sort points by polar angle with p
  3. consider points in order; discard unless it create ccw turn

challenges:

  1. Find point p with smallest y-coordinate:
    Define a total order, comparing by y-coordinate
  2. Sort points by polar angle with respect to p
    Define a total order for each point p
  3. Determine whether \(p_1 \rightarrow p_2 \rightarrow p_3\) is a counterclockwise turn
    Computational geometry
  4. sort efficiently
    Mergesort in \(N\log N\) time
  5. handle degeneracies(three or more points on a line)
    Require care, but not hard

ccw

for 3 points a, b, c, signed area \(Area(a,b,c)\):
\[2\times Area(a,b,c) = \left\vert \begin{array}{ccc} a_{x} & a_{y} & 1 \\ b_{x} & b_{y} & 1\\ c_{x} & c_{y} & 1 \end{array} \right\vert = (b_x -a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x)\]

  • Area > 0: \(a \rightarrow b \rightarrow c\) is counterclockwise
  • Area < 0: \(a \rightarrow b \rightarrow c\) is clockwise
  • Area = 0: \(a \rightarrow b \rightarrow c\) is collinear

code

Arrays.sort(p, Point2D.Y_ORDER);
Arrays.sort(p, p[0].BY_POLAR_ORDER);  

hull.push(p[0]);
hull.push(p[1]);

for (i = 2; i<N; i++)
{
    Point2D top = hull.pop;
    while (Point2D.ccw(hull.peek(), top, p[i]) <= 0 )
        top = hull.pop;
    hull.push(top);
    hull.push(p[i]);
}

Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.