Homework 0 graded

Homework 0 has been graded. The average was 34.82 (stddev = 7.34). More comments will follow later.

Food for Thought: Random Binary Trees

In class, we saw treap, a form of random binary search trees where the priorities are chosen at random. Let us consider a different form of random trees.

Let $\pi$ be a random permutation of the elements of $\{1, \ldots, n\}$. Let $T_\pi$ denote the tree that results from inserting $\{1, \ldots, n\}$ into an initially empty BST in the order of appearance in $\pi$ using the standard BST insert rules (with no rotations). A tree $T$ that is sampled from the distribution of all such trees, uniformly over all permutations, is called a random tree.

Define the size of a node in a BST to be the number of elements in its subtree (including itself). Denote the sizes of the nodes $1, \ldots, n$ by $s_1, \ldots, s_n$.

There are several questions one can ask here:

1. Given a specific tree $T$, what is the probability of getting this tree $P[T]$ in terms of $s_i$'s?
   
2. Suppose we use the following insertion scheme (called INSERT$(i)$).
   After inserting element $i$ at a leaf using standard BST insert, traverse the access path upwards one node at a time.
   For each node $j$ encountered on this path, mark $j$ with probability $(1 + s_j)^{-1}$.
   Rotate $i$ with its parent until $i$ rotates over the highest marked node on the access path (and erase all marks).
   
   Now let $T$ be a BST with root $w$, left-subtree $T_L$ and right-subtree $T_R$.
   Define Join$(T_L, T_R)$ to be the set of trees that can be created
   by rotating nodes with $w$ until $w$ is a leaf, and then deleting $w$.
   Thus, Join$(T_L, T_R)$ is the set $\hat{T}$ of trees such that inserting $w$
   into $T' \in \hat{T}$ yields $T$ with some positive probability (convince yourself of this fact).
   
   Can we show that $P[T] \cdot n = P[T_L] \cdot P[T_R] = \sum_{T' \in Join(T_L, T_R)} P[T']$?
   
   
3. So then... this would imply that the sequence INSERT$(1), \ldots, $ INSERT $(n)$ will create a random tree in this sense.
   

We will post some solutions later :)

Homework 1 posted

Homework 1 has been posted on the course website; you can also click here for the PDF. It will be due back at the beginning of class on Friday, February 6.

We strongly encourage you to start early!

Homework 0 is due tomorrow (Friday)

REMINDER: Homework 0 will be due tomorrow (Friday) at the beginning of class, at 1:30. If you can, use a separate sheet of paper for each problem. Please also staple your homework so that we don't lose it too easily.

MLK Day: No Class Today

There will be no class today in observance of MLK Day.

Kanat's office hours will also be canceled.

HW0 Clarification

Yiming Wang found a problem with Question 5a from homework 0. The vertex $u$ should be in $J_2$ but not in $J_1$. Thanks Yiming!

The PDF on the website has been updated. This homework will be due Friday, January 23, at the beginning of class.

Welcome to 15-750

This is the class blog for CMU 15-750 Graduate Algorithms. The instructor is Gary Miller, and the TAs are Michael Dinitz and Kanat Tangwongsan.

We will use this blog to supplement the course website. Announcements, supplementary materials, homework hints and clarifications, etc. will be posted here. This is a substitute for a mailing list. We encourage your participation in this blog.

Sometimes, we will want to type Math in these posts. To make sure MathML is working correctly, I have ''borrowed'' the following examples (and instructions) from Prof. Ryan O'Donnell's blog. The following two statements should look more or less the same:

A set system $L$ is "laminar" if for all $A$, $B$ $\in$ $L$, either $A \cap B = \emptyset$, $A \subseteq B$, or $B \subseteq A$.

and

A set system L is "laminar" if for all A, B ∈ L, either A∩B = Ø, A ⊆ B, or B ⊆ A.

If it's not working for you, you may need the following extensions:

• IE Plug-in: http://www.dessci.com/en/products/mathplayer/download.htm


• Firefox Fonts: http://www.mozilla.org/projects/mathml/fonts