Analysis of Algorithms University of Southern California CSCI 570 V Adamchik Lecture 2 Fall 2023 Review Amortized Cost Reading chapters 1 2 Ch1 review questions Ch1 exercises Discussion Problem 1 Consider these two statements about a connected undirected graph with vertices and edges I II 2 Mark all the correct choices below a I and II are both false b Only I is true c Only II is true d I and II are both true Planar Graphs A graph is planar if it can be drawn in the plane without crossing edges K4 is planar K5 is not planar Euler s Formula Theorem If G is a connected planar graph with V vertices E edges and F faces then V E F 2 4 faces A planar graph when drawn in the plane splits the plane into disjoint faces Coloring Planar Graphs A coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same color 4 Color Theorem 1976 Theorem Any simple planar graph can be colored with less than or equal to 4 colors It was proven in 1976 by K Appel and W Haken They used a special purpose computer program Since that time computer scientists have been working on developing a formal program proof of correctness The idea is to write code that describes not only what the machine should do but also why it should be doing it If a graph is NOT planar the coloring problem is hard NP hard Amortized Analysis In a sequence of operations the worst case does not occur often in each operation some operations may be cheap some may be expensive Therefore a traditional worst case per operation analysis can give overly pessimistic bound When same operation takes different times how can we accurately calculate the runtime complexity Unbounded Array Consider insertions into an array of size n some operations take O n others O 1 If the current array is full the cost of insertion is linear if it is not full insertion takes a constant time Amortized analysis is an alternative to the traditional worst case analysis Namely we perform a worst case analysis on a sequence of operations We will create a new data structure unbounded array when we need to insert into a full array we allocate a new array twice as large and copy the elements we already have to the new array The Aggregate Method The aggregate method computes the upper bound T n on the total cost of n operations The amortized cost of an operation is given by In this method each operation will get the same amortized cost even if there are several types of operations in the sequence Unbounded Array Unbounded Array Unbounded Array summary The amortized cost of an operation is given by upper bound on the total cost of n operations where is the We considered unbounded array with a doubling up resizing policy Insertions 1 2 3 4 5 6 7 8 9 2n 1 Insertion Cost 1 1 1 1 1 1 1 1 1 1 Copy Cost 0 1 2 0 4 0 0 0 8 2n We computed the average cost per insert O 1 It is important to realize that we achieve a great amortized cost just because we have implemented a clever resizing policy Binary Counter Given a binary number n with log n bits stored as an array where each entry A i stores the i th bit The cost of incrementing a binary number binary addition is the number of bits flipped Binary Counter Discussion Problem 2 Another Binary Counter Let us assume that the cost of a flip is 2k to flip k th bit Flipping the lowest order bit costs 20 1 the next bit costs 21 2 and so on What is the amortized cost per increment Use the aggregate method Discussion Problem 3 Another Yet Binary Counter Let us assume that the cost of a flip is k 1 to flip k th bit Flipping the lowest order bit costs 0 1 1 the next bit costs 1 1 2 the next bit costs 2 1 3 and so on What is the amortized cost per operation for a sequence of n increments starting from zero What is the amortized cost per increment Use the aggregate method The Accounting Method The accounting method or the banker s method computes the individual cost of each operation We assign different charges to each operation some operations may charge more or less than they actually cost The amount we charge an operation is called its amortized cost Discussion Problem 4 You have a stack data type and you need to implement a FIFO queue The stack has the usual POP and PUSH operations and the cost of each operation is 1 The FIFO has two operations ENQUEUE and DEQUEUE We can implement a FIFO queue using two stacks What is the amortized cost of ENQUEUE and DEQUEUE operations
View Full Document
Unlocking...