## Dynamic Programming : ZigZag : TCCC03 Semi Final 3 level 1

December 31, 2012
```	public int longestZigZag(int[] sequence){
if(sequence.length == 1) return 1;
int[] L = new int[sequence.length];
int[] diff = new int[sequence.length-1];
int maxLength = 1;
boolean maxValue;

for(int j =0; j<(sequence.length - 1);j++){
diff[j] = sequence[j+1] - sequence[j];
}
if(diff[0] >= 0) maxValue = true;
else maxValue = false;

for(int j = 1; j< diff.length;j++){
boolean curValue= maxValue;
if(diff[j] > 0 ) curValue = true;
else if(diff[j]<0) curValue = false;
if(curValue != maxValue){
maxLength++;
maxValue = curValue;
}
}

return maxLength+1;
}```

## Benchmark Trade Bond Price Challenge : kaggle

December 26, 2012

This post was long overdue. I participated in the benchmark trade bond pricing challenge and used a regression based approach to predict bond prices. Here is an outline of the approach.

1. Build on the training set and predict on the test set. The dependent variable we are trying to predict is the bond price and the independent variables are last 10 trade prices.
2. Prepare frequency charts based on callability is 0 or 1.
3. Divide the data into 12 parts – callability, price > 100 or price < 100(bond price will always converge to 100 so the curve will look different), types of trade in the bond (dealer to dealer, dealer to client, client to client – quotes driven market)
4. Some of the values were missing – missing value treatment (based on exponential weights)
5. Run regression on these sub-data sets and analyze the results
6. Some of the t-tests failed – bond ids and time to delay – p value that was kept as cut off for rejecting the coefficients is 3%

Notes :

1. R2 is a statistic that will give some information about the goodness of fit of a model. In regression, the R2 coefficient of determination is a statistical measure of how well the regression line approximates the real data points. An R2 of 1.0 indicates that the regression line perfectly fits the data.
2. R2   measures goodness of fit. But it will not detect overfit because it will increase with any new predictor (unless it has already reached 1).
3. Assumptions of Regression
4. L Linear relationship
I Independent observations
N Normally distributed around line
E Equal variance across X’s
5. Multicollinearity : When two independent variables are correlated and its detection – Variance Inflation Factor
6. A p-value is the probability of an observed or more extreme result arising by chance. So, if p<.03, then that probability is quite less and hence, we can keep that independent variable

I have been away from data science now because of job change and interviewing. New Year Resolution : get back to kaggle .

## Learning and Mastering Java

December 25, 2012

Here is my target list for the enxt year. I have read all these books in some bits and pieces, but this year I want to be thorough with my knowledge.

## SRM 208 Div 1 : TallPeople

December 25, 2012
```
public int[] getPeople(String[] people) {
int[] ret = new int[2];
int R=people.length,C=people[0].split(" ").length;
int[][] arr = new int[R][C];

for(int i = 0;i<R;i++){
String[] split = people[i].split(" ");
for(int j=0;j<C;j++){
arr[i][j] = Integer.parseInt(split[j]);
}
}

int maxMinRow = Integer.MIN_VALUE;
for(int i = 0;i<R;i++){
int minRow = Integer.MAX_VALUE;
for(int j=0;j<C;j++){
if(arr[i][j]< minRow)
minRow = arr[i][j];

}
if(maxMinRow < minRow)
maxMinRow = minRow;
}
ret[0] = maxMinRow;

int minMaxCol = Integer.MAX_VALUE;
for(int i = 0;i<C;i++){
int maxCol = Integer.MIN_VALUE;
for(int j=0;j<R;j++){
if(arr[j][i]> maxCol)
maxCol = arr[j][i];

}
if(minMaxCol > maxCol)
minMaxCol = maxCol;
}
ret[1] = minMaxCol;

return ret;
}

```

December 25, 2012

Hello Competitive Programming ! My first entry into topcoder :

```
{
public String getTask(String[] list, int n)
{
List<String> myList = new ArrayList<String>();
for(int i=0;i<list.length;i++) {
}
int pos = 0;
while (myList.size() > 1) {
pos = (pos + n - 1)%myList.size();
myList.remove(pos);
pos = pos % myList.size();
}
return myList.get(0);
}
}

```

## Implement an algorithm to print all valid (e g , properly opened and closed) combinations of n-pairs of parentheses

December 25, 2012

Input : 3

Output : ()()(), ()(()), (())(), ((()))

```
public static void printPar(int l, int r, char[] str, int count) {
if (l < 0 || r < l) return; // invalid state
if (l == 0 && r == 0) {
System.out.println(str); // found one, so print it
} else {
if (l > 0) { // try a left paren, if there are some available
str[count] = ‘(‘;
printPar(l - 1, r, str, count + 1);
}
if (r > l) { // try a right paren, if there’s a matching left
str[count] = ‘)’;
printPar(l, r - 1, str, count + 1);
}
}
}

```

## Sudoku Solver

December 2, 2012

The Sudoku solver can be implemented as a recursive backtracking solution.

Pseudo Code for any backtracking solution :

bool Solve(configuration conf)
{
if (no more choices) // BASE CASE
return (conf is goal state);
for (all available choices) {
try one choice c;
// solve from here, if works out, you’re done
if (Solve(conf with choice c made)) return true;
unmake choice c;
}
return false;  // tried all choices, no soln found
}