Algorithms - Princeton University
AlgorithmsR OBERT S EDGEWICK K EVIN W AYNE1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsF O U R T HE D I T I O NR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
Stacks and queuesFundamental data types.・Value: collection of objects.・Operations: insert, remove, iterate, test if empty.・Intent is clear when we insert.・Which item do we remove?stackpushpopqueueenqueuedequeueStack. Examine the item most recently added.LIFO "last in first out"Queue. Examine the item least recently added.FIFO "first in first out"2
Client, implementation, interfaceSeparate interface and implementation.Ex: stack, queue, bag, priority queue, symbol table, union-find, . Benefits.・Client can't know details of implementation client has many implementation from which to choose.・Implementation can't know details of client needs many clients can re-use the same implementation.・Design: creates modular, reusable libraries.・Performance: use optimized implementation where it matters.Client: program using operations defined in interface.Implementation: actual code implementing operations.Interface: description of data type, basic operations.3
1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
Stack APIWarmup API. Stack of strings data type.pushpoppublic class StackOfStringsStackOfStrings()void push(String item)String pop()boolean isEmpty()int size()create an empty stackinsert a new string onto stackremove and return the stringmost recently addedis the stack empty?number of strings on the stackWarmup client. Reverse sequence of strings from standard input.5
How to implement a stack with a linked list?A.Can't be done efficiently with a singly-linked list.top of stackB.itwasthebestofnullbestthewasitnulltop of stackC.of6
Stack: linked-list implementation・Maintain pointer first to first node in a singly-linked list.・Push new item before first.・Pop item from first.top of stackofbestthewasitnullfirst7
Stack pop: linked-list implementationsave item to returnString item first.item;delete first nodeinner classprivate class Node{String item;Node next;}first first.next;firstorbetonullfirstorbetonullreturn saved itemreturn item;Removing the first node in a linked list8
Stack push: linked-list implementationsave a link to the listNode oldfirst first;oldfirstfirstinner classprivate class Node{String item;Node next;}orbetonullcreate a new node for the beginningfirst new Node();oldfirstfirstorbetonullset the instance variables in the new nodefirst.item "not";first.next oldfirst;firstnotorbetonullInserting a new node at the beginning of a linked list9
Stack: linked-list implementation in Javapublic class LinkedStackOfStrings{private Node first null;private class Node{String item;Node next;}public boolean isEmpty(){ return first null;private inner class(access modifiers for instancevariables don't matter)}public void push(String item){Node oldfirst first;first new Node();first.item item;first.next oldfirst;}public String pop(){String item first.item;first first.next;return item;}}10
Stack: linked-list implementation performanceProposition. Every operation takes constant time in the worst case.Proposition. A stack with N items uses 40 N bytes.node object (inner class)public class Node{String item;inner classNode next;.private classNode}{String item;Node next;}40 bytesobjectoverhead16 bytes (object overhead)extraoverhead8 bytes (inner class extra overhead)8 bytes (reference to String)itemreferencesnext8 bytes (reference to Node)40 bytes per stack nodeRemark. This accounts for the memory for the stack(but not the memory for strings themselves, which the client owns).11
How to implement a fixed-capacity stack with an array?A.Can't be done efficiently with an array.top of 89timesofbestthewasitnullnullnullnull0123456789top of stackC.12
Fixed-capacity stack: array implementation・Use array s[] to store N items on stack.・push(): add new item at s[N].・pop(): remove item from s[N-1].top of 789Ncapacity 10Defect. Stack overflows when N exceeds capacity. [stay tuned]13
Fixed-capacity stack: array implementationpublic class FixedCapacityStackOfStrings{private String[] s;private int N 0;a cheat(stay tuned)public FixedCapacityStackOfStrings(int capacity){ s new String[capacity]; }public boolean isEmpty(){ return N 0; }public void push(String item){ s[N ] item; }public String pop(){ return s[--N]; }use to index into array;then increment N}decrement N;then use to index into array14
Stack considerationsOverflow and underflow.・Underflow: throw exception if pop from an empty stack.・Overflow: use resizing array for array implementation. [stay tuned]Null items. We allow null items to be inserted.Loitering. Holding a reference to an object when it is no longer needed.public String pop(){ return s[--N]; }loiteringpublic String pop(){String item s[--N];s[N] null;return item;}this version avoids "loitering":garbage collector can reclaim memory foran object only if no outstanding references15
1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
Stack: resizing-array implementationProblem. Requiring client to provide capacity does not implement API!Q. 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.infeasible for large N・Need to copy all items to a new array, for each operation.・Array accesses to insert first N items N (2 4 2(N – 1))1 array accessper push N 2.2(k–1) array accesses to expand to size k(ignoring cost to create new array)Challenge. Ensure that array resizing happens infrequently.17
Stack: resizing-array implementation"repeated doubling"Q. How to grow array?A. If array is full, create a new array of twice the size, and copy items.public ResizingArrayStackOfStrings(){ 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 (int i 0; i N; i )copy[i] s[i];s copy;}Array accesses to insert first N 2i items. N (2 4 8 N) 3N.1 array accessper pushk array accesses to double to size k(ignoring cost to create new array)18
Stack: resizing-array implementationQ. How to shrink array?First try.・push():・pop():double size of array s[] when array is full.halve size of array s[] when array is one-half full.Too expensive in worst case.・Consider push-pop-push-pop- sequence when array is full.・Each operation takes time proportional to N.N 5tobeornotN 4tobeornotN 5tobeornotN 4tobeornottonullnullnulltonullnullnull19
Stack: resizing-array implementationQ. How to shrink array?Efficient solution.・push():・pop():double size of array s[] when array is full.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;}Invariant. Array is between 25% and 100% full.20
Stack resizing-array implementation: performanceAmortized analysis. Starting from an empty data structure, averagerunning time per operation over a worst-case sequence of operations.Proposition. Starting from an empty stack, any sequence of M push andpop operations takes time proportional to zedoubling andhalving operationsorder of growth of running timefor resizing stack with N items21
Stack resizing-array implementation: memory usageProposition. Uses between 8 N and 32 N bytes to represent a stackwith N items.・ 8 N when full.・ 32 N when one-quarter full.public class ResizingArrayStackOfStrings{8 bytes array sizeprivate String[] s;private int N 0; }Remark. This accounts for the memory for the stack(but not the memory for strings themselves, which the client owns).22
Stack implementations: resizing array vs. linked listTradeoffs. Can implement a stack with either resizing array or linked list;save a link to the listclient can useNodeinterchangeably.oldfirst first; Which one is better?oldfirstLinked-list implementation.firstorbe・extra time and space to deal with the links.・Usescreatea new node for the beginningtoEvery operation takes constant timein the worst case.nullfirst new Node();Resizing-array implementation.oldfirst・Every operation takes constant amortized time.・Less wasted space.firstorbetonullset the instance variables in the new nodeN 4to "not";beorfirst.itemfirst.next rting a new node at the beginning of a linked list23
1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
Queue APIenqueuepublic class QueueOfStringsQueueOfStrings()void enqueue(String item)String dequeue()boolean isEmpty()int size()create an empty queueinsert a new string onto queueremove and return the stringleast recently addedis the queue empty?number of strings on the queuedequeue25
How to implement a queue with a linked list?A.Can't be done efficiently with a singly-linked list.back of queueB.timesfront of queueofbestthewasfront of queueC.ititnullback of queuewasthebestoftimesnull26
Queue: linked-list implementation・Maintain one pointer first to first node in a singly-linked list.・Maintain another pointer last to last node.・Dequeue from first.・Enqueue after last.front of queueitfirstback of queuewasthebestoftimesnulllast27
Queue dequeue: linked-list implementationsave item to returnString item first.item;delete first nodefirst first.next;inner classlastfirstprivate class Node{String item;Node next;}tobeornullfirstlasttobeornullreturn saved itemreturn item;Removing the first node in a linked listRemark. Identical code to linked-liststack pop().28
Queue enqueue: linked-list implementationsave a link to the last nodeNode oldlast last;oldlastlastfirstinner classprivate class Node{String item;Node next;}tobeornullcreate a new node for the endlast new Node();last.item "not";oldlastfirsttobelastornullnotnulllink the new node to the end of the listoldlast.next last;oldlastfirsttobelastorInserting a new node at the end of a linked listnotnull29
Queue: linked-list implementation in Javapublic class LinkedQueueOfStrings{private Node first, last;private class Node{ /* same as in LinkedStackOfStrings */public boolean isEmpty(){ return first null;}}public void enqueue(String item){Node oldlast last;last new Node();last.item item;last.next null;if (isEmpty()) first last;elseoldlast.next last;}special cases forempty queuepublic String dequeue(){String item first.item;first first.next;if (isEmpty()) last null;return item;}}30
How to implement a fixed-capacity queue with an array?A.Can't be done efficiently with an array.front of queueB.back of back of queueC.front of 31
Queue: resizing-array implementation・Use array q[] to store items in queue.・enqueue(): add new item at q[tail].・dequeue(): remove item from q[head].・Update head and tail modulo the capacity.・Add resizing array.front of queueq[]back of 789headtailcapacity 10Q. How to resize?32
1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
Parameterized stackWe implemented: StackOfStrings.We also want: StackOfURLs, StackOfInts, StackOfVans, .Attempt 1. Implement a separate stack class for each type.・Rewriting code is tedious and error-prone.・Maintaining cut-and-pasted code is tedious and error-prone.@# *! most reasonable approach until Java 1.5.34
Parameterized stackWe implemented: StackOfStrings.We also want: StackOfURLs, StackOfInts, StackOfVans, .Attempt 2. Implement a stack with items of type Object.・Casting is required in client.・Casting is error-prone: run-time error if types mismatch.StackOfObjects s new StackOfObjects();Apple a new Apple();Orange b new Orange();s.push(a);s.push(b);a (Apple) (s.pop());run-time error35
Parameterized stackWe implemented: StackOfStrings.We also want: StackOfURLs, StackOfInts, StackOfVans, .Attempt 3. Java generics.・Avoid casting in client.・Discover type mismatch errors at compile-time instead of run-time.type parameterStack Apple s new Stack Apple ();Apple a new Apple();Orange b new Orange();s.push(a);s.push(b);compile-time errora s.pop();Guiding principles. Welcome compile-time errors; avoid run-time errors.36
Generic stack: linked-list implementationpublic class LinkedStackOfStrings{private Node first null;}public class Stack Item {private Node first null;private class Node{String item;Node next;}private class Node{Item item;Node next;}public boolean isEmpty(){ return first null;public boolean isEmpty(){ return first null;}generic type name}public void push(String item){Node oldfirst first;first new Node();first.item item;first.next oldfirst;}public void push(Item item){Node oldfirst first;first new Node();first.item item;first.next oldfirst;}public String pop(){String item first.item;first first.next;return item;}public Item pop(){Item item first.item;first first.next;return item;}}37
Generic stack: array implementationthe way it should bepublic class FixedCapacityStackOfStrings{private String[] s;private int N 0;}public class FixedCapacityStack Item {private Item[] s;private int N 0;public .StackOfStrings(int capacity){ s new String[capacity]; }public FixedCapacityStack(int capacity){ s new Item[capacity]; }public boolean isEmpty(){ return N 0; }public boolean isEmpty(){ return N 0; }public void push(String item){ s[N ] item; }public void push(Item item){ s[N ] item; }public String pop(){ return s[--N]; }public Item pop(){ return s[--N];}}@# *! generic array creation not allowed in Java38
Generic stack: array implementationthe way it ispublic class FixedCapacityStackOfStrings{private String[] s;private int N 0;public class FixedCapacityStack Item {private Item[] s;private int N 0;public .StackOfStrings(int capacity){ s new String[capacity]; }public FixedCapacityStack(int capacity){ s (Item[]) new Object[capacity]; }public boolean isEmpty(){ return N 0; }public boolean isEmpty(){ return N 0; }public void push(String item){ s[N ] item; }public void push(Item item){ s[N ] item; }public String pop(){ return s[--N]; }public Item pop(){ return s[--N];}}}the ugly cast39
Unchecked cast% javac FixedCapacityStack.javaNote: FixedCapacityStack.java uses unchecked or unsafe operations.Note: Recompile with -Xlint:unchecked for details.% javac -Xlint:unchecked FixedCapacityStack.javaFixedCapacityStack.java:26: warning: [unchecked] unchecked castfound: java.lang.Object[]required: Item[]a (Item[]) new Object[capacity]; 1 warningQ. Why does Java make me cast (or use reflection)?Short answer. Backward compatibility.Long answer. Need to learn about type erasure and covariant arrays.40
Generic data types: autoboxingQ. What to do about primitive types?Wrapper type.・Each primitive type has a wrapper object type.・Ex: Integer is wrapper type for int.Autoboxing. Automatic cast between a primitive type and its wrapper.Stack Integer s new Stack Integer ();s.push(17);int a s.pop();// s.push(Integer.valueOf(17));// int a s.pop().intValue();Bottom line. Client code can use generic stack for any type of data.41
1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
IterationDesign challenge. Support iteration over stack items by client,without revealing the internal representation of the 56789firsttimesNcurrentofbestthewasitnullJava solution. Make stack implement the java.lang.Iterable interface.43
Iteratorsjava.lang.Iterable interfaceQ. What is an Iterable ?A. Has a method that returns an Iterator.Q. What is an Iterator ?public interface Iterable Item {Iterator Item iterator();}java.util.Iterator interfaceA. Has methods hasNext() and next().Q. Why make data structures Iterable ?A. Java supports elegant client code.“foreach” statement (shorthand)for (String s : stack)StdOut.println(s);public interface Iterator Item {boolean hasNext();Item next();optional; usevoid remove();at your own risk}equivalent code (longhand)Iterator String i stack.iterator();while (i.hasNext()){String s i.next();StdOut.println(s);}44
Stack iterator: linked-list implementationimport 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(){throw UnsupportedOperationExceptionItem item current.item;throw NoSuchElementExceptionif no more items in iterationcurrent current.next;return item;}}}firsttimescurrentofbestthewasitnull45
Stack iterator: array implementationimport 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() {public void remove(){public Item next(){return i 0;/* not supported */return ll012345678946
Iteration: concurrent modificationQ. What if client modifies the data structure while iterating?A. A fail-fast iterator throws a nt modificationfor (String s : stack)stack.push(s);Q. How to detect?A.・Count total number of push() and pop() operations in Stack.・Save counts in *Iterator subclass upon creation.・If, when calling next() and hasNext(), the current counts do not equalthe saved counts, throw exception.47
1.3 B AGS , Q UEUES, AND S TACKS‣ stacks‣ resizing arraysAlgorithmsR OBERT S EDGEWICK K EVIN W AYNEhttp://algs4.cs.princeton.edu‣ queues‣ generics‣ iterators‣ applications
Java collections libraryList interface. java.util.List is API for an sequence of items.public interface List Item implements Iterable Item List()boolean isEmpty()int size()create an empty listis the list empty?number of itemsvoid add(Item item)append item to the endItem get(int index)return item at given indexItem remove(int index)boolean contains(Item item)Iterator Item iterator()return and delete item at given indexdoes the list contain the given item?iterator over all items in the list.Implementations. java.util.ArrayList uses resizing array;java.util.LinkedListuses linked list.caveat: only someoperations are efficient49
Java collections libraryjava.util.Stack.・Supports push(), pop(), and iteration.・Extends java.util.Vector, which implements java.util.Listinterface from previous slide, including get() and remove().・Bloated and poorly-designed API (why?)Java 1.3 bug report (June 27, 2001)The iterator method on java.util.Stack iterates through a Stack fromthe bottom up. One would think that it should iterate as if it werepopping off the top of the Stack.status (closed, will not fix)It was an incorrect design decision to have Stack ex
Stack implementations: resizing array vs. linked list N 4 to be or not null null null null to be Inserting a new node at the beginning of a linked list first new Node(); Node oldfirst first; first or to be or oldfirst oldfirst first save a link to the list create a new node for the beginning set the instance variables in the new node .
yDepartment of Electrical Engineering, Princeton University, Princeton, NJ 08544-5263 (jdurante@princeton.edu). zDepartment of Operations Research and Financial Engineering, Princeton University, Princeton, NJ 0854
25 Valley Road, Princeton, New Jersey 08540 t 609.806.4204 f 609 .806.4225 October 16, 2013 Honorable President and Members of the Princeton Board of Education Princeton Public Schools County of Mercer Princeton
Princeton Admission Office Box 430 Princeton, NJ 08542-0430 www.princeton.edu Experience Princeton EXPERIENCE PRINCETON 2019-20 Office of Admission . Finance Gender and Sexuality Studies Geological Engineering Global Health and Health Policy Hellenic Studies History and the Practice of Diplomacy
Douglas S. Massey Curriculum Vitae June 4, 2018 Address: Office of Population Research Princeton University Wallace Hall Princeton, NJ 08544 dmassey@princeton.edu Birth: Born October 5, 1952 in Olympia, Washington, USA Citizenship: Citizen and Resident of the United States Education: Ph.D., Sociology, Princeton University, 1978 M.A., Sociology, Princeton University, 1977
A tutorial on Bayesian nonparametric models Samuel J. Gershmana, , David M. Bleib a Department of Psychology and Princeton Neuroscience Institute, Princeton University, Princeton NJ 08540, USA b Department of Computer Science, Princeton University, Princeton NJ 08540, USA article info
Quantitative Spatial Economics Stephen J. Redding and Esteban Rossi-Hansberg Department of Economics and Woodrow Wilson School of Public and International Affairs, Princeton University, Princeton, New Jersey 08544; email: reddings@princeton.edu, erossi@princeton.edu Annu. Rev. Econ. 2017. 9:21-58 The Annual Review of Economics is online at
CONTENTS Highlights 1 In a Nutshell 5 Textbooks 6 Princeton Frontiers in Physics 7 Biological Physics 8 Condensed Matter 9 Quantum Physics 9 Astronomy & Astrophysics 10 Princeton Series in Astrophysics 12 Princeton Series in Modern Observational Astronomy 13 Princeton Series in Physics 13 Mathematics, Mat
applied mathematics and control theory. By the nature of its . Princeton University, Princeton, NJ 08544 USA (e-mail: gfyoung@princeton.edu; naomi@princeton.edu). L. Scardovi is with the Department of Electrical and Computer Engineering, . In the companion paper
