What do you do when Chrome is blocked by the firm even installed without admin rights

Not sure if this works for everyone but this is the simplest way you can find on google and myself had experienced this issue for a long time.
1. Down load the chrome installer
2. Install it
3. Go to C:\Users\YOURUSERNAME\AppData\Local\Google\Chrome\Application
4. Change chrome.exe -> WHATEVERYOULIKE.exe
5. Enjoy your chrome

An update about when finding out Safari blocked java 7

It is a problem that Chrome doesn't support java 7 on OSX. So after I got my mac I disabled java 7 and turn back to java 6 so as to use the 32-bit chrome (I have no idea why chrome abandoned the ones that are eager to use chrome on their mac with Lion or Mountain Lion. And why OSX started to abandon Oracle's Java by taking away the Java Preference in the System Preference).

Anyway, now I need switched back to Safari to run some cool applets on Prof. Perlin's home page. Then I found that Safari always remind me to update to the latest version of java even if I download java 7 already. Also, the testing page doesn't work at all even all the solutions listed have been tried. This was due to the version under 1.7.10.22 has security problems and safari started to block java. So the solution you can try, is to type the following command, or open the file with administration privilege:

cd /System/Library/CoreServices/CoreTypes.bundle/Contents/Resources
sudo vim XProtect.meta.plist

You will see that 

        JavaWebComponentVersionMinimum
        1.6.0_37-b06-435
        LastModification
        Thu, 31 Jan 2013 04:41:14 GMT
        PlugInBlacklist
        
                10
                
                        com.macromedia.Flash Player.plugin
                        
                                MinimumPlugInBundleVersion
                                11.3.300.271
                        
                        com.oracle.java.JavaAppletPlugin
                        
                                MinimumPlugInBundleVersion
                                1.7.11.22
                        
                
        
        Version
        1038

Now we can see that the Minimum PlugInBundleVersion is 1.7.11.22 (While my version is 1.7.11.21). So all we need to do is change this number to a version that is lower than what we have right now then Java should work smoothly.

Also, if you want to bring up the Java Console, Java 7 has the Java in System Preference. There are bunch of settings you can play with. If you want to get back the Java Preference which has been taken away by OSX, go to download and install the dmg package called Java Essential, then you can choose the preferred version of Java.

What to do when my mac complains about ntfs-3g cannot unmount bootcamp?

The error message is:

NTFS-3G could not mount /dev/disk1s1

at /Volumes/Noga_Serials because the following problem occurred:

Did not receive a signal within 15.000000 seconds. Exiting...

Everytime I started my os x system after I installed windows 8 with bootcamp, or I plugin an external hardrive which is NTFS format, this message appears and looks ugly actually.

Actually the message does no harm and the drive is correctly mounted...

But I still did not prefer this kind of unfriendly information. At first I thought it was the problem of some improperly mounted disk so I tried to unmount some dir under /Volumes/ but that doesn't work at all because all as removing bootcamp will lead me to no where.

Then I thought of what drivers will be better to mount the hardrives and I think MacFuse is quite better and works smoothly. So do install MacFuse then NTFS-3g (though the latter works fine but the error message is really annoying).

Nov 7, 2013:
My bad, after removing the NTFS-3g I was not able to get write access to my NTFS drive. That was just a bug for NTFS-3g but it still allows R/W access to driver.

Portfolio Optimization with Simple Heuristic

Lately on the Heuristic course we have competition of Portfolio. It simulates the real market but largely simplified into a game that we can play with. The description is as here. And the whole gaming process can be found on this website.

A detailed description is given as below:

Initialization

We call the ith gamble g[i]. Each gamble will have three different returns (gihi, gimed, gilow), mapping to three initial probabilities(gihiprob, gimedprob, gilowprob), where the gimedprob is at least 0.4.

Initially, the average expected return per gamble is 2 to 1. Thus the expectation is E=gihi*P(gihi)+gimed*P(gimed)+gilow*P(gilow)=2. Different gambles may give different returns. Low returns are normally less than 1 (so constitute a loss). During each round, we permute all the gambles, and get a new sequence of gambles g'1, g'2, ..., g'n.

Classes

Now we assume each gamble belongs to a class (which is also true in reality), ranging from 1 to 15. Among these classes some are favorable classes, some are neutral, and some are unfavorable. The favorable classes bias the gihiprob higher while the unfavorable bias the gilowprob higher. Number of gambles in each classes might not be equal. We have the following rules to change the probabilities of the gambles in the classes:

for i = 1, N do
  if gi is favorable
    P(gihi) += P(gilow) / 2
    P(gilow) /= 2
  else if gi is unfavorable
    P(gilow) += P(gihi) / 2
    P(gihi) /= 2
end

Link

Certain gamble have links to each other. Link also makes a series of gambles change their probabilities of returns during each round.  The link if different from class, and it gives a correlation between two gambles. For example, the stock price of Microsoft and the price of Nokia will influence each other (I consider these two are not necessarily in the same class). The way of calculating the link's influence to a gamble's probability is as follows:

permute gamble sequence: g'=perm(g)
for i = 1, N do
  Hi = all gambles before g'i that have links with g'i and have high return
  Mi = same but have medium return
  Li = same but have low return
  if Hi > Mi + Li
    P(gihi) +=P(gilow) / 2
    P(gilow) /= 2
  else if Li > Mi + Hi
    P(gilow) += P(gihi) / 2
    P(gihi) /= 2
  Play gi
end

Thus, the full sequence of operation is:

1. Reset each probability to initial 
2. Make adjustments based on favorable/unfavorable classes 
3. Start computing gambles, making adjustments based on links as you go 

Task

Suppose we can bet (invest) on approximately N gambles (stocks). We are given the capital of 1 (the total money or budget you initially have is 1). Our task is to allocate the 1 unit among chosen number of gambles.

Game

1. In the first game we play 5 round.
a. Assign outcomes to each gamble according to the probability above.
b. Calculate each person's wealth based on their allocation and the outcomes (having started each round at 1).
If return of the person >=2, then that person gets a point for that round. The player will be told what the final return outcome of each gamble was to help the player infer which class is favorable and perhaps change allocations for the next round.

The player is not told which order the gambles were played in however. The favorable and unfavorable classes will remain the same during the five rounds.

2. In the second game we play 200 round.

The favorable and unfavorable classes may change up to 10 times (without warning) during those rounds. Again, the player will be told what the final return outcome of each gamble was to help the player infer which class(es) is(are) favorable and perhaps change allocations for the next round. Players need not be fully invested during all rounds. Inspired by Jake Loveless's experience at a finance company where consistent winnings are favored over erratic profits and losses, we will have two criteria for winning: total amount of money at the end, and 10 percentile daily return (that is sort all daily returns from least (most negative) to greatest and take the return that is at the 10th percentile in that list). In the original game, we used Sharpe Ratio as the criteria, which is computed as

sum(return) / sqrt(sum((return - avg_return)^2))
Here the return is the real value of profit we make each round (though the real sharpe ratio is given as a ratio).

Tackling the first problem

For the first game, our intuitive goal is to find some combination of gambles, that give the largest probability of return that is larger than 2.

For example, if we bet two gambles g0, g1, and we allocate x to g0, then the probability that return >=2 is (here i and j has 3 values: 0:high, 1: medium, 2: low):

for (int i = 0; i < 3; ++ i) {
  for (int j = 0; j < 3; ++ j) {
    if (g0.getReturn(i) * x + g1.getReturn(j) * (1-x) >= 2) {
      prob += getProb(g0, i) * getProb(g1, j);
    }
}

This method is guaranteed to have the best probability in the set of gambles with fixed amount of gambles, by traversing all the possible combinations of the selected gambles with different ratio assigned to each gamble. However, in the scenario of two gambles, if we explore the ratio (x) by a step size of 0.01 each time, we will have 100 * N * N computation. If we want to select many gambles, the time complexity is factorial.

But do we really need so many gambles to decide which will give the best return? Actually for the first game we don't need to complicate the problem. If we can find the best allocation in one or two gambles that get us a point, we don't really care about whether the return is 2 or 100. If we name the previous function computeProbability, we have the following algorithm:

double best_prob = 0;
int[] best_comb = new int[2];
double best_x = 0;
for (double x = 0; x <= 1; x += 0.01) {
  for (int i = 0; i < gambles.size() - 1; ++i) {
    for (int j = i + 1; j < gambles.size(); ++j) {
      double prob = computeProbability(i, j, x);
      if (prob > best_prob) {
        best_prob = prob;
        best_comb[0] = i;
        best_comb[1] = j;
        best_x = x;
      }
    }
  }
}

We usually get 5 points in 5 rounds, that means the easy algorithm works quite well to meet the requirement.

Solving the second problem

Here I will firstly explain the original solution to solve the problem to get the best sharpe ratio.

This problem gives more complicated scenario: besides links making probabilities of gambles change each round, the classes might also change.

But do we really want to consider all these complex changes? Lets look at the Sharpe Ratio again:
sum(return) / sqrt(sum((return - avg_return)^2))
It is the measurement of return per risk. The assumption is that if the returns of the gambles of your portfolio stay fixed, but they vary tremendously, the sharpe ratio will be small. This is because the denominator, which is the variance of the returns, will be large. Then you might risk in earning a lot of money for a round, than lose a lot in the next. Also, if you keep the denominator fixed, and make the sum of return as large as possible, the sharpe ratio will be large.

Based on the formular, to get the best sharpe ratio, we need to make the denominator as small as possible. If we can make the return of each round as close as we can, say, almost 0, we will get the denominator almost 0. It doesn't matter if the return is large or small, say 2 or 100, because the nominator and denominator are both multiplied by a constant.

So we bet on some gambles, say 5 gambles, which produce the smallest variance of the high, medium and low returns. If there is one stock whose variance is less than 0.0001, we only bet on that gamble.

PriorityQueue q
for (int gi = 0; gi < n; ++gi) {
  var = computeVariance(gi)
  if gi.avg < 1.2 continue // not consider gi whose average is less than 1.2
  q.add(var)
  if q.size() > 5 // maximum gambles we bet on is 5
    q.poll()
}

smallest = smallest variance in q
if smallest < 0.0001
  only bet on the gamble
else
  bet on all gambles in q

Actually this is really impractical though we gives a very large sharpe ratio, average 10000 during experiments. Because we are not making any money when betting on the stablest gambles.

So now the goal is to make as much money as possible.
Here is the other strategy we used during the competition, which makes billions of money in the scenario.

Now we do need to consider the class problem inorder to get a really big return in each round. To make the strategy as simple as we can, we only bet on one gamble with the highest return (You could make it onto several gambles but the idea here is quite simple). Because the class will change, we need a function to guess the favorable and unfavorable classes. Here I will introduce the depth we trace in history. We only consider a certain time limit of data, say only the previous round, to obtain information of guessing the class of the gamble. Adapting Machine Learning techniques here might contribute more but then it's more than heuristic and not what I am going to cover.

For each current round we update return probability based on the previous round and linking information. And then we look at the previous rounds, if number of high returns (Hi) is more than number of low returns (Li) in the depth we trace, we consider it to be among favorable classes, and vice versa.

int[] probAdaption // save the number of probabilities being high or low

for (int i = 0; i < n; ++i) {
  if (gi.return
    if (probAdaption[i] >= traceDepth) continue;
    ++probAdaption[i];
    } else if (gi.return == Gamble.LOW) {
      if (probAdaption[i] <= -traceDepth) continue;
      --probAdaption[i];
  }
}

Because we are not sure of the adaptation with this strategy, so we don't actually make P(gihi) +=P(gilow) / 2, P(gilow) /= 2, we give an experimental coefficient to replace the 0.5 coefficient. 

int adaption = probAdaption[id];
while (adaption > 1) {
  adaption = 0;
  double d = lProb * adaptionCoefficient;
  lProb -= d;
  hProb += d;
}
while (adaption < -1) {
  adaption = 0;
  double d = hProb * adaptionCoefficient;
  hProb -= d;
  lProb += d;
}

The last thing is to pick the largest expected return among n gambles. That's it. Our strategy doing portfolio. This strategy returns near 5 - 10 times of the previous round in average.

The Traveling Salesman Problem

The problem description is given in the class:
http://cs.nyu.edu/courses/Fall12/CSCI-GA.2965-001/travelingsalesman.html

From a graph perspective, this problem can be brief as:

Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight.

To traverse all posible city sequence and find the best solution (optimal distance score), time complexity is as high as factorial time O(n!) with simplest recursion. Or to make things simpler, try use dynamic programming to reduce a great amount of efforts and get almost 30 cities run on my laptop.

Many strategies and heuristic are used to solve this problem, such as minimum matching and Simulated Annealing. We chose to use Simulated Annealing as our base algorithm for its flexibility to do optimization.

One general idea is to obtain the Minimum Spanning Tree (MST). For the baseline by traversing every nodes on the MST twice, we get solution up to 2*score of the shortest path. In the input provided, the shortest path of MST is ~625,000 miles, so our baseline is ~1,250,000.

Step 1
Consider the distance score  = sigma^n d[i][j], where n is total number of cities, d[i][j] is distance from city i to city j. And consider score_i = score after the ith iteration.

The primitive version is to randomly generate a city sequence. Then swap 2 cities in each iteration. The score will be updated (accepted) if the score_(i+1) < score_i || (score_(i+1) - score_i)/T > R(0, 1). 

The good thing about this algorithm is that it is really simple, and it allows worse result in order to search a larger solution space. This gives a result ~1,200,000, which is almost the same as the baseline with time limitation of 2 min. :( What can be realized is that this way doesn't shuffle the city sequence a lot as we swap every two cities at a time. So By swapping two fixed length of cities in the sequence as below:

ab1234cde5678fg

ab5678cde1234fg

Here the numbers are cities that are going to be swapped, where letters are cities stay in their current position. But still this doesn't make a lot improvement. So instead of swapping fixed length sub-sequence, we make the length arbitrary as below:

ab123cde45678fg

ab45678cde123fg

With this method and a lot of code optimization, we successfully reduce the score into 960,000. 

We don't shuffle inside the chosen sub-sequence is because that will cause more calculation of the distance score, thus reduce the number of iteration we can run. As in Simulated Annealing, it is guaranteed that with unlimited amount of time,  the optimal score should be obtained. That means we have two ways to improve our algorithm: one is to optimize our swapping (replacement) strategy, the other is to make the iterations to run as many as possible.

Step 2

As to the second one, we make the start sequence as reasonable as possible to avoid random solutions that actually make score worse by accepting bad scores. So we use the Depth First Search of MST as our initial sequence, instead random generalization. During the DFS, if the node in the tree has been visited, we skip and continue searching the whole tree. 

Also, we optimize our random() method by bit manipulation instead of Java.util.Random. This makes three times of iterations as before and start with 970,000 instead of very random scores larger than 1 million. 

Another method is that, after lowering the temperature several times to a low value, we only accept better scores, regardless of the probability of worse scores might generate larger solution space. Then we found the cooling temperature and the acceptance probability becomes not that important because we have already begun with an very small value, so accepting worse values will be meaningless even if we might be easy to get into local minimal solution. So we only accept the better scores through all iteration.

Step 3

As to the first one. We developed a different replacement method. The strategy is described as follow:

1. Save all the neighbors of the city sorted from the nearest to the farthest;
2. Randomly pick a start point a of the sequence;
3. Randomly pick b from the closest 4 neighbor cities around a, which the probability decrease from the closest to the farthest.
4. Reverse the sub-sequence of the city sequence start from city next to a to b.

For example:

abc12345defg

abc54321defg

Consider the start point we choose is c, and 5 is one of the closest 4 cities to c. So we reverse the sub-sequence from the point next to c, which is 1, to 5. Why this should work? Because you are trying to get a better path by making the almost closest cities to be the next city to travel, so this is much better heuristic than trying to do reverse randomly. We are not using the closest one because this will let the model go into local optima easily.

This simple model successfully beat all other 9 teams in our class. It wins because of the ability to run extremely fast by optimize every operation, and the heuristic of initialization and replacement. Anyone with different or better solution is welcomed to discuss with us.

Our code is on GitHub and running command is just (Consider the input file is the same directory as the  java files)

javac SAOpt.java MST.java

java SAOpt

Accessing Gmail Accounts through Mail

Today when I was trying to add my nyu account to mail it always showed the same error message: server rejected your username and password.
 Some people mentioned cleaning the Captcha but it didn't work for my case. So I explored google support and I got the way to figure it out.

First go to account:

Then click on security:

And turn the 2-step verification on (It might require you to login again). After turning it on you will be able Generate new application-specific password by edit Authorizing application and sites.

Each application will need a new password but you will need to enter it once then it's all set.

I still have a lot problems switching from my pc to mac, such as shortcut keys issue and personal settings. And now I should say Mac is a good system, much better than windows in a lot of aspects.

jQuery plugIn: Fixed header table for IE

For the purpose of building a spreadsheet-like table, I will have to make the table header fixed while the body is scrollable. While in Chrome and Firefox you can accomplish this simply set the css of the table body: scrollable. This does not work for IE. After searching I used one plugin on the internet called http://www.farinspace.com/jquery-scrollable-table-plugin/.
And modified it into my own edition.  To use it, simply type:

$("#"+TABLEID).createScrollableTable();

Code is as below:

(function($) {
$.fn.createScrollableTable = function(options) {
var defaults = {
width: '1160',
height: '600'
};
var options = $.extend(defaults, options);


return this.each(function() {
var table = $(this);
prepareTable(table);
});


function prepareTable(table) {

var tableId = table.attr('id');
var tb = $('#'+tableId);
var wholeWidth = $("#"+tableId).width() > options.width ? $("#"+tableId).width() : options.width;
// wrap the current table (will end up being just body table)
var minheight = 580;
var css;
if (minheight > $("#"+tableId).height()) {
css = {
'width': options.width,
'height': $("#"+tableId).height()+20,
'overflow': 'auto'
};
}else {
css = {
'width': options.width,
'height': options.height,
'overflow': 'auto'
};
}
var bodyWrap = table.wrap('<div></div>')
.parent()
.attr('id', tableId + '_body_wrap')
.css(css);

var thead_tr_first = $('thead tr:nth-child(1)',tb);
var tbody_tr_first = $('tbody tr:first',tb);
var col_width = [];
var w = 0;
var cells_head = thead_tr_first.find('th');
var cells_body = tbody_tr_first.find('td');
if (cells_body.length == 1) {
for (var i = 0; i < cells_head.length; ++i) {
col_width[i] = $(cells_head[i]).width();
}
}
else if (cells_head.length == 0) {
for (var i = 0; i < cells_body.length; ++i) {
col_width[i] = $(cells_body[i]).width();
}
}
else {
for (var i = 0; i < cells_body.length; ++i) {
col_width[i] = $(cells_head[i]).width() > $(cells_body[i]).width() ? $(cells_head[i]).width() : $(cells_body[i]).width();
}
col_width[0] = col_width[0] < 0 ? 20 : col_width[0];
}

var thead_cols = $('thead tr:nth-child(1)',tb).find('td, th');
var tbody_cols = tbody_tr_first.find('td');

var tbh = $('<table class="tablesorter" cellspacing="0"></table>').insertBefore(bodyWrap).prepend($('thead',tb));
tbh.css('width', options.width);
var css_head = {
'width': options.width,
'overflow': 'hidden'
};
var headWrap = tbh.wrap('<div></div>').parent().attr('id', tableId + '_head_wrap').css(css_head);

$.each($('.tablesorter'), function(i, elem) {
$(elem).css('width', wholeWidth);
$(elem).css('table-layout', 'fixed');
});

$.each (thead_cols, function (i, elem) {
$(elem).width(col_width[i]);
// $(elem).css('width', col_width[i]);
});
$.each (tbody_cols, function (i, elem) {
$(elem).width(col_width[i]);
// $(elem).css('width', col_width[i]);
});

bodyWrap.scroll(function () {
headWrap.scrollLeft($(this).scrollLeft());
});
}


function getWidth(td) {
if ($.browser.msie) { return $(td).outerWidth() - 1; }
if ($.browser.mozilla) { return $(td).width(); }
if ($.browser.safari) { return $(td).outerWidth(); }
return $(td).outerWidth();
};


};
})(jQuery);