Lecture 22. String matching and polynomial multiplication

In this class, we explain the following relationship between approximate string matching and polynomial multiplication.

If you can multiply two polynomials of length N in time O(N log N). Then you can solve the problem of string matching problem in time O(n log m) where n is the length of the string and m is the length of the pattern.

Lecture 21. KMP algorithm and approximate string match

In this class, we finished KMP's algorithm for string matching. We also showed the connection between approximate string matching and calculating convolution between two sequences.

Lecture 18. Union Find (2)

Today, we finish the lecture on Union Find. In the end of the class, we had a pretty complicate proof for the log*n running time. If you are confused, have a look at the following page
http://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_Union_Find

The proof is not exactly accurate, but you can start read from the proof below the picture of many buckets.

Lecture 17 Union Find (1)

Today, we talked about union find, data structure that supports find and union operation. We gave an implementation that has cost O(log n) for both operations. We also explain the idea of how to modify the find  function to improve the running time to log* n.

If you are interested in the reference of total number of atoms in the universe, here is a wiki page:
http://en.wikipedia.org/wiki/Observable_universe

Lecture 16 Fibonacci heap (3)

Today, we finished the Fibonacci heap and proved that it has O(1) amortized cost for insertion, merge, find_min, decrease_key. The only expensive work is delete_min which takes O(log n).

As an application, we show how to use Fibonacci heap in Prim's algorithm for Minimum Spanning Tree.

Lecture 15. Fibonacci Heap (2)

Today we talked about how to implement a decrease_key. This implementation will give us tree that is no longer binomial tree. But it will still have the property that suppose the children of a node is sorted according to its degree, then the i-th  has degree at least i-2. (An alternative definition of binomial tree is that its ith child has degree exact i-1).  We call any tree of above property Fibonacci Tree.

Lecture 14 Binomial Heap and Fibonacci Heap

Today, we talked about Binomial Heap and why it takes an amortized running time of O(log n) for the deletion and O(1) for all the other operations. We also (try to) motivate Fibonacci Heap which also support decrease_key in O(1) time.

If you are confused by the Dijkstra's algorithm I described in the end,  take a look at the wiki description.

lecture 13 Binomial Heaps (2)

Today, we talked about how to implement the merge operation of Binomial heap in O(log n) time. This will give us insertion, delete_min, merge all in O(log n).

Surprisingly, if we are a little bit lazier in the implementation, we can make all the operations O(1) except for the delete_min operation.

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.

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.

Lecture 6. Analysis of Treaps

Today, we talked about the insertion and deletion of Treap. We also showed that the expected height of a of any node in the Treap is 2 log n.

If you want to see the proof that height of a treap is O(log n) with high probability, here is a very nice note by Avrim. It shows that the heights of all nodes are less than 8 log n with probability 1/n^{0.44}.

Lecture 5 introduction to Treap

Today, we talked about Treap. Basically, it is an implementation of the BST with the property that the insertion, deletion, and look-up can all be done in O(log n) in expectation (the construction is randomized). There are also other implementations of BST with these properties such as AVL tree, B-tree, red-black tree, which you may know before.

We showed that for given a set of keys with assigned priority, the corresponding Treap exists and is unique.

We also showed how to insert a new (key, priority) pair into a Treap.

Lecture 4. Linear Time Selection (2)

Today, we studied two algorithms. One is a randomized algorithm for selecting the k-th largest number. The other is a deterministic algorithm for selecting the median.

We proved that the first algorithm runs in linear time in expectation and the second algorithm runs in linear time.

Below are some nice notes from Avrim Blum for the materials covered in the course today.

Clarification of Lecture 3

Some of the students asked me again why the probability  that a_i is compared with a_j is 2/(j-i+1) for any i<j.

Following is the key fact: the probability a_i is compared with a_j is equal to the probability that either a_i or a_j  are the first to be chosen as the pivot among a_i, a_(i+1),..., a_(j-1), a_j.

Analyzing the probability can be also thought of a dart game: each time we throw a dart uniform randomly. If we hit i or j, we will win. If we hit any number k such that  i<k<j, we will lose. If we hit a number outside the range of [i,j], then we will keep playing the game. Then the winning probability is exactly 2/(j-i+1).

Lecture 3. Analyzing Quicksort and Linear Time Selection Algorithm

We analyzed the running time of quicksort. Also, we also gave a randomized algorithm for selecting the k-th largest number.

Lecture 2: Divide and Conquer and analyzing recurrence

Today, we talked about Karasuba's algorithm for multiplication and Strassen's algorithm for matrix multiplication. Question regarding Lecture 2 can be asked here.