CPSC 320 Lecture 1: CPSC_320__Amortized_Analysis_VI
Document Summary
Beginning of class announcements: solutions have been posted for both versions of the second midterm. Grad- ing has started on the midterms: assignment 7 has been posted and is due on wednesday. Assignments 5 and 6 is in a strange state but some marks will hopefully be returned in the upcoming week. The goal to today"s class is to nish the analysis of fibonacci heaps. Recall the following facts about the deletemin operation. The potential di erence (fi) (fi 1) was calculated to be (c 1 k)u. Thus, we can determine the amortized cost of a deletemin operation using these facts. costam(deletemin) d(n) + t(fi 1) + 2c + k + 1 + (c 1 k)u (1) As established last day, t(fi 1) k c + d(n) + 2 because we have an upper bound on the amount of merges needed to be done by a deletemin operation.
