Skip to content

Instantly share code, notes, and snippets.

@mlhaufe

mlhaufe/CS535_HW6_1.html

Created December 6, 2012 08:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mlhaufe/4222819 to your computer and use it in GitHub Desktop.
Save mlhaufe/4222819 to your computer and use it in GitHub Desktop.
Download ZIP
CS535 HW6
Raw
CS535_HW6_1.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<script type="text/javascript;version=1.8">
"use strict"
function Range(low, high){
if(!(this instanceof Range))
return new Range(low,high)
this.low = low;
this.high = high;
}
Range.prototype.__iterator__ = function(){
for (let i = this.low; i <= this.high; i++)
yield i;
};
function Sum(range,fn){
if(!(this instanceof Sum))
return new Sum(range,fn)
this.range = range;
this.fn = fn;
}
Sum.prototype = {
__iterator__: function(){
for(let i in this.range)
yield this.fn(i)
},
reduce: function(){
return [r for(r in this)].reduce(function(a,b) a + b)
}
}
function Min(range,fn){
if(!(this instanceof Min))
return new Min(range,fn)
this.range = range
this.fn = fn
}
Min.prototype = {
__iterator__: function(){
for(let k in this.range){
yield this.fn(k);
}
},
mindex: function(){
var min = NaN,
last, cur;
for(let i in this){
cur = i;
if(isNaN(min)){
min = i;
} else if (cur < last){
min = i
} else { }
last = cur
}
return [j for(j in this)].indexOf(min) + 1;
},
reduce: function(){
var a = [i for(i in this)]
console.log("\tMin(" + a.join(", ") + ")")
return a.reduce(function(a,b) Math.min(a,b))
}
}
//////////////////////////////////
var a = {
1:1,
2:2,
3:3,
4:4
}
var p = {
1:0.1,
2:0.2,
3:0.3,
4:0.4
}
function p_i(i) p[i];
// A[y][x]
var A = {
1:{0:'',1:'',2:'',3:'',4:''},
2:{0:'',1:'',2:'',3:'',4:''},
3:{0:'',1:'',2:'',3:'',4:''},
4:{0:'',1:'',2:'',3:'',4:''},
5:{0:'',1:'',2:'',3:'',4:''}
}
// R[y][x]
var R = {
1:{0:'',1:'',2:'',3:'',4:''},
2:{0:'',1:'',2:'',3:'',4:''},
3:{0:'',1:'',2:'',3:'',4:''},
4:{0:'',1:'',2:'',3:'',4:''},
5:{0:'',1:'',2:'',3:'',4:''}
}
function optBST(){
let l = 1, n = 4
for(; l <= n; l++){
A[l][l - 1] = 0; console.log("A["+l+"]["+(l - 1)+"] = 0");
A[l][l] = p[l]; console.log("A["+l+"]["+l+"] = " + p[l]);
R[l][l - 1] = 0; console.log("R["+l+"]["+(l - 1)+"] = 0");
R[l][l] = l; console.log("R["+l+"]["+l+"] = " + l);
}
A[l][l - 1] = 0;console.log("A["+l+"]["+(l - 1)+"] = 0");
R[l][l - 1] = 0;console.log("R["+l+"]["+(l - 1)+"] = 0");
for(let d = 1; d <= n - 1; d++){
for(let i = 1; i <= n - d; i++){
let j = i + d;
let min = Min(Range(i,j),function(k){
let w,x,y,z
w = A[i][k - 1]
x = A[k + 1][j]
y = Number(Sum(Range(i,j),p_i).reduce().toFixed(1))
z = w + x + y
console.log("\tA["+i+"]["+k+" - 1] + A["+k+" + 1]["+j+"] + Sum(Range("+i+","+j+"),p_i) ==> " + w + " + " + x + " + " + y + " ==> " + z.toFixed(1))
return z
})
console.log("A["+i+"]["+j+"] = Min(Range("+i+","+j+"), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))")
A[i][j] = min.reduce()
console.log("A["+i+"]["+j+"] = " + A[i][j])
R[i][j] = min.mindex()
console.log("R["+i+"]["+j+"] = " + R[i][j])
}
}
console.log("-------")
console.log("(A[1]["+n+"] = " + A[1][n] +", R[1]["+n+"] = " + R[1][n] + ")")
return [ A[1][n] , R[1][n] ]
}
optBST()
</script>
</head>
<body>
</body>
</html>
Raw
output.txt
A[1][0] = 0
A[1][1] = 0.1
R[1][0] = 0
R[1][1] = 1
A[2][1] = 0
A[2][2] = 0.2
R[2][1] = 0
R[2][2] = 2
A[3][2] = 0
A[3][3] = 0.3
R[3][2] = 0
R[3][3] = 3
A[4][3] = 0
A[4][4] = 0.4
R[4][3] = 0
R[4][4] = 4
A[5][4] = 0
R[5][4] = 0
A[1][2] = Min(Range(1,2), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))
A[1][1 - 1] + A[1 + 1][2] + Sum(Range(1,2),p_i) ==> 0 + 0.2 + 0.3 ==> 0.5
A[1][2 - 1] + A[2 + 1][2] + Sum(Range(1,2),p_i) ==> 0.1 + 0 + 0.3 ==> 0.4
Min(0.5, 0.4)
A[1][2] = 0.4
R[1][2] = 2
A[2][3] = Min(Range(2,3), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))
A[2][2 - 1] + A[2 + 1][3] + Sum(Range(2,3),p_i) ==> 0 + 0.3 + 0.5 ==> 0.8
A[2][3 - 1] + A[3 + 1][3] + Sum(Range(2,3),p_i) ==> 0.2 + 0 + 0.5 ==> 0.7
Min(0.8, 0.7)
A[2][3] = 0.7
R[2][3] = 2
A[3][4] = Min(Range(3,4), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))
A[3][3 - 1] + A[3 + 1][4] + Sum(Range(3,4),p_i) ==> 0 + 0.4 + 0.7 ==> 1.1
A[3][4 - 1] + A[4 + 1][4] + Sum(Range(3,4),p_i) ==> 0.3 + 0 + 0.7 ==> 1.0
Min(1.1, 1)
A[3][4] = 1
R[3][4] = 2
A[1][3] = Min(Range(1,3), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))
A[1][1 - 1] + A[1 + 1][3] + Sum(Range(1,3),p_i) ==> 0 + 0.7 + 0.6 ==> 1.3
A[1][2 - 1] + A[2 + 1][3] + Sum(Range(1,3),p_i) ==> 0.1 + 0.3 + 0.6 ==> 1.0
A[1][3 - 1] + A[3 + 1][3] + Sum(Range(1,3),p_i) ==> 0.4 + 0 + 0.6 ==> 1.0
Min(1.3, 1, 1)
A[1][3] = 1
R[1][3] = 2
A[2][4] = Min(Range(2,4), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))
A[2][2 - 1] + A[2 + 1][4] + Sum(Range(2,4),p_i) ==> 0 + 1 + 0.9 ==> 1.9
A[2][3 - 1] + A[3 + 1][4] + Sum(Range(2,4),p_i) ==> 0.2 + 0.4 + 0.9 ==> 1.5
A[2][4 - 1] + A[4 + 1][4] + Sum(Range(2,4),p_i) ==> 0.7 + 0 + 0.9 ==> 1.6
Min(1.9, 1.5, 1.6)
A[2][4] = 1.5
R[2][4] = 2
A[1][4] = Min(Range(1,4), A[i][k - 1] + A[k + 1][j] + Sum(Range(i,j),p_i))
A[1][1 - 1] + A[1 + 1][4] + Sum(Range(1,4),p_i) ==> 0 + 1.5 + 1 ==> 2.5
A[1][2 - 1] + A[2 + 1][4] + Sum(Range(1,4),p_i) ==> 0.1 + 1 + 1 ==> 2.1
A[1][3 - 1] + A[3 + 1][4] + Sum(Range(1,4),p_i) ==> 0.4 + 0.4 + 1 ==> 1.8
A[1][4 - 1] + A[4 + 1][4] + Sum(Range(1,4),p_i) ==> 1 + 0 + 1 ==> 2.0
Min(2.5, 2.1, 1.8, 2)
A[1][4] = 1.8
R[1][4] = 3
-------
(A[1][4] = 1.8, R[1][4] = 3)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment