chaoxu

12 ms·

91.
by chaoxu 10y ago
I almost exclusively work on problems can be solved(by a combinatorial algorithm) in polynomial time. I have never used theory of mixed integer linear programs, but that's because I focus on different aspects of combinatorial optimizat
92.
by chaoxu 10y ago
I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial algorithms instead of going for gradient descent.
93.
by chaoxu 10y ago
If there is no need for predicting memory utilization, then doesn't real time GC fit the bill? Consider all your know w/e you want execute in time T. A real time GC make sure it always execute in time 2T. For any sequence of opera
94.
by chaoxu 11y ago
np. There might be ways to speed up the running time for this special case. Naive algorithm using submodular minization + maximum matching as an oracle would take around O(n^c) where c is probably more than 10.
95.
by chaoxu 11y ago
I have just answered one of those problems here. http://cstheory.stackexchange.com/questions/20245/subset-of-... I hope I didn't misunderstood the problem.
96.
by chaoxu 11y ago
Here is an accessible algorithms paper. It's a cute puzzle problem. It was inspired by answers on cs.stackexchange. Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts http://arxiv.org/abs/1502.04048
97.
by chaoxu 11y ago
It's actually a reference to a disclaimer in Algorithm Design Manual. I don't think he actually reviewed the lecture notes. The Algorithm Design Manual had the following(page ix in second edition) "Any errors, deficiencies, o
98.
by chaoxu 11y ago
I was a TA for classes using this material. We(the TAs) sometimes come up with problems to be incorporated in it. The lecture notes are superb, I often refer people to them because it's freely available. The hw is basically"given
99.
by chaoxu 11y ago
There is no proof that this approximates the Levenshtein distance. Might be interesting to show this is true. (or somehow characterize all the bad cases)
100.
by chaoxu 11y ago
probabilistic convolution tree is not much more involved. In some sense it's just multiple polynomial multiplication. But anyway, coin change problem can be solved much faster. http://link.springer.com/article/10.
101.
by chaoxu 11y ago
I'm still looking for a open source version of this so I can create a nice collection of algorithm problems.
102.
by chaoxu 11y ago
Another way to think of this problem is find a feasible flow in a complete graph that satisfy all vertex demands and using minimum number of edges.
103.
by chaoxu 11y ago
Author here. The idea is a mix of many things. This is not how we write it in the paper, but just for intuition. If Σ(S) is the set of all subset sums of S, where S={s_1,...,s_n}, then Σ(S) = Σ(s_1)+Σ(s_2)+...+Σ(s_n). Here A+B = {a+b|a in
104.
A Faster Pseudopolynomial Time Algorithm for Subset Sum(arxiv.org)
34 points by chaoxu 11y ago|2 comments
105.
by chaoxu 12y ago
The problem seems to be: find the smallest regular k-gon that covers all the points. (now, assume the total number of points is n, and k = O(n)) One can transform the problem to the following, and solve it in around O(n^7) time. http:&#x2
106.
Marking Streets to Improve Parking Density(arxiv.org)
8 points by chaoxu 12y ago|1 comments
107.
by chaoxu 12y ago
Not everyone mit graduate is MIT professor good.
108.
by chaoxu 12y ago
I want to see something like this but with Haskell. So I get to see if Haskell is nice for expressing algorithms.
109.
by chaoxu 12y ago
"For example, to computationally identify the likely boundary of something - a microscopic cell, or submicroscopic cellular component." I still don't know which field you are from, thus I kindly request you to give me a defin
110.
by chaoxu 12y ago
It would be nice if you explicitly state you are learning Haskell in your article. If I'm a newbie and I see some of the awkward Haskell code(which I also make sometimes), I would feel discouraged. It doesn't seem Haskell is makin
111.
by chaoxu 12y ago
This does make sense under author's definition: convex hull is defined as the boundary of any convex set enclosing the set of points. But in standard terminology, convex hull of a set S is the smallest convex set containing the set of
112.
by chaoxu 12y ago
Of course, using the most abstract definition is not the best idea, but anything equivalent to the standard terminology is ok. For example, in 2d, we can san say the convex hull of a finite set of points is the smallest enclosing convex pol
113.
by chaoxu 12y ago
I don't see which part the wikipedia is contradicting it self, could you point out? I see all 4 definition which are all equivalent. What is your domain? I be interested in seeing the motivation of defining convex hull that way. Becau
114.
by chaoxu 12y ago
I have a hard time understanding why the author go out of his/her way to rename standard definitions. 1. The definition of convex hull of a set S in the article, is the boundary of a convex set that contains all the points in S. The st
115.
by chaoxu 12y ago
You could have taken a algorithms class. Since you are from Uiuc, ask people around you for a referral, which would land you a phone interview or coding challenge. Certain companies send out coding challenges. I think Dropbox do.
116.
by chaoxu 12y ago
I think he meant algorithms with certain guarantee to be "not wrong". Say, "right with high probability" or "within a constant factor from the optimal" etc. Many heuristic does not have any guarantee(unless som
117.
by chaoxu 12y ago
Why not just have a remote desktop session and see everything someone does? Someone might code best in eclipse. And interviewer might even allow the interviewee use the internet to search. You get to see the entire workflow.
118.
by chaoxu 12y ago
Writing out full solution of all the exercise might be another textbooks. Math textbooks even left proof of theorems as an exercise to the reader.
119.
by chaoxu 12y ago
For cs people the more important would be property testing, since often we are interested in finding out if something holds with high probability without read everything. A common possibility is mapping a subset of set of vertices of a grap
120.
by chaoxu 12y ago
As far as I know, the applications are for theoretical problems and has no application in everyday work.

More ›