Lecture 12. Binomial Trees and clarifications

Today we talked about the construction of Binomial Heaps. The main motivation is to allow efficient merging operation. As we know the binary heap merging takes time \Omega(n).

In the end of the class, there is a mistake when I described the delete-min operations. For a binomial heap H,we will first take the tree with the smallest root B_min and delete of its root to get H'= (B_1,...B_{min-1}). In the class, I mention that then we will merge H' with H. This is wrong. As is pointed out by some student, we want to merge H' with H'' where H'' =(H\B_min) (the notion means that H'' is the heap we get after remove B_min from H).

Lecture 11 Splay Tree

Today we proved that for deletion and search as well as the splay operation, the amortized cost is O(log n) for splay trees. As a homework, you will show the insertion will also have an amortized cost O(log n).

Lecture 10 Splay Tree

Today, we talked about the implementation of Splay Trees. We also introduced the potential function for the analysis of Splay Trees.

Lecture 9 Amortized Analysis and Splay Tree

Today we summarize 3 different techniques of analyzing amortized cost. Also, we introduce the basic idea of Splay Tree. It is similar to the standard binary tree while the difference is that after it access some element by the standard BST operations, it will bring that element to the root of the tree.

Good news(?)

Starting next Wednesday 9/12, the class will meet at LWSN B151.

Lecture 8. Amortized Analysis (2)

Today, we introduce 3 ways of analyzing the amortized cost of an algorithm. We use  the problem of simulating a queue by two stacks as an example.

These 3 mehtods are aggregate analysis, banker's method and physicist's method.  Aggregate analysis basically analyzes the average cost of  n different operations. Banker's method is a generalization (of aggregate analysis) which allows us to assign different cost to different operations as long as the cost we pay can always cover the time we spend on the operations. The physicist's method introduce a potential function (which can be viewed as all the credits available in the banker's method). After defining the potential function, it naturally induces a amortized cost for each operation.

Lecture 7. Amortized Analysis (1)

Today, we talked  about amortized analysis. One example we use is the dynamic array.

We showed that although the worst case insertion can be Omega(n), the amortized cost is actually constant.