Algorithms and Data Structures
Algorithms and Data Structures CS 200
Popular in Course
Popular in ComputerScienence
This 40 page Class Notes was uploaded by Betty Kertzmann on Monday September 21, 2015. The Class Notes belongs to CS 200 at Colorado State University taught by Adele Howe in Fall. Since its upload, it has received 6 views. For similar materials see /class/210170/cs-200-colorado-state-university in ComputerScienence at Colorado State University.
Reviews for Algorithms and Data Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/21/15
CSZmei Balanced Search Trees i i Efficiency of binary search tree is function of CSZOO Balanced he39ght Height of a binary search tree of n Items It Maximum n l quot 7 Minimum logzn 1 Height of a binary search tree depends on the walls 8 M39rmrs Chapter 131 order of insertions and deletions Balanced search trees modify representation and algorithm to better manage height 23 C5209 7K CSZOCl gaK F 2 3 Trees Data Structure uh uh Ii Ii Ii Ii Properties 6 each internal node has either two or three children All leaves are at the same level Search keys lt S Search keys gt S Search keys lt S Search keys gt L Search keys gt S and lt L 2 node a single item 3node two items whose whose search key is search keys 8 and L satisfy gt left child s search keys left child s search keys lt S lt I lt right Child s keys middle child s search keys middle child s search keys lt L A 23 tree with n nodes has height lt log2n 1 lt 9m Ch39ld s searCh keWS Traversing 23 Trees inorderin ttTreetonhreeTree if ttTree s root node is a leaf visit the data items else if root has two data items inorder1eft subtree visit rst data item inordermiddle subtree visit second data item inorderright subtree else root has one data item inorder1eft subtree visit data item inorder right subtree c5200 pagi Fi Iii li d What is the property of inorder traversal of binary search trees Is it maintained for 23 trees CSZOQJiI in El Searching 23 Trees 1 3 g Analogous to binary search trees Number of comparisons required to search a 23 tree Approximately equal to the number of comparisons required to search a binary search tree that is as balanced as possible Insert Example CSZOQE7 91quot I Inserting 39 space available in leaf Which is C5200 9 Insert Example cont en 5 Inserting 38 no space in leaf but space in parent 20 40 e em cszoo hx Insert Example cont ii Ii Inserting 37 space in leaf 30 39 70 90 I m a o oo cs zog k Insert Example cont ii Insert 36 No space in leaf or immediate parent a 30 39 b 61 IO 20 C36 37 38 30 37 39 i 23 Insert Algorithm a 7 S M L I To insert an item Locate the leaf at which the search would terminate Insert the new item into the leaf If the leaf now contains only two items you are done If the leaf now contains three items split the leaf into two nodes n1 and n2 If the parent contains two items you are done OthenNise it contains three items and has 4 children continue on next slide cszooj i a 23 Insert Algorithm cont When an internal node contains 3 items Split the node into two nodes Accommodate the node s children c5209 23 Insert cont 1 i 1 at 1 New root Rootr gt n a a b c d a b c d I When the root contains three items Split the root into two nodes Create a new root node csaz j K 7 23 Delete Example a 39239 Deleting 7O Swap with inorder successor cszog if It i 23 Delete Example cont it i Deleting 70 w 0 910 Delete value from leatC Merge nodes by deleting empty leaf and moving 80 down 23 Delete Example cont i Next step Delete 100 23 Delete Example cont wig0 1 a 60 80 G Delete value from leaf Doesn t work Redistribute 65209 H 23 Delete Example cont Deleting 80 23 Delete Example cont Deleting 80 lt Node becomes empty Delete value from leaf Merge by moving 90 down and removing empty leaf a Swap with inorder successor cszoofqx 7 23 Delete Example cont 5 Deleting 80 e lt Root becomes empty Merge move 50 down adopt empty leaf39s child remove empty node Remove empty root cszoo 23 Delete Algorithm 1 Locate the node that needs to be deleted 2 If it s not a leaf find its inorder successor and swap 3 If the leaf contains two items you can just delete one 4 OthenNise deletion would leave an empty node need to do some more work cszogj g cszoo C e Redistribute a Empty n node n e o a b c d b c d a d 0 Merge Empty a 0 node n a b c a b c Same operations are performed in interior nodes 23 Delete Conceptual cont i 2 3 Delete Conceptual a Redistribute a gt 3 0 Sibling Leaf Sibling Leaf b Sibling Leaf c5200 2 3 Delete Conceptual cont ii i e 6 Empty root Delete Height h 5 L j 5 L Height h 1 a b c a b C If the root becomes empty simply delete it Comparison with Binary Search 0522451 Trees mfni A 23 tree is guaranteed to be balanced A 23 will usually have reduced height in comparison to a balanced binary search tree but requires more time to go through each node 39 C5200 CompleXIty of 23 Trees If u d Insen Delete CSZOQR7 BTrees 9 23 tree are a special case of Btrees A lt keyi ltA key1 keyz keys key4 keVk1 l The Btree39s creators Rudolf Bayer and Ed McCreight have not explained what if anything the B stands for 632 Linear timeordered structures mini Data structures that reflect a temporal 20ng relationship Ii i Ii Linear Structures order of removal based on order ofinsertion I eg first comefirst serve l StaCkS Walls 7 first in first outFIFO I Queues Walls Ch 8 take from the top of the pile last in first out LIFO CSZOQR7 C5209 9 3 H Stacks u Stack ADT u d g Last In First Out LIFO structure Create eg top Query a pile of papers 39 Empty a stack of plates in a cafe 39 Retr39eve quot get f39rSt 39tem AddRemove done from same end of 39 Add structure Push add With constraint on posmon both from top head of list in a typical I Remove implementation Pop remove With constraints Remove all csigz i Stack Methods 5 3 a pushin newItemStackItemType throws StackException adds a new item to the top of the stack Exception when insertion fails popStackItemType throws StackException deletes the top item from the stack and returns it Exception when deletion fails peekStackItemType query throws StackException returns the top item from the stack but does not remove it Exception when retrieval fails Stack Application eggli Runtime Stack 15 i Recursive invocations tracked on call stack First method that returns is the last one invoked which returns to the second to the last one Element of call stack call frame aka activation record parameters and return values local variables return address pointer to next instruction to be executed in calling method Stack Application eggIRE Depth First Search hm Consider looking for a path in a maze Strategy keep turning right straight or left if others aren t options until get to dead end or goal backtrack at dead ends and try different turn Stack application 65345 Prefix expressions i a 5 How is this implemented In our recursive descent parser In Java stacks are used in Java Virtual Machine for call mechanism and expression evaluation 652211 Evaluating a Postfix Expression i 3 a while there are input tokens left read the next token if the token is a value push it onto the stack else the token is a function taking n arguments pop the top n values from the stack and evaluate the function push the result on the stack If there is only one value in the stack return it as the result else throw an exception Stack Application Balancing Braces CSZOQJiI in El ll How can we use a stack to determine whether the braces In a string are balanced abcdefgijk 1mn opqr abcdefghijk1m Stack Implementation 683 ArrayList g39 m Push use add add to the end ofthe ArrayList worst case complexity On but ONLY when running out of capacity Pop use getsize 1 to save return value use remove size1 to destructiver modify the stack Peek use getsize 1 What if we push and pop at index 0 Every push pop is On Stack Implementation Linked List c5209 public class StackReferenceBased implements StackInterface private Node top public StackReferenceBasedO top null public boolean isEmptyO return top null public void push0bject newItem top new NodenewItem top Public class Node private Object item private Node next Stacklmplementation 653 Linked List cont 393 a public Objeot pop throws StaokExoeption if lisEmptyO Node temp top top topgetNext return tempgetItem else throw new StaokExoeption Stack Implementation wigEL Sineg Linked List 15 r I PUSh use add 1 ADT List worst case complexity 01 Pop use remove1 ADT List worst case complexity 01 Peek use get1 ADT List Why not use addremove data from the tail csg K Stack API in Java g39 m public class StackltEgtextends VectorltEgt The stack class represents a lastinfirst out LIFO stack of objects It extends class Vector with five operations that allow a vector to be treated as a stack The usual push and pop operations are provided as well as a method to peek at the top item on the stack a method to test for whether the stack is empty and a method to search the stack for an item and discover how far it is from the top from jaVa sun com Problem c5209 F Queues Ii 1 I First In First OutFFO structure Imagine a checkout line So removing and addi ends of tructure e done from opposite add to tail remove from head typical Used in operating systems forjobs done in one go eg print jobs batch jobs Which structure can be used for timesliced jobs El Queue Methods cszogj gm H lh It enqueuein neWIteszueueItemType adds a new item to the tail of the queue Throws exception if not successful dequeueQueueItemType deletes the first item from the head of the queue and returns it Throws exception if not successful peekQueueItemType returns the first item from the head of the queue but does not remove it Throws exception if not successful Queue Implementation 652 i Using ArrayList 5 Enqueue use add adds to the end of the ArrayList Dequeue use getO to get return value use removeO to destructively modify the queue Peek I use Problem how much time is required Na39ive ArrayBased Implementation items cszooflXw Ia o 3 2 4 1 MAXQUEUE 1 lt Array indexes front back 0 I 2 3 items lb 47 49 6 10 front back 0 I 47 48 2 49 L MAX OUEUE I Drift can cause the queue to appear full How do we initialize front and back Hint how does a queue with a single element look like Queue Implementation c52 h Using Arrays a Use wraparound array structure number of elements in queue headindex enqueue add to next open position increment count dequeue remove from head by incrementing head decrement count peek use head index cszooj g 7 1 h A ArraYBased Implementation L A wraparound array eliminates the front problem of drift MAX QUEUE 1 enqueue 1 back backl MAXQUEUE itemsback newItem count 2 dequeue frontItem itemsfront front frontl MAXQUEUE back count Initialization peek front to 0 return item at front back t0 MAXQUEUEl Issues With ArrayBased wayeh Implementation r a u Determining full front and back cannot be used to distinguish between queuefull and queueempty conditions CSZOClJ Kni H ArrayBased Example in a The effect of some queue operations 1 1 front 1 front 394 2 2 vast 1ck 1ck baCk4 3 ArrayBased Issues cont ini Queue with single item gt Delete item queue becomes empty MAXQUEUE 1 O MAXQUEUE 1 0 u 5 v 2 5 2 4T 3 front 4T 3 back back front front passes back when the queue becomes empty Determining Full in ArrayBased 6523i Queue 1 a Queue with single empty slot gt Insert 9 queue becomes full MAXQUEUE4 0 MAXQUEUE 4 0 visa W 4 T3 4T 3 front back back back catches up to front when the queue becomes full front Solution count of items C5329 cher Approaches 5 a a Use a flag full to distinguish between the full and empty conditions Declare MAXQUEUE 1 locations for the array items but use only MAXQUEUE of them for queue items Queue Implementation ng in Using DLL ii i DLL is symmetric two choices enqueue at head or tail Enqueue use edd0 method Dequeue use remove method at size Peek use get method How can we use SLL without losing on order of complexity ReferenceBased Queue eggi Implementation 5 h 1 A linked list with two external references A reference to the front A reference to the back a 2 e gt 4 7 e e firstNode At which end do we dequeue lastNode V 0 V ReferenceBased Queue 6823 ReferenceBased Queue ll 6523 lmplementatlon II an en Enqueue an a A circular linked list with one external Enqueueing an item into a nonempty queue reference l newNode setNext lastNode getNext 2 lastNode setNext newNode lastNode references the back of the queue J I f N l 2 l gt 4 1 l gt 39 3 l D 3 lastNode newNode b 2 gt 4 gt 1 gt 7 l e lastNode newNode references new node lastNode ReferenceBased Queue ll 652 ReferenceBased egg xi Enqueue cont 1 Implementation ll Dequeue Enqueueing an item into an empty queue Dequeuelng an Item from a queue of more than one Item a b I39 mg 3 3 newNode setNeXt newNode lastNode newNode l l firstNode lastNodegetNext I A I Z gt 4 gt 1 gt 7 2 lastNode setNext firstNode getNext lastNode newNode lastNode newNode lg firstNode lastNode 65200 951 Deque mim g public interface DequeltEgt extends QueueltEgt A linear collection that supports element insertion and removal at both ends The name deque is short for quotdouble ended queuequot and is usually pronounced quotdeckquot Most Deque implementations place no fixed limits on the number of elements they may contain but this interface supports capacityrestricted deques as well as those with no fixed size limit From java sun com While Java has a Stack class its usage is discouraged 20ng i Defining Languages Walls amp Mirrors Ch 62 CSZOQJEI in El Definitions 15 Language is a set of strings of symbols from a finite alphabet Grammar is a set of rules that the strings must follow Recognition Algorithm determines whether a string is a member of the language csg K Grammarfor Java Identifiers unim ltidentl39 ergt ltlettergt ltidentl39 ergt ltlettergt ltidentl39 ergt ltdigitgt ltidenti ergt lt139dentl39 ergt ltlettergtab zAB Z ltdigitgt0 1 9 x l y means x or y x y means x followed by y lt word gt is called a nonterminal which can be replaced by other symbols depending on the rules Terminals are symbols eg letters words from which legal strings are constructed Rules have the form ltwordgt C8209 F Syntax Diagrams aquot Java Identifier c5209 1 28209 Java Class ii 3 g Example Prefix Expressmns 1quot 1 ltClussdeclumti0ngt ltm0d139 ergt class ltl39dentl39 ergt extends ltClussnumegt Types of Algebraic Expressions Prefix Postfix RPN Infix Examples 1 5 4 3 2 5 4 3 3 5 4 3 4 5 4 3 implements ltinterfucenumegt ltinterfucenumegt lt elddeclamtiongt cszogjm 68209 Example Prefix Expressions g 1 Example Other Expressions 5 3 1 Due to lack of ambiguity pre x and postfix are Grammar easier to parse ltpre xgt lt139dentl39 ergt lt0pemtorgt ltpre xgt ltpre xgt Grammar lt0Pm1f07gt ltpre xgt lt139dentl39 ergt lt0pemtorgt ltpre xgt ltpre xgt ltid nti Wgt a I b I I Z lt0pemtorgt I POStfiX lt139dentl39 ergta b z Unary operators cszoglngi Ii Parsing 5 3 a 5384 1 Recognize the structure of the expression terminology PARSE the expression 2 Build the tree while parsing Evaluating an expression tree CSZOQJiI El ll When visiting a node use the results of its children to evaluate it Walk the tree in postorder How do we know the original expression is valid CSZOQE7 5mg Recognizmg Languages hm Parsing checks a sequence of symbols to determine whether it obeys rules in a grammar and assigns the symbols to nonterminals from the grammar Simple parsing Top down start with beginning grammar rule expand non terminals until reach a terminal and check whether it matches keep trying options until either find a complete match or exhaust possibilities Bottom up start with symbol in input string match to rule replace with non terminal eithertind another non terminal match or match next terminal in input keep trying options until eithertind complete match or exhaust possibilities Example Recognizing Prefix Expressions Top Down Grammar ltprefixgt ltidenti ergt l lt0pemt0rgt ltpre xgt ltprefixgt lt0pemt0rgt ltidenti ergta b z Given a b c ltprefixgt lt0pemt0rgt ltprefixgt ltpre xgt ltpre xgt ltprefixgt lt0pemt0rgt ltpre xgt ltpre xgt ltprefixgt ltprefixgt ltpre xgt ltprefixgt ltidenti ergt ltpre xgt ltpre xgt a ltprefixgt ltpre xgt 11 abc c5209 F nil I a a ltidentifiergt ltprefixgt 9 a b ltpre xgt 10 a b ltidenti ergt 682211 Recursive Descent Code 1 3 d public class Parse private String nextIn private StringTokenizer st public ParseString sentence st new StringTokenizersentence class to Find words in strings nextIn stnextToken private baolean expression if ID return true rule ltexpressiongt ltidentifiergt else rule ltexpressiongt ltoperatorgt ltexpressiongt ltexpressiongt if operator if expression if expression urn else return false else return false else return false 20ng in i Algorithms and Complexity Rosen Ch 32 Growth of Functions Rosen Ch 33 Complexity of Algorithms Walls Ch 101 Efficiency of Algorithms Measuring the efficiency of eggli algorithms 15 i We have two algorithms algl and alga that solve the same problem Our application needs a fast running time How do we choose between the Measuring the efficiency of 683 algorithms g39 m Implement the two algorithms in Java and compare their running times Issues with this approach How are the algorithms coded We want to compare the algorithms not the implementations What computer should we use Results may be sensitive to this choice What data should we use algorithms Measuring the efficiency of 65345 algorithms en 5 Goal 7 techniques that analyze algorithms independent of specifics such as implementation hardware or data Solution analyze and model the number of operations the algorithm will perform as a function of input Example copying an array with n elements requires operations 6522 Growth rates g g a Algorithm A requires n22 operations to solve a problem of size n Algorithm B requires 5n10 operations to solve a problem of size n So which do we pick Order of magnitude 6324 growth analySIS 1quot g A function fx is Ogx if and only if there exist two positive constants c and k CSZOQR7 BigO 5 focus is only on growth shape of gx matters not the multiplicative constant c focus is on large x k allows us to ignore shapes for smaller x examples such that fx ls cgx V x gt k cgX 1 00 k n C5209 Classic Shapes constant 53 a 01 c522 c522 Classic Shapes Linear 1 3 d Other Shapes Sublinear in a 0x I fX ax b 4 Algorithm examples 2 lquot CSZOQE C8209 F aquot F ClaSSIc Shapes logarithm a a Logarithms cont an g Definition 39 IogXY 3909 X log y b0 a 10gb ac logxa a log x 23 8 log28 3 2416 l092164 logarithm is a strictly increasmg very We almost always work with base 2 Slow grOWing function examples of logarithmic complexity codes we have already discussed cszoglngi 5 Other Shapes Superlmear u a a 1 395 s 7 Polynomial x2 exponential cX CSZOO iI 1 Ti Growth rates 11quot i Algorithm A requires n22 operations to solve a problem of size n Algorithm B requires 5n10 operations to solve a problem of size n For large enough problem size algorithm B is more efficient We focus on the growth rate Algorithm A requires time proportional to n2 Algorithm B requires time proportional to n CSZOQE7 9 Simplifying BigO g39 m Theorem Let fx anx an1x 1 alx do where anan1a1a0 are real numbers Then fx is 0x Combinations of Functions 53 5 c5209 Additive Theorem Suppose thatflx is 0g1x andf2x is 0g2x Then f1 f2x is 0maX g1x g2x l Multiplicative Theorem Suppose thatflx is 0g1x andf2x is 0g2x Then f1f2x is 0g1xg2x 682211 Other Notations i 3 1 BigOmega 9 lower bound BigTheta 8 tight upper bound Best Worst or Average cigar J Time Complexity 1 g 1 Best case shortest time possible to execute an algorithm time measured in steps 01 time operations Average case amount of time expected usually In this course we will hand wave a lot Worst case just how bad can it get What is the maximal steps this will take Example linear search cszogjm Practical Analysis Loops 5 1 public void insc ElcmcntAtObjcct obj int index 2 for i clementCount i gt index i 3 clementData clementData l How many times will line 3 repeat On what does the number depend CS 209 i F Practical AnalySIs RecurSIon a t fn depends on number of calls work done in each call Examples factorial how many recursive calls binary search Practical Analysis c522 Practical Analysis maul t 1 i Comblnatlons 5quot Dependent loops 11quot 1 Sequential 7 fn additive i O innerloop iters 0 steepest growth dominates eg copying of array followed by binary search fn n logn O tori0iltni i1 innerloop iters 1 f0rJ390jltii i n1 innerloop iters n1 Embedded code fn multiplicative I Total 0 1 2 n1 eg nested forloops each with n iterations fn nnW2 Innermost loop body 01 2 fn nn O On CSZOQE7 C5209 5391quot F F Examples u m Example SelectionSort j a g Copying an array I Basic idea 0n where n is size ofthe array Take multiple passes over the array Linear search in a list for a particular value Keep already sorted array at highend Best case 01 Worst case 0n where n is the list size Find the biggest element in unsorted part Enumerate all lowercase char strings of length n Swap it into the highest position in unsorted part fn 26 0c Invariant each pass guarantees that I Insert Element in Vector Class one more element is in the correct position and all elements in lower part of array are smaller Best case 01 Worst case 0n where n Is the number of elements currently in the vector C5200 I ii Selection Sort Code public static void selectionSortComparable theArray int n Sorts the items in an array into ascending order Precondition theArray is an array of n items Postcondition theArray is sorted into ascending order last index of the last item in the subarray of items yet to be sorted largest index of the largest item found for int last nl last gt 1 last Invariant theArrayllastlnl is sorted and gt theArray0last select largest item in theArray0last int largest indexOfLargesttheArray lastl swap largest item theArraylargest with theArraylast Comparable temp theArraylargest theArraylargest theArraylast theArrayllast temp Iiiinn CSZOO 1 i indexOfLargest private static int indexOfLargestComparable theArray int size Finds the largest item in an array Precondition theArray is an array of size items size gt 1 Postcondition Returns the index of the largest item in the array int indexSoFar 0 index of largest item found so far Invariant theArrayindexSoFargttheArray0currlndexl for int currlndex l currlndex lt size H currlndex if L l nmnare39l d quot quot gtO indexSoFar currlndex end if end for return indexSoFar selectionSort csgoijm Algorithm Complexity mi la How many compares are done How many swaps are done How much space Algorithm Complexity selectionSort 68209 i Igni How many compares are done n1n21 or On2 How many swaps are done Note swap is run even if already in position n or On How much space lnplace algorithm Iiibd csigz i Examples 5 a a Copying an array Linear search in a list for a particular value Enumerate all lowercase char strings of length n Insert Element in Vector class CSZOQJEI li El Overall Comments 1 39 Orderof magnitude analysis focuses on large problems lfthe problem size is always small you can probably ignore an algorithm s efficiency Weigh the tradeoffs between an algorithm s time requirements its memory requirements expense of programmingmaintenance Compare algorithms for both style and efficiency 65200 F ai C8200 structure Check the c5200 webpage c5209 Quizzes amp Class Participation F39 R are ou with us in ii C8200 Fall 2008 Tests what have you learned Instructor Adele Howe 39 Lib ass39gnments can you Implement It GTA John Stevens Homework assignments UTA Erin N agoshi do you understand the underlying theory 08200 Class Overview 08200 Class Overview cszogq CSZOZF39 Class meetings min 5 Difference from C8160161 53 1 Lectures In CS16X you are told Concepts What to do Programming assignments discussion I HOW to do it Classes methods etc Quizzes I I i Tests In C8200 this is less so Labs What to do Lab meetings help you with programming and Sometimes Class names homework assignments practice material from lecturebook meet with teammate later I Larger pregrams commumg agglgnments Actual Lab work done by yourself or your team during 39 Team programmmg labs and in your own time 08200 0lass Overview 08200 0lass Overview Sigg R Course Goals die 1 To understand programs at different levels Logical view Programs Algorithms Data Structures Understand their relationship and use them correctly efficiently Implementations Programs Methods Objects Practice design and implementation of objectoriented programs in Java Read others code and work together to build larger programs Connect underlying theory to programming concepts 08200 Class Overview 5 csaoorlil li Policies 5 1 g Trust men and they will be true to you treat them greatly and they will show themselves great Ralph Waldo Emerson Be professional c5209 Programming Assignments 55 Building a realistic simulator of Internet traf c Multipart assignment Read and parse packets Rout them through little tiny network Part individual part EW EEEEEZTEN T EARE team assignment BROKEN DOWN lNTO SMALL PACKETS AND WRAPPED WITH SPHPPlNGmSTRUCTIONS from www1b1govscienceArcadesArchiveinrmmadon superhighmyhtml 08200 Class Overview 7 08200 0lass Overview 6 CSEI7 Clearing Cobwebs ig 1 T or F You can cast an int to double Legal int a 5 int b 4 Spot the bugs double scores 502 1210 5505 1427 double mine for int in 1 in 4 in mine mine scoresin What does this do public static double abodouble anArPayll int x if x 1 return anArrayO else return anArrayx 1 aboanArray x 1 08200 0lass Overview 8 cszoo p liI E Starting Point in i Walls amp Mirrors Ch 15 Java programming Principles of programming Recursion ADTs Linked Lists Rosen Ch 11131517212334364142 45 5153 Logic Functions Integers Recursion Counting 08200 Class Overview 9 C8200 Priority Queues csaogm amp ADT Table Ii I IEI Is I Manage data by value I Operations Create empty Is empty Size Insert new item Delete item with search key Retrieve item by search key Traverse items in sorted order N955 quot N 65ng IaI 5 ii and Iieaps IWalls Ch 12 Table Priority Queues heaps heap sort 2227 Pseudocode for Table ADT il I It I createTableO creates an empty table I tableIsEmptyboolean query Determines whether a table is empty I tableLengthinteger query Determines the number of items in a table I tableTraverseTab1eItemType Traverses a table in sorted search key order Pseudocode for Table ADT csiwm cont IiiE If I tableInsertin newIteszableItemType throws TableException Inserts newItem into a table whose items have distinct search keys that differ from newltem s search key throws exception if unsuccessful I tableDeletein searchKeyzKeyType boolean Deletes from a table the item whose search key equals searchKey Returns true if successful false if no item found I tableRetrievein searchKeyKeyTypeTab1eItemType Returns item whose search key equals searchKey Returns null if not there CSZOgIEIR I It Table Items iii 5 public abstract class KeyedItemltKT extends Comparable lt super KTgtgt private KT searchKey public KeyedItemKT key searchKey key public KT getKeyO return searchKey cszogm 339 Table or Dictionary Example in 5 32406 Bad Day Daniel Powter 32406 Beep The Pussycat Dolls 32406 Move Along The AllAmerican Rejects 32406 Temperature Sean Paul 32406 Unwritten Natasha Bedingfeld 65200 E H 7 Table Items Example ena Public class TopTunes extends KeyedltemltStringgt private String title search key private int rank private String artist private String date public TopTunesString theTitle int theRank supertheTitle rank theRank c5202 l in Table Interface ge 5 public interface TablelnterfaceltT extends KeyedItemltKTgt KT extends Comparable lt super KTgtgt Precondition for all operations No two items of the table have the same search key The table39s items are sorted by search key public boolean tableIsEmptyO Determines whether a table is empty Postcondition Returns true if the table is empty false otherwise public int tableLengthO Determines the length of a table Postcondition Returns the number of items in the table Table Interface cont CSZOgIEIKR HE public void tableInsertT newItem throws TableException Inserts an item into a table in its proper sorted order according to the item39s search key Precondition The item is newItem whose search key would be unique in the table Postcondltion If successful newItem is in its proper order in table Otherwise table is unchanged throw TableException public boolean tableDeleteKT searchKey Deletes an item with search key KT from table Precondition searchKey is the search key of item to be deleted Postcondltion If there is an item with KT in the table the item was deleted and method returns true Otherwise table is unchanged return false Table Interface cont 69ng 339 5 ii public KeyedItem tableBetrieveKT searchKey Retrieves an item with a search key KT from table Precondition searchKey is search key for item to be retrieved Postcondition If the retrieval was successful table item with search key matching KT is returned If no such item exists return null end Tablelnterface Possible Implementations of Table Array sorted by Search Key Pros fast access via binary search CSZOtJ x I It IiiEuni Cons requires knowing size add and delete are not directly supported ArrayList sorted by Search Key Pros fast access via binary search Cons may waste space add and delete are expensive Linked List sorted by Search Key Cons expensive retrieval add and delete Binary Search Tree Pros fast average access efficient use of space I COl39lSI poor worst case access Priority Queues c5202 l in int 5 Characteristics order data by a special search key priority provide access to one element at a time typically highest priority minimum value Use simulations operating systems CSZOgliR CSZOgIi Priority Queue ADT Operations iii 7 Priority Queue Implementationtn 1 Create an empty priority queue ArrayList ordered by priority createPQueueO Sorted ArrayList 2 Determine Whether empty location of maximum element position 0 qusEmptyboolean query add find the insertion location 3 Insert new item Unsorted ArrayList qunsertOn newItemzPQItemType throws PQueueExoeption 39 add at end of VeCtor 4 Retrieve and delete the item with the highest 39 The max39mume39emem mealsmm priority I Lll39lked ilSt queletePQItemType Binary search tree CSZOO CSZOO i H in H 9 Heaps t e e Heap Examples Validity a e t Characteristics complete binary tree root holds the maximum value each subtree is also a heap values in descending order on every path from root to leaf root of tree holds maximum value global each node is greater than its two children local Valid valid N01 Valid this is called the heap property COMPLETE INCOMPLETE t395 Heap ADT e a 5 createHeapO create empty heap heapIsEmptyboolean query determines if empty I heapInsertin newItem2HeapItemType throws HeapException inserts newItem based on its search key Throws exception if heap is full heapDeleteHeapItemType retrieves and then deletes heap s root item which has largest search key Implementation ilkh ArrayListbased Heap iii a Addressing root at position 0 left child of position i at position 2i1 right child of position i at position 2i1 parent of position i at position Li12j ArrayListbased Binary Tree 653 Priority Queue Example 5 E 5 012 3 4 5 6 7 8 91011121314 Why is there so much wasted space ArrayListbased Heap 6539 Example a e What is the property of a complete heap in an ArrayList cszoglnk 1 Heap Operations heapInsert 5 put a new value into first open position maintaining completeness percolate values up Reenforcing the heap property swap with parent until in the right place Add 36 to the heap Heap Operations heapInsert a 320 put a new value into first open position maintaining completeness percolate values up Reenforcing the heap property swap with parent until in the right place cszoo in l Heap Operations heapInsert 5 ii 5 u put a new value into first open position maintaining completeness percolate values up Reenforcing the heap property swap with parent until in the right place Add 36 to the heap c5201 lil E Lecture 20 10302007 6 i Walls 12 Priority Queues and Heaps Heaps Heap sort CSZOgIEIR I It Heap Operations heapInsert j E 5 u put a new value into first open position maintaining completeness percolate values up Reenforcing the heap property swap with parent until in the right place Elm l 4 5 0123 6 Add 36 to the heap csaogm amp Heap Insert Pseudocode in a insert newltem into bottom of tree itemsaddnewItemitemssize trickle new item up to appropriate spot place itemssize 1 parent place12 while parent gt 0 and itemsgetplace gt itemsgetparent swap data at position place and position parent place parent parent place12 cszooflgx n Heap operations heapDelete 5 E 5 always remove value at root Why substitute with rightmost leaf of bottom level Why percolate down swap with maximum child as necessary Delete from heap c5202 l in Heap operations heapDelete 5 a 5 always remove value at root Why substitute with rightmost leaf of bottom level Why percolate down swap with maximum child as necessary 7 Save 36 lj 023456 1 Delete from heap CSZOgliR 1 I Heap operations heapDelete ia always remove value at root Why substitute with rightmost leaf of bottom level Why percolate down swap with maximum child as necessary Return 36 Delete from heap CSZOQER ii I heapRebuild Pseudocode 5 it 5 heapRebuilditemsArrayList rootinteger sizeinteger if root is not a leaf child 2 root 1 left child if root has right child rightGhild child 1 if itemsgetrightGhildgetKey gt itemsgetchildgetKey child rightGhild larger child if itemsgetrootgetKey lt itemsgetchildgetKey swap data at position root with position child heapRebuilditems child size CSZOO Ftp heapDelete Pseudocode I It return the item in root rootItem itemsget0 copy item from last node into root Itemsset0root1tem itemsgetsize1 size heapBebuilditems 0 size return rootItem ArrayListbased Heaps 6523 Order of Complexity 5 it 5 Best Case Worst Case insert 00 om because of ensurecapacity delete 00 oog n because tree is complete Heap versus BST for 653 PriorityQueue as ii What if you know maximum needed size for the PriorityQueue How does worst case complexity compare How does average case complexity compare c5200 gig 7 HeapSort in g Alternatively Start with an non heap array Create a heap by iteratively expanding the portion of the tree that is a semiheap Start from leaves which are semiheaps Move up to next level calling heapRebuild with each parent Swap the root with the largest item in unsorted portion and rebuild 65200 E F ii HeapSort nilh j Algorithm Insert all elements one at a time to a heap Iterativer delete them removing minimum value at each step place removed item in next available location in a separate vector or in place at end of current vector Computational complexity cszoglil l l HeapSort Pseudocode ii is i heapSortourItemsArrayList nzinteger for index n2 goes to O heapBebuildourItems index n Assertion ourItems position 0 has largest item last n 1 for step 1 through 11 Swap ourItems at O with ourItems at last Decrement last heapBebuildourItems 0 last