1. Given an unsorted list L with n elements, define the set S: {a, b \in L: a < b and f(a) < f(b)} (where f(x) is x's position in the list). Call a list c-sorted (0 < c \leq 1) if |S|/(\choose{n, 2}) \geq c. For what 0 < c < 1 do there exist sublinear algorithms to c-sort any list L? (We can consider either algorithms that are guaranteed to produce a c-sorting of a list, or those for which the expected value of the expression |S|/(\choose{n, 2}) is at least c.)
2. Define a candy-passing game on a graph G as follows: For the initial state s_0, we assign a number of "chips" to each vertex v. We go from state s_i to state s_(i+1) as follows: if a vertex v with degree d has at least d chips on it, then it "passes" one chip to each adjacent vertex. Denote the maximum degree of a vertex in G by \Delta(G); is it true that, for any initial configuration with at least (\Delta(G)+1)*|V(G)| total chips, there is some k for which s_k = s_(k+1)? Can we place an upper bound on k?
3. Anyone know how to do LaTeX (or any sort of mathematical notation stuff) in Blogger?
1 comment:
Haha... I noticed you were trying and failing to get LaTeX to work. That was good for me, though, because it means I actually understood what was being denoted... most of the time :-D.
Post a Comment