1Basic Data StructuresCS211Fall 20002Limitations of Runtime Analysis■ Big-O can hide a large constant● Example: Selection● Example: small problems■ The problem you want to solve may not be the worst case● Example: Simplex method for linear programming■ Your program may not be run often enough to make analysis worthwhile● Example: one-shot vs. every day■ You may be analyzing and improving the wrong part of the program● Common situation● Should use profilingtools3Why Bother with Runtime Analysis?■ Computers are so fast these days that we can do whatever we want using just simple algorithms and data structures, can’t we?■ Well…not really; data-structure/algorithm improvements can be a very big win■ Scenario:● A runs in n2msec● A’ runs in n2/10 msec● B runs in 10 n log n msec■ Problem of size n=103● A: 103sec ≈ 17 minutes● A’: 102sec ≈ 1.7 minutes● B: 102sec ≈ 1.7 minutes■ Problem of size n=106● A: 109sec ≈ 30 years● A’: 108sec ≈ 3 years● B: 2 x 105sec ≈ 2 days1 day = 86,400 sec ≈ 105sec1,000 days ≈ 3 years4Strategies for Programming ProblemsGoal: Make it easier to solve programming problems■ Basic Data Structures● I recognize this; I can use this well-known data structure● Examples: Stack, Queue, Priority Queue, Hashtable, Binary Search Tree■ Algorithm Design Methods● I can design an algorithm to solve this● Examples: Divide & Conquer, Greedy, Dynamic Programming■ Problem Reductions● I can change this problem into another with a known solution● Or, I can show that a reasonable algorithm is most-likely impossible● Examples: reduction to network flow, NP-complete problems5Recall: Use of Objects Encourages…■ Abstraction● Avoid details● Distill down to fundamental parts■ Encapsulation● Information hiding● Our code depends on the available operations, but not on how they are implementedWhy use these ideas?● Basically, because they seem to help● Result in clean interfaces, easier modification, portable code6Abstract Data Types (ADTs)■ A method for achieving abstraction for data structures and algorithms■ ADT = model + operations■ Describes what each operation does, but not how it does it■ An ADT is independent of its implementation■ In Java, an interfacecorresponds well to an ADT● The interface describes the operations, but says nothing at all about how they are implemented■ Example: Stack interface/ADTpublic interface Stack {public void push (Object x);public Object pop ( );public Object peek ( );public boolean isEmpty ( );public void makeEmpty ( );}27Array Implementation of Stackclass StackArray implements Stack {Object [ ] s; // Holds the stackint top; // Index of stack toppublic StackArray(int max) // Constructor{s = new Object [max]; top = -1;}public void push (Object item) {s [++top] = item;}public Object pop ( ) {return s [top – –];}public Object peek ( ) {return s [top];}public boolean isEmpty( ) {return top == -1;}public void makeEmpty( ) {top = -1;}}// Better for garbage collection if makeEmpty( ) also cleared the arraymax-132103topO(1) worst-case time for each operation8Linked List Implementation of Stackclass StackLinked implements Stack {class Node {Object data; Node next; // An inner classNode (Object d, Node n) // Constructor for Node{data = d; next = n;}}Node top; // Top Node of stackpublic StackLinked ( ) {top = null;} // Constructorpublic void push (Object item) {top = new Node(item,top);}public Object pop ( ) {Object temp = top.data; top = top.next; return temp;}public boolean isEmpty ( ) {return top == null;}public void makeEmpty ( ) {top = null;}}topO(1) worst-case time for each operationNote that the array implementation can overflow, but the linked list version can’t9ADT QueueOperations:void enQueue (Object x);Object deQueue ( );Object peek ( )boolean isEmpty ( );void makeEmpty ( );▲ Text uses getFront( ) instead of peek( )Possible implementationsLinked ListheadlastArray with wraparound(can overflow)head lastArray with head always at A[0](deQueue( ) becomes expensive) (can overflow)last10ADT DictionaryOperations:void insert (Object key,Object value);void update (Object key, Object value);Object find (Object key);void remove (Object key);void makeEmpty ( );Think of key = word; value = definition■Uses:● Symbol tables● Wide use within other algorithmsArray implementations■ Update( ) and find ( ) use Binary Search■ Can use Binary Search for remove( ), but then find( ) doesn’t work■ Can use special “removed” mark to make find( ) work againO(1) or O(n)O(1) or O(n)makeEmptyO(n)O(n)removeO(n)O(log n)findO(n)O(log n)updateO(1)O(n)insertunsortedsorted11Multiple Dictionary ImplementationsO(log n)O(log n)O(1)removeworst-caseO(log n)O(log n)O(log n)Balanced Treeexpected(sort of)O(log n)O(log n)O(log n)Binary Search Tree (BST)expectedO(1)O(1)O(1)Hashtablefindupdateinsert12ADT Priority QueueOperations:void insert (Object x);Object getMax ( );boolean isEmpty ( );Uses:● Job scheduler● Event-driven simulation● Wide use within other algorithmsO(log n)O(log n)HeapO(1)O(n)Sorted ArrayO(n)O(1)Unsorted ArrayO(n)O(1)Linked
View Full Document
Unlocking...