This is the tenth post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lecture fifteen, which introduces the concept of Dynamic Programming and applies it to the Longest Common Subsequence problem.

Dynamic programming is a design technique similar to divide and conquer. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. Dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subsubproblem is encountered.

Dynamic programming was systematized by Richard E. Bellman. He began the systematic study of dynamic programming in 1955. The word “programming,” both here and in linear programming, refers to the use of a tabular solution method and not to writing computer code.

Dynamic programming is typically applied to optimization problems. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

Dynamic programming can be effectively applied to solve the longest common subsequence (LCS) problem. The problem is stated as following: given two sequences (or strings) x and y find a maximum-length common subsequence (substring) of x and y.

For example, given two sequences x = “ABCBDAB” and y = “BDCABA”, the LCS(x, y) = { “BCBA”, “BDAB”, “BCAB” }. As you can see there are several optimal solutions.

Lecture fifteen introduces dynamic programming via this longest common subsequence problem. It first gives a brute-force, exponential time algorithm for solving it. The idea of algorithm is to check every subequence of x[1..m] (m is the length of sequence x) to see if it is also a subsequence of y[1..n] (n is the length of sequence y). Checking takes O(n) time, and there are 2^m subsequences of x. The running time thus is exponential O(n·2^m). It is no good for large sequences and the lecture continues with a simplification - let’s look at the length of a longest-common subseq and then extend this algorithm to find the LCS itself. The simplified algorithm is recursive in nature and computes the same subproblems. At this moment two dynamic programming hallmarks are stated:

• 1. Optimal substructure: an optimal solution to a problem contains optimal solutions to subproblems.
• 2. Overlapping subproblems: a recursive solution contains a “small” number of distinct subproblems repeated many times.

As the subproblems are overlapping, the lecture introduces concept of memoization algorithm (note that it’s not memorization). A better known word for memoization is caching. The subproblems are cached (memoized) so that they are not recomputed over and over again.

The lecture ends with constructing a dynamic programming table for LCS problem and explains how to find a LCS from this table.

You’re welcome to watch lecture fifteen:

Topics covered in lecture fifteen:

• [00:20] Dynamic programming.
• [01:47] Longest common subsequence (LCS) problem.
• [03:55] Example of LCS on sequences “ABCBDAB” and “BDCABA”.
• [06:55] Brute force algorithm for LCS.
• [07:50] Analysis of brute force algorithm.
• [11:40] Simplification of LCS problem.
• [16:20] Theorem about LCS length.
• [18:25] Proof of the theorem.
• [30:40] Dynamic programming hallmark #1: Optimal substructure.
• [32:25] Example of hallmark #1 on LCS.
• [34:15] Recursive algorithm for longest common subseq.
• [36:40] Worst case analysis of the algorithm.
• [38:10] Recursion tree of algorithm.
• [42:40] Dynamic programming hallmark #2: Overlapping subproblems.
• [44:40] Example of hallmark #2 on LCS.
• [45:50] Memoization algorithm for LCS.
• [48:45] Time and space analysis of memoized algorithm.
• [54:30] Dynamic programming algorithm for LCS.
• [01:01:15] Analysis of dynamic programming algorithm.

Lecture fifteen notes:

Lecture 15, page 1 of 2.

Lecture 15, page 2 of 2.

Have fun with programming dynamically! The next post will be about graphs, greedy algorithms and minimum spanning trees.

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”). Chapter 15 is called “Dynamic Programming” and covers the topics in this lecture. It also explains the assembly-line scheduling problem, matrix-chain multiplication problem, elements of dynamic programming and optimal binary search trees.

This is the ninth post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lectures thirteen and fourteen. They are on theoretical topics of Amortized Analysis, Competitive Analysis and Self-Organizing Lists.

Amortized analysis is a tool for analyzing algorithms that perform a sequence of similar operations. It can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a single operation within the sequence might be expensive. Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the average performance of each operation in the worst case.

Lecture thirteen looks at three most common techniques used in amortized analysis - Aggregate Analysis, Accounting Method (also known as Taxation Method) and Potential Method.

Competitive analysis is a method that is used to show how an Online Algorithm compares to an Offline Algorithm. An algorithm is said to be online if it does not know the data it will be executing on beforehand. An offline algorithm may see all of the data in advance.

A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time.

Lecture fourteen gives a precise definition of what it means for an algorithm to be competitive and shows a heuristic for a self-organizing list that makes it 4-competitive.

Lecture 13: Amortized Algorithms

Lecture thirteen starts with a question - “How large should a hash table be?” Well, we could make it as large as possible to minimize the search time, but then it might take too much space. We could then try to make it as small as possible, but what if we don’t know the number of elements that will be hashed into it? The solution is to use a dynamic hash table that grows whenever it is about to overflow.

This creates a problem that at the moment of overflow the table must be grown and growing it might take a lot of time. Thus, we need a way to analyze the running time in a long run.

Lecture continues with three methods for this analysis, called amortized arguments - aggregate method, accounting method, and potential method.

In aggregate analysis, we determine an upper bound T(n) on the total cost of a sequence of n operations. The average cost per operation is then T(n)/n. We take the average cost as the amortized cost of each operation, so that all operations have the same amortized cost.

In accounting method we determine an amortized cost of each operation. When there is more than one type of operation, each type of operation may have a different amortized cost. The accounting method overcharges some operations early in the sequence, storing the overcharge as “prepaid credit” on specific objects in the data structure. The credit is used later in the sequence to pay for operations that are charged less than they actually cost.

Potential method is like the accounting method in that we determine the amortized cost of each operation and may overcharge operations early on to compensate for undercharges later. The potential method maintains the credit as the “potential energy” of the data structure as a whole instead of associating the credit with individual objects within the data structure.

Each method is applied to dynamic tables to show that average cost per insert is O(1).

You’re welcome to watch lecture thirteen:

Topics covered in lecture thirteen:

• [01:05] How large should a hash table be?
• [04:45] Dynamic tables.
• [06:15] Algorithm of dynamic hash tables.
• [07:10] Example of inserting elements in a dynamic array.
• [09:35] Wrong analysis of time needed for n insert operations.
• [12:15] Correct analysis of n insert operations using aggregate analysis method.
• [19:10] Definition of amortized analysis.
• [21:20] Types of amortized arguments.
• [23:55] Accounting method (taxation method) amortized analysis.
• [29:00] Dynamic table analysis with accounting (taxation) method.
• [40:45] Potential method amortized analysis.
• [54:15] Table doubling analysis with potential method.
• [01:13:10] Conclusions about amortized costs, methods and bounds.

Lecture thirteen notes:

Lecture 13, page 1 of 2.

Lecture 13, page 2 of 2.

Lecture 14: Competitive Analysis and Self-Organizing Lists

Lecture fourteen starts with the notion of self-organizing lists. A self-organizing list is a list that reorders itself to improve the average access time. The goal is to find a reordering that minimizes the total access time.

At this point the lecture steps away from this problem for a moment and defines online algorithms and offline algorithms: Given a sequence S of operations that algorithm must execute, an online algorithm must execute each operation immediately but an offline algorithm may see all of S in advance.

Now the lecture returns to the self-organizing list problem and looks at two heuristics how the list might reorganize itself to minimize the access time. The first way is to keep a count of the number of times each element in the list is accessed and reorder list in the order of decreasing count. The other is move-to-front heuristic (MTF) - after accessing the element, move it to the front of the list.

Next the lecture defines what it means for an algorithm to be competitive. It is said that an online algorithm is α-competitive if there is a constant k such that for any sequence of operations the (running time cost of online algorithm) <= α·(running time cost of an optimal offline algorithm (also called "God's algorithm")) + k.

Lecture continues with a theorem that move-to-front is 4-competitive for self-organizing lists. The proof of this theorem takes almost an hour!

Topics covered in lecture fourteen:

• [01:00] Definition of self-organizing lists.
• [03:00] Example of a self-organizing list (illustrates transpose cost and access cost).
• [05:00] Definition of on-line and off-line algorithms.
• [08:45] Worst case analysis of self-organizing lists.
• [11:40] Average case analysis of selforganizing lists.
• [17:05] Move-to-front heuristic.
• [20:35] Definition of competitive analysis.
• [23:35] Theorem: MTF is 4-competitive.
• [25:50] Proof of this theorem.

Lecture fourteen notes:

Lecture 14, page 1 of 2.

Lecture 14, page 2 of 2.

Have fun with amortized and competitive analysis! The next post will be about dynamic programming!

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”):

This is the eighth post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lecture twelve, which introduces an efficient search structure called Skip Lists.

Skip lists are an efficient data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforce balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler to implement and significantly faster than the equivalent algorithms for balanced search trees (see lectures 9 and 10 for search trees).

Here is the first publication ever on skip lists by their inventor William Pugh - Skip Lists: A Probabalistic Alternative to Balanced Trees

The lecture begins with Erik Demaine (professor) telling the students that before the lecture he implemented skip lists to see how fast it could be done. It took him 10 minutes to implement linked lists (on which skip lists are based) and took another 30 to implement skip lists themselves (+30 mins debugging ;) ). He says that they are so simple that at no point did he have to think while implementing them. Compare it to red-black trees for example, where you have to think really hard to implement the operations to maintain red-black tree properties (see lecture 10 on red-black trees).

The lecture continues with derivation of skip lists from scratch. First, a single sorted linked list is considered. Searching in a sorted linked list takes O(n). Then another sorted linked list is added. The added linked list is chosen to be a sublist of the first linked list. The elements that both lists share are linked together with another link (see my scanned lecture notes below to see how it looks). The search cost for such structure is O(2·sqrt(n)). Then another and another linked list is added, the search cost goes down to O(3·n^1/3), O(4·n^1/4), …, O(k·n^1/k). Now, what should k be? Take it to be log(n), we get running time of O(lg(n)·n^1/lg(n)), which is O(2·lg(n)) - logarithmic time search structure!

The lecture also presents Search(x) method for finding the element x in a skip list, and Insert(x) method for inserting the element x in a skip list.

The rest of the lecture is allocated to the proof that the search operation in skiplists takes O(lg(n)) time with high probability.

You’re welcome to watch lecture twelve:

Topics covered in lecture twelve:

• [00:10] A new dynamic, balanced, randomized and simple search structure - skip lists.
• [01:20] Review of other simple search structures - treaps, red-black trees, b-trees.
• [03:55] Skip lists are a data structure that you will never forget, so simple it is.
• [06:10] All the skip list operations take O(lg(n)) time almost guaranteed (with high probability).
• [07:30] Implementing skip lists from scratch.
• [09:05] Search cost in a single sorted linked list.
• [10:30] Adding a second linked list, search cost analysis.
• [11:16] Trick question: what is this sequence 14, 23, 34, 42, 50, 59, 66, 72, 79, 86, 96, 103, 110, 116, 125? (I won’t reveal the answer ;) , you’ll have to watch the lecture).
• [14:35] Building skip list out of this sequence.
• [17:07] Search(x) operation algorithm for a skip list.
• [18:40] Example of search operation.
• [21:20] What elements do go in the second linked list?
• [25:30] Search cost of a skip list with two sorted linked lists.
• [27:53] Skip list with three sorted link lists.
• [29:14] Skip list with k sorted linked lists.
• [29:25] What should k be? (It should ideally be lg(n)).
• [32:10] Example of an ideal skip list.
• [38:30] Skip lists roughly maintain their structure subject to updates (insert, delete).
• [39:40] Insert(x) operation algorithm for a skip list.
• [47:00] Building a random skip list.
• [54:00] Rigorous analysis of search cost of skip lists.
• [55:00] Theorem: with high probability, search in n element skiplist costs O(lg(n)).
• [57:10] Definition: with high probability.
• [01:00:00] Boole’s inequality.
• [01:06:55] Joke: probability that Search(x) algorithm takes more than O(lg(n)) time is smaller than a meteor striking the earth at the same time that your computer has floating point error at the same time earth explodes :D .
• [01:07:45] Lemma: With high probability number of levels in a skiplist is O(lg(n)).
• [01:13:00] Cool idea - analyze search time backwards.

Lecture twelve notes:

Lecture 12, page 1 of 2.

Lecture 12, page 2 of 2.

Have fun building skip lists! The next post will be about two really theoretical lectures on amortized analysis, competitive analysis and self-organizing lists.

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”):

PPS. This was one of the lectures that did not have a corresponding chapter in the book.

This is the seventh post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lecture eleven, which is on the topic of Augmenting Data Structures.

There are some programming situations that can be perfectly solved with standard data structures such as a linked lists, hash tables, or binary search trees. Many others require a dash of creativity. Only in rare situations will you need to create an entirely new type of data structure, though. More often, it will suffice to augment (to modify) an existing data structure by storing additional information in it. You can then program new operations for the data structure to support the desired application. Augmenting a data structure is not always straightforward, however, since the added information must be updated and maintained by the ordinary operations on the data structure.

This lecture discusses two data structures that are constructed by augmenting red-black trees (see the previous post on red-black trees).

The first part of the lecture describes a data structure that supports general order-statistic operations on a dynamic set. It’s called dynamic order statistics. The notion of order statistics was introduced in lecture six. In lecture six it was shown that any order statistic could be retrieved in O(n) time from an unordered set. In this lecture it is shown how red-black trees can be modified so that any order statistic can be determined in O(lg(n)) time. It presents two algorithms OS-Select(i), which returns i-th smallest item in a dynamic set, and OS-Rank(x), which returns rank (position) of element x in sorted order.

The lecture continues with general methodology of how to augment a data structure. Augmenting a data structure can be broken into four steps:

• 1. Choosing an underlying data structure,
• 2. Determining additional information to be maintained in the underlying data structure,
• 3. Verifying that the additional information can be maintained for the basic modifying operations (insert, delete, rotate, etc.) on the underlying data structure, and
• 4. Developing new operations.

The second part of the lecture applies this methodology to construct a data structure called interval trees. This data structure maintains a dynamic set of elements, with each element x containing an interval. Interval is simply pair of numbers (low, high). For example, a time interval from 3 o’clock to 7 o’clock is a pair (3, 7).

Lecture gives an algorithm called Interval-Search(x), which given a query interval x, quickly finds an interval in the set that overlaps it. Time complexity of this algorithm is O(lg(n)).

The lecture ends with the correctness proof of Interval-Search(x) algorithm.

You’re welcome to watch lecture eleven:

Topics covered in lecture eleven:

• [00:20] Concept of augmenting data structures.
• [02:00] Dynamic order statistics.
• [02:20] OS-Select operation on dynamic order statistics.
• [02:50] OS-Rank operation on dynamic order statistics.
• [03:49] Dynamic order statistics key idea - keep the sizes of subtrees in nodes of a red-black tree.
• [04:10] Example of a tree representing dynamic order statistic.
• [10:10] OS-Select algorithm.
• [16:40] Analysis of OS-Select.
• [17:30] OS-Rank algorithm.
• [20:15] Modifying operations of dynamic order statistics tree.
• [22:55] Example of inserting an element into the tree.
• [26:11] Example of rotating a tree.
• [29:30] Methodology of data structure augmentation.
• [36:45] Data structure augmentation applied to construct interval trees.
• [37:31] Example of time-intervals.
• [39:48] Query operation on interval trees - find an interval in the set that overlaps a given query interval.
• [41:15] Step 1, underlying data structure: red-black tree keyed on low endpoint.
• [45:10] Step 2, additional node information: largest value in the subtree rooted at that node.
• [50:24] Step 3, modifying ops: insert, delete.
• [56:55] Step 4, new ops: Interval-Search.
• [01:00:00] Example of Interval-Search algorithm.
• [01:06:30] Running time of Interval-Search — O(lg(n)).
• [01:07:20] List all overlaps (k of them) in O(k*lg(n)) time.
• [01:08:50] Best algorithm to find all overlaps to date os O(k + lg(n)).
• [01:09:11] Correctness proof of Interval-Search algorithm.

Lecture eleven notes:

Lecture 11, page 1 of 2.

Lecture 11, page 2 of 2.

Have fun augmenting data structures! The next post will be about a simple and efficient search structure called skip list!

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”):

This is the sixth post in an article series about MIT’s lecture course “Introduction to Algorithms.” In this post I will review lectures nine and ten, which are on the topic of Search Trees.

Search tree data structures provide many dynamic-set operations such as search, insert, delete, minimum element, maximum element and others. The complexity of these operations is proportional to the height of the tree. The better we can balance the tree, the faster they will be. Lectures nine and ten discuss two such structures.

Lecture nine discusses randomly built binary search trees. A randomly built binary search tree is a binary tree that arises from inserting the keys in random order into an initially empty tree. The key result shown in this lecture is that the height of this tree is O(lg(n)).

Lecture ten discusses red-black trees. A red-black tree is a binary search tree with extra bit of information at each node — it’s color, which can be either red or black. By contrasting the way nodes are colored on any path from the root to a leaf, red-black trees ensure that the tree is balanced, giving us guarantees that the operations on this tree will run on O(lg(n)) time!

PS. Sorry for being silent for the past two weeks. I am preparing for job interviews at a company starting with ‘G‘ and it is taking all my time. ;)

Lecture 9: Randomly Built Binary Search Trees

Lecture nine starts with an example of good and bad binary search tree. Given a binary tree with n nodes, a good trees has height log(n) but the bad one has height close to n. As the basic operations on trees run in time proportional to the height of the tree, it’s recommended that we build the good trees and not the bad ones.

Before discussing randomly built binary search trees, professor Erik Demaine shows another sorting algorithm. It’s called binary search tree sort (BST-sort). It’s amazingly simple — given an array of n items to sort, build a BST out of it and do an in-order tree walk on it. In-order tree walk walks the left branch first, then prints the values, and then walks the right branch. Can you see why the printed list of values is sorted? (If not see the lecture ;) ) [part three of the article series covers sorting algorithms]

Turns out that there is a relation between BST-sort and quicksort algorithm. BST-sort and quicksort make the same comparisons but in different order. [more info on quicksort in part two of article series and in “three beautiful quicksorts” post]

After this discussion, the lecture finally continues with randomized BST-sort which leads to idea of randomly built BSTs.

The other half of the lecture is devoted to a complicated proof of the expected height of a randomly built binary search tree. The result of this proof is that the expected height is order log(n).

You’re welcome to watch lecture nine:

Topics covered in lecture nine:

• [00:50] Good and bad binary search trees (BSTs).
• [02:00] Binary search tree sort tree algorithm.
• [03:45] Example of running BST-sort on array (3, 1, 8, 2, 6, 7, 5).
• [05:45] Running time analysis of BST-sort algorithm.
• [11:45] BST-sort relation to quicksort algorithm.
• [16:05] Randomized BST-sort.
• [19:00] Randomly built binary search trees.
• [24:58] Theorem: expected height of a rand BST tree is O(lg(n)).
• [26:45] Proof outline.
• [32:45] Definition of convex function.
• [46:55] Jensen’s inequality.
• [55:55] Expected random BST height analysis.

Lecture nine notes:

Lecture 9, page 1 of 2.

Lecture 9, page 2 of 2.

Lecture 10: Red-Black Trees

Lecture ten begins with a discussion of balanced search trees. Balanced search tree is search tree data structure maintain a dynamic set of n elements using tree of height log(n).

There are many balanced search tree data structures. For example: AVL trees (invented in 1964), 2-3 trees (invented in 1970), 2-3-4 trees, B-trees, red-black trees, skiplists, treaps.

This lecture focuses exclusively on red-black trees.

Red-black trees are binary search trees with extra color field for each node. They satisfy red-black properties:

• Every node is either red or black.
• The root and leaves are black.
• Every red node has a black parent.
• All simple paths from a node to x to a descendant leaf of x have same number of black nodes = black-height(x).

The lecture gives a proof sketch of the height of an RB-tree and discusses running time of queries (search, min, max, successor, predecessor operations) and then goes into details of update operations (insert, delete). Along the way rotations on a tree are defined, the right-rotate and left-rotate ops.

The other half of the lecture looks at Red-Black-Insert operation that inserts an element in the tree while maintaining the red-black properties.

Here is the video of lecture ten:

Topics covered in lecture ten:

• [00:35] Balanced search trees.
• [02:30] Examples of balanced search tree data structures.
• [05:16] Red-black trees.
• [06:11] Red-black properties.
• [11:26] Example of red-black tree.
• [17:30] Height of red-black tree.
• [18:50] Proof sketch of RBtree height.
• [21:30] Connection of red-black trees to 2-3-4 trees.
• [32:10] Running time of query operations.
• [35:37] How to do RB-tree updates (inserts, deletes)?
• [36:30] Tree rotations.
• [40:55] Idea of red-black tree insert operation.
• [44:30] Example of inserting an element in a tree.
• [54:30] RB-Insert algorithm.
• [01:03:35] The three cases in insert operation.

Lecture ten notes:

Lecture 10, page 1 of 2.

Lecture 10, page 2 of 2.

Have fun building trees! The next post will be about general methodology of augmenting data structures and it will discuss dynamic order statistics and interval trees!

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”):