September 27, 2011

P -> NP -> NPC -> NPH

Polynomial -> Nondeterministic Polynomial -> Nondeterministic Polynomial Complete -> Nondeterministic Polynomial Hard

Polynormial (wiki): is an expression of finite length constructed from variables (also known as indeterminates) and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents. For example, x2 − 4x + 7 is a polynomial, but x2 − 4/x + 7x3/2 is not, because its second term involves division by the variable x (4/x) and because its third term contains an exponent that is not a whole number (3/2).

Would the n! algorithm be considered a solution in polynomial time? A factorial certainly doesn't appear to be a term raised to a power.
No. factorial time is not polynomial time. Polynomial time normally means an equation of the form O(Nk), where N = number of items being processed, and k = some constant. The important part is that the exponent is a constant -- you're multiplying N by itself some number of that's fixed -- not dependent on N itself. A factorial-complexity algorithm means the number of multiplications is not fixed -- the number of multiplications itself grows with N.

September 25, 2011

Dijkstra's Algorithm

I just found a website site which have enough demos with animation when you click on the graph for you guys to play around to understand Dijkstra's process. Enjoy it with the reference link bellow!

Reference

September 24, 2011

C# - MVC2.0 Flow

September 23, 2011

C# Model - DataAnnotations

using System.ComponentModel.DataAnnotations;

[Required(ErrorMessage="ID is required.")]
public int id { get; set; }

[Required(ErrorMessage="Name is required")]
public string name { get; set; }

[Required(ErrorMessage="Age is required"), Range(0, 20, ErrorMessage="Age is between 0 and 20.")]
public int age { get; set; }

C# - MVC to prevent Non-existed Action & Content Information

protected override void HandleUnknownAction(string actionName)
{
Response.Write("Oops! You're trying to invoke a non-existed action called "+ Server.HtmlEncode(actionName));
//base.HandleUnknownAction(actionName);
}
//======= Content Information:
string infor = "User: " + User.Identity.Name +"<br/>"
+ "Server: " + Server.MachineName + "<br/>"
+ "Script timeout: " + Server.ScriptTimeout + "<br/>"
+ "User IP: " + Request.UserHostAddress + "<br/>"
+ "Preferred language: " + Request.UserLanguages[0] + "<br/>"
+ "Browser: " + Request.Browser + "<br/>"
+ "Raw URL: " + Request.RawUrl + "<br/>"
+ "Http method: " + Request.HttpMethod + "<br/>"
+ "Controller: " + RouteData.Values["controller"] + "<br/>"
+ "Action method: " + RouteData.Values["action"] + "<br/>"
+ "ID: " + RouteData.Values["Id"];
return Content(infor);

September 21, 2011

Memoized LCS (Longest Common Subsequence) and Fibonacci

========== Normal LCS
static int LCSCall(String[] arr1, String[] arr2, int m, int n){
count++;
if(m == 0)
return 0;
else if (n == 0)
return 0;
else if (arr1[m] == arr2[n])
return LCSCall(arr1, arr2, m-1, n-1) + 1;
else{
int temp1 = LCSCall(arr1, arr2, m, n-1);
int temp2 = LCSCall(arr1, arr2, m-1, n);
return (temp1>temp2)? temp1: temp2;
}
}

========== Memoized LCS
static int memoize(String[] arr1, String[] arr2, int m, int n){
Fn = new int[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
Fn[i][j] = -1;
}
}
return memoizeLCS(arr1, arr2, arr1.length-1, arr2.length-1);
}

static int memoizeLCS(String[] arr1, String[] arr2, int m, int n){
count2++;
if(Fn[m][n]>=0)
return Fn[m][n];
else if(n==0)
Fn[m][0]= 0;
else if(m==0)
Fn[0][n]=0;
else if(arr1[m] == arr2[n])
Fn[m][n] = memoizeLCS(arr1, arr2, m-1, n-1) + 1;
else{
int temp1 = memoizeLCS(arr1, arr2, m, n-1);
int temp2 = memoizeLCS(arr1, arr2, m-1, n);
Fn[m][n] = (temp1>temp2)? temp1: temp2;
}
return Fn[m][n];
}

========== Normal Fibonacci
static int Fibonacci1(int num){
count++;
return (num <= 2) ? 1: Fibonacci1(num - 1) + Fibonacci1(num - 2);
}

========== Memoized Fibonacci
static int memoizeFib(int num){
Fn = new int[num];
for(int i = 0; i<num; i++)
Fn[i] = 0;
return Fibonacci2(num-1);
}

static int Fibonacci2(int num){
count2++;
if(num ==0 || num ==1)
Fn[num]=1;
else if(Fn[num]==0)
Fn[num] = Fibonacci2(num-1) + Fibonacci2(num-2);

return Fn[num];
}

Bi-Connected Graph

Depth-First Search has longer path than Breadth-First Search but it has bi-connected Component. Both can have Spanning forest, connected component, paths, and cycle.

Knapsack - Calculation & Algorithm

Knapsack Algorithm:for w = 0 to W
B[0,w] = 0
for i = 1 to n
B[i,0] = 0
for i = 1 to n
for w = 0 to W
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w]
// wi > w

Reference

September 07, 2011

EntityFramework Query Tracking Tool: Entity FrameworkProfiler

It's a listener which is gonna tell me what is going on with Entity framework when I run any query.
1st - I need to add one reference HibernatingRhinos .Profiler.Appender into my application
2nd - Write one line of code, HibernatingRhinos .Profiler.Appender .EntityFramework .EntityFrameworkProfiler .Initialize(), before any LINQ statement that I use to connect with data by using Entity framework.
3rd - Run "Entity FrameworkProfiler"
4th - Compile my application

[Options -> Settings -> dis-check "Auto Update"]
[Free 30days trail]
<Reference>

September 05, 2011

EntityFramework

var ctx = new NorthwindEntities();
var query = ctx.Products.Where( x=> x.CategoryID == 5);
var query = from p in ctx.Products
Where p.CategoryID == 5
select p;
----- Deferred Execution
var query = from p in ctx.Products where p.CategoryID == 5 || p.CategoryID == 9 select p;
var categoryQuery = from c in query where c.CategoryID == 5 select c;
=> There will have only one query statement for both of LINQ to Entity above.
=> Entity framework valuate the last expression which is enumerated by LINQ and it will turn it back to SQL statement.
=> Entity framework will take LINQ expressions and past it to SQL. (easy for group and join)
----- View and Store Procedure
Right click on EDM diagram -> Update Model from Database

Store procedure: "Add Function Import" -> Select returns & customize Column -> Create New Complex Type -> Get Column Information -> Create New Complex Type
[ In example, they have sample view which has the same return as store procedure] so they select "Entities" as return result
var query = from c in ctx.CustomerSales()
select c;

----- Lazy and Eager loading
[Navigation Properties] Orders
// ========= Lazy Loading
from c in ctx.Customers
select c;

foreach
item.Orders.Count;
// ========= Eager Loading
from c in ctx.Customers.Include("Orders")
select c;

foreach
item.Orders.Count;
----- Custom Mapping
Right click on table -> table mapping // it'll map fields on entity table to any sources we want
-> Create field
Scalar Property
Navigation Property
Complex Property
Association
Inheritance
Function Import
-> Change type and Getter|Setter in property to be private or public
-> Right click on Table -> Table Mapping -> -> Select "Sales By Customer"
[ Mapping Violation cos two object mapped to the same view "Sales By Customer"] Just go to mapping and remove View

((41:29))
----- Optimizing Query Call
[Coalition = when one table depends on another table by some fields]
[Navigation property are IQueryable, so that we can use LINQ to execute this Navigation property]

var customers = from c in ctx.Customers
select new {
customerID = c.CustomerID,
orderTotal = c.Orders.Sum( x => x.Order_Details.Sum( z => z.UnitPrice))
} // it has a little problem with "NULL" value. To solve it, we should join Customer and Orders

var customers = from c in ctx.Customers
join o in ctx.Orders on c.CustomerID == o.CustomerID
select new {
customerID = c.CustomerID,
orderTotal = o.Order_Details.Sum( z => z.UnitPrice))
} //

var query = from o in ctx.Orders
join od in ctx.Order_Details on o.OrderID equals od.OrderID
group od by o.CustomerID into grouping
select new {
CustomerID = grouping.Key,
OrderTotal = grouping.Sum(x=>x.UnitPrice)
};

var query = from o in ctx.Orders
join od in ctx.Order_Details on o.OrderID equals od.OrderID
group od by o.CustomerID into grouping
select grouping; // bad

September 04, 2011

MS SQL Server Query Tracking Tool: AnjLab Sql Profiler

It's similar to Entity FrameworkProfiler but it particularly listens to the specific database in MS SQL Server. It will tracking all queries accessing to the database.
New Trace -> Create Connection to Database -> Events: Check All for "SQLStmtStarting" -> Filter: Select DatabaseID "Equal to 10(Northwind)" -> Run



[Free Opensource]
<Reference>

September 03, 2011

IDE for LINQ: LINGPad

I use this IDE to practice LINQ. It has enough features for me to learn LINQ such as C# Expression, C# Statement which I can declare many variables, C# Program which allows me to create classes and methods and it also can connect to data in MS SQL Server, XML, WCF and Entity Framework (Awesome!). Moreover, I can write VB code, SQL statement, and F# expression or program as well. It also has documentation of using LINQ. It's a simple but powerful tool to me, so I don't know what else is better than this!
[Free trial]
< Download it >

LINQ examples

from num in numbers
where num < 5
select num

(from ci in contactList
where ci.ID == id
select ci).FirstOrDefault();

from student in app.students
where student.ID > 111
select student;

from student in app.students
where student.ID > 111
select student.Last;

from student in students
group student by student.Last[0];

from student in students
group student by student.Last[0] into g
orderby g.Key
select g;

from student in students
group student by student.Scores.Average() >= 80;

from student in students
let avg = (int)student.Scores.Average()
group student by (avg == 0? 0: avg / 10) into g
orderby g.Key
select g;

from studentin students
orderby student.Last, student.First
select student;

from category in categories
join prod in products on category.ID equals prod.CategoryID
select new { ProductName = prod.Name, Category = category.Name};

from category in categories
join prod in products on category.ID equals prod.CategoryID into prodGroup
select new { CategoryName = Category.Name, Products = prodGroup};

MS SQL Server - Save (Not Permitted) dialog box

The Save (Not Permitted) dialog box warns you that saving changes is not permitted because the changes you have made require the listed tables to be dropped and re-created.

The following actions might require a table to be re-created:

- Adding a new column to the middle of the table
- Dropping a column
- Changing column nullability
- Changing the order of the columns
- Changing the data type of a column

To change this option, on the Tools menu, click Options, expand Designers, and then click Table and Database Designers. Select or clear the Prevent saving changes that require the table to be re-created check box.

September 02, 2011

LINQ Operators

- from "range var" [As type] in IEnumerable[]
- where "bool expr"| Func
- select "rang var" | "var member" | anonymouse var
- [group ...|join....|select ...] into variable
- orderby var [ascending|descending][, variable...]
- join var in IEnumerable[] on var equals var
- let "range variable" = expression

- Projection Operators
numbers.Select( (num, index) => new { Num = num, InPlace = (num ==index)});

from a in numberA
from b in numberB
where a < b
select new {a , b};

from c in customers
where c.Region == "WA"
from o in c.Orders
where o.OrderDate >= new DateTime(1997, 1, 1)
select new {c.CustomerID, o.OrderID};

customers.SelectMany( (cust, custIndex) => cust.Orders.Select( o => "Customer #" + (custIndex +

1) + " has an order with OrderID "+ o.OrderID));
- Partition Operators
numbers.Take(3);
numbers.Skip(3);
numbers.TakeWhile( n => n < 6);
numbers.SkipWhile( n => n < 6);
- Ordering Operators
orderby field1, field2 descending/ascending
OrderBy(a => a).ThenBy(a => a.Length)
OrderBy(a => a).ThenByDescending(a => a.Length)
- Grouping Operators
group n by n % 5 into g
group w by w[0] into g
select new { key, value};

from cus in customers
select new { cus.CompanyName, YearGroups = from o in cus.Orders
group o by o.OrderDate.Year into yg
select new { Year = yg.Key,
MonthGroups = from o in yg
group o by o.OrderDate.Month into mg
select new { Month = mg.Key, Orders = mg}
}
}

words.GroupBy(w => w.Trim(), v => v.ToUpper());
- Set Operators
numbers.Distinct();
(from ....... select ........).Distinct();

var numUnion = num1.Union(num2).OrderBy( a => a);
var numIntersect = num1.Intersect(num2);
IEnumberable numExcept = num1.Except(num2);
- Conversion Operators
ToArray();
ToList();

var scoreRecords = new[]{ new {Name = "Alice", Score = 50}, new {Name = "Bob", Score = 40}, new

{Name = "Cathy", Score = 45}};
var scoreRecordsDict = scoreRecords.ToDictionary (sr => sr.Name);
numbers.OfType(); // get only double values in array of object
- Element Operators
(from ... select ...).First();
strings.First( s => s[0] == 'o');
numbers.FirstOrDefault(); // if no value, return default
products.FirstOrDefault( p => p.ProductID == 789) // return null if not found
strings.ElementAt(1);
- Generation Operators
from n in Enumerable.Range(100, 50) // from 100 to 149
select new { Number = n, OddEven = n%2 ==1 ? "Odd":"Even"}

Enumerable.Repeat(7, 10);
- Quantifiers Operators
Array.Any ( w => w.Contains("ei"));

group p by p.Category into g
where g.Any(p => p.UnitsInStock ==0)

numbers.All( n => n % 2 == 1); // all number are Odd

group p by p.Category into g
where g.All( p => p.UnitsInStock > 0) // category that has all products in stock
- Aggregate Operators
numbers.Distinct().Count();
numbers.Count(n => n % 2 == 1);

select new ( c.CustomerID, orderCount = c.Orders.Count());

group p by p.Category into g
select new { g.Key, ProductCount = g.Count()};

numbers.Sum();
strings.Sum( w => w.Length);

int[] numbersA = {0, 2, 4, 5, 6};
int[] numbersB = {1, 3, 5, 7, 8};
var numSum = numbersA.Select((a, index)=> new {a = a, value=numbersA[index] * numbersB

[index]}).Sum(a => a.value);

group p by p.Category into g
select new { g.Key, totalUnitsInStock = g.Sum( p => p.UnitsInStock)};

numbers.Min();
words.Min(w => w.Length);

group p by p.Category into g
select new {g.Key, CheapestPrice = g.Min( p => p.UnitPrice)};

group p by p.Category into g
let minPrice = g.Min( p => p.UnitsPrice)
select new { g.Key, CheapestPrice = g.Where( p => p.UnitsPrice == minPrice)}; // get cheapest

product in each category

numbers.Max();
words.Max( w => w.Length);

numbers.Average();
words.Average( w => w.Length);

double product = doubles.Aggregate((running, next) => running * next);
- Miscellaneous Operators
numbersA.Concat(numbersB); // connect two array together
wordsA.SequenceEqual(wordsB); // all element are match even with index order

- Query Execution
int i = 0;
var q = from n in numbers select ++i; // i will increase while foreach
var q = (from n in numbers select ++i).ToList(); // Execute immediately
Query Reuse // we will get different result once we change the source
- Join Operators
from c in customer
join p in product on c.customerID equals p.customerID
select {c.customerName, p.ProductName};

from h in Tbl_Hotels
join r in Tbl_Rooms on h.HotelNo equals r.HotelNo into gs
from g in gs // Cross join
select new {h.HotelName, g.RoomNo};

from h in Tbl_Hotels
join r in Tbl_Rooms on h.HotelNo equals r.HotelNo into gs
from g in gs.DefaultIfEmpty() // left outer join
select new {h.HotelName, g.RoomNo};

September 01, 2011

C# - IComparer of String (case insensitive)


void Main()
{
string[] words = { "aPPLE", "AbAcUs", "bRaNcH", "BlUeBeRrY", "ClOvEr", "cHeRry"};
//var sortedWords = words.OrderBy( a => a, new CaseInsensitiveComparer());
var sortedWords = words.OrderByDescending(a => a, new CaseInsensitiveComparer());

foreach(var sw in sortedWords)
Console.WriteLine(sw);
}
//-----------------------------------
class CaseInsensitiveComparer : IComparer<string>{
public int Compare(string x, string y){
return string.Compare(x, y, StringComparison.OrdinalIgnoreCase);
}
}