Musings

A random collection

Archive for November 2010

.NET: WCF Service Logging

To enable trace logging in WCF service do the following:

  1. Hint: May use C:\Program Files\Microsoft SDKs\Windows\v6.0,v6.0A,v7.0\Bin\svcconfigeditor.exe to edit Config file
  2. Define Trace Sources in Config File
    1. System.ServiceModel – Logs all stages of WCF processing, whenever configuration is read, a message is processed in transport, security processing, a message is dispatched in user code, and so on
    2. System.ServiceModel.MessageLogging – Logs all messages that flow through the system
    3. System.IdentityModel
    4. System.ServiceModel.Activation
    5. System.IO.Log – Logging for the .NET Framework interface to the Common Log File System
    6. System.Runtime.Serialization – Logs when objects are read or written
  3. Define Trace Listeners to Consume Traces for each source, example: System.Diagnostics.XmlWriterTraceListener . You can have shared listeners for all/multiple sources, and you can have more than one listeners for each source.
  4. Configure Activity Tracing and Propagation
  5. Example:
    <configuration>
      <system.serviceModel>
        <diagnostics performanceCounters="All">
            <messageLogging maxMessagesToLog="30000" logEntireMessage="true" logMessagesAtServiceLevel="true" logMalformedMessages="true" logMessagesAtTransportLevel="true">
            </messageLogging>
        </diagnostics>
      </system.serviceModel>
    
      <system.diagnostics>
        <sources>
          <source name="System.ServiceModel" switchValue="Verbose, ActivityTracing">
            <listeners>
              <add name="xml"/>
            </listeners>
          </source>
          <source name="System.ServiceModel.MessageLogging" switchValue="Verbose">
            <listeners>
              <add name="xml"/>
            </listeners>
          </source>
        </sources>
        <sharedListeners>
          <add name="xml" type="System.Diagnostics.XmlWriterTraceListener" initializeData="e2eTraceTest.e2e"/>
        </sharedListeners>
        <trace autoflush="true"/>
      </system.diagnostics>
    
      <system.diagnostics>
        <sources>
          <source name="System.ServiceModel" 
                      switchValue="Information, ActivityTracing"
                      propagateActivity="true">
            <listeners>
              <add name="traceListener" 
                      type="System.Diagnostics.XmlWriterTraceListener" 
                      initializeData= "c:\log\Traces.svclog" />
            </listeners>
          </source>
        </sources>
      </system.diagnostics>
    </configuration>
    
  6. C:\Program Files\Microsoft SDKs\Windows\v7.0A\bin\svctraceviewer.exe

Your own logging in WCF

  1. Use System.Diagnostics.TraceSource to create a trace source for your application/module
  2. Start logging with traceSource.TraceEvent() calls
  3. Enable logging for your module in config file
  4. Let us see an example:
    private System.Diagnostics.TraceSource ts;
    ...
    ts = new System.Diagnostics.TraceSource("MyOwnServiceTraceSource");
    ...
    ts.TraceEvent(System.Diagnostics.TraceEventType.Information, 1, "Voila!");
    	
  5. Example of config file changes:
    <configuration>
        <system.diagnostics>
            <sources>
              <source name="MyOwnServiceTraceSource" switchValue="Verbose, ActivityTracing">
                <listeners>
                  <add name="xml"/>
                </listeners>
              </source>
            </sources>
            <sharedListeners>
                <add name="xml" type="System.Diagnostics.XmlWriterTraceListener" initializeData="myownlogs.xml"/>
            </sharedListeners>
            <trace autoflush="true"/>
        </system.diagnostics>
    </configuration>
    	

Written by curious

November 30, 2010 at 10:56 am

Posted in dotNET

MATH: Latex Cheatsheet

Editors for Latex documents:

  1. Lyx
  2. Texlipse – a plugin for Eclipse
  3. TikzEdt

The cheatsheet

  1. General Purpose template
        \documentclass[12pt]{article}
        \usepackage{amsmath,amssymb,amsfonts}
        \def\E{\mathbb{E}}
        \def\bS{\mathbb{S}}
        \def\R{\mathbb{R}}
    
        \pagestyle{plain}
    
        \begin{document}
        \end{document}
        
  2. My favorite template for notes (with 2 columns)
    \documentclass[8pt,twocolumn]{extarticle}
        \usepackage[top=0.25in,bottom=.5in,left=0.3in,right=0.3in]{geometry}
    
        \usepackage{amsmath, amssymb, amsthm}
        \usepackage{framed}
        \usepackage{color,soul}
        \usepackage{verbatim}
        \usepackage{multirow}
    
        \usepackage{picture}
    
        \usepackage{tikz}
        \usetikzlibrary{shapes,arrows,snakes,backgrounds}
    
        \usepackage{bbm} % for indicator
    
        \usepackage{listings}
        \lstset{language=Matlab,breaklines=true}
    
        \setlength{\columnseprule}{.2pt} % will put a line between columns
        \setlength{\parindent}{0in}
        %\setlength{\parskip}{3mm}
    
        \newtheorem*{thm}{Theorem}
        \newtheorem*{cor}{Corollary}
        \newcommand{\bm}[1]{\boldsymbol{#1}}
    
        \newcommand{\Var}{\text{Var}}
        \newcommand{\Cov}{\text{Cov}}
        \newcommand{\E}{\mathbb{E}}
    
        \usepackage{units, datetime, fancyhdr, lastpage}
        \pagestyle{fancy}
        \fancyhf{}
        \cfoot{\thepage\ of \pageref{LastPage}}
        \rfoot{\mmddyyyydate\today\ \currenttime}
    \begin{document}
    \end{document}
    
  3. A Template for Beamer Slides (Reference: Beamer User Guide at CTAN)
        \documentclass[10pt]{beamer}
    
        \title{TODO: My Slides}
        \subtitle{TODO: Sub-title for slides}
        \author[T. Author]{TODO Author}
        \date{January 1, 2012} % TODO
        \begin{document}
    
        %----------- titlepage ----------------------------------------------%
        \begin{frame}[plain]
          \titlepage
        \end{frame}
        
        %----------- slide --------------------------------------------------%
        \begin{frame}
          \frametitle{TODO: Title of Slide}
    
          \begin{itemize}
            \item Itemized list entry
          \end{itemize}
    
          % Useful stuff
          % \pause
          % \medskip
          % \bigskip
          % \includegraphics[height=25mm]{something.pdf}
          % \begin{columns}
          %   \begin{column}{0.3\textwidth}
          %     bla bla
          %   \end{column}
          %   \begin{column}{0.3\textwidth}
          %     bla bla
          %   \end{column}
          % \end{columns}
    
          % \begin{displaybox}{60mm} \end{displaybox}
          % \[ \]
    
        \end{frame}
    
        \end{document}
        
  4. Options for drawing in Latex: pstricks, pgf/tikz, xypic
    • pgf/tikz — simpler than pstricks. Here is an example
              \documentclass{article}
              \usepackage{tikz}
              \begin{document}
      
              \begin{tikzpicture}[scale=1.5]
                  % Draw axes
                  \draw [<->,thick] (0,2) node (yaxis) [above] {$y$}
                      |- (3,0) node (xaxis) [right] {$x$};
                  % Draw two intersecting lines
                  \draw (0,0) coordinate (a_1) -- (2,1.8) coordinate (a_2);
                  \draw (0,1.5) coordinate (b_1) -- (2.5,0) coordinate (b_2);
                  % Calculate the intersection of the lines a_1 -- a_2 and b_1 -- b_2
                  % and store the coordinate in c.
                  \coordinate (c) at (intersection of a_1--a_2 and b_1--b_2);
                  % Draw lines indicating intersection with y and x axis. Here we use
                  % the perpendicular coordinate system
                  \draw[dashed] (yaxis |- c) node[left] {$y'$}
                      -| (xaxis -| c) node[below] {$x'$};
                  % Draw a dot to indicate intersection point
                  \fill[red] (c) circle (2pt);
              \end{tikzpicture}
              \end{document}
              

      Reference: Manual, Examples, Resources, Minimal

      Some useful code:

      • Scaling a picture
                    \begin{tikzpicture}[scale=0.5] \end{tikzpicture}
        
                    \begin{tikzpicture}[xscale=2.5,yscale=0.5] \end{tikzpicture}
                    
      • Draw a line from (x0,y0) to (x1,y1):
                    \draw (x0,y0) -- (x1,y1);
                    

        A path of straight lines

                    \draw (x0,y0) -- (x1,y1) -- (x2,y2) -- (x3,y3);
                    

        Arrows

                    \draw[->] (x0,y0) -- (x1,y1);
                    \draw[<-] (x0,y0) -- (x1,y1);
                    \draw[|->] (x0,y0) -- (x1,y1);
                    

        Thicker lines: ultra thin, very thin, thin, semithick, thick, very think, ultra thick

                    \draw[thick] (x0,y0) -- (x1,y1);
                    \draw[line width=3] (x0,y0) -- (x1,y1); % 3pt wide
                    

        Dashes and dots: dashed, dotted, thinly dotted

        Colors: red, green, blue, cyan, magenta, yellow, black, gray, darkgray, lightgray, brown, lime, olive, orange, pink, purple, teal, violet, white

      • Draw a line from (x0,y0) to point with polar coordinates (a1:r1) a1 = angle, r1 = radius
                    \draw[color=green] (x0,y0) -- (a1:r1);
                    
      • Draw an arc with center at (x0,y0) starting at startAngle=a1, ending at angle, e1 and radius=r1
                    \draw (x0,y0) arc [radius=r1, start angle=a1, end angle=e1];
        
                    \draw (x0,y0) arc (a1:e1:r1);
                    
      • Draw a green rectangle between coordinates (x0,y0) to (x1,y1):
                    \draw[color=green] (x0,y0) rectangle (x1,y1);
                    
      • Draw a filled ellipse with center at (x0,y0) and (r1, r2):
                    \draw[fill=color!shade] (x0,y0) ellipse (r1 and r2);
                    

        Draw a dotted circle with center at (x0,y0) and radius r0:

                    \draw[style=dashed] (x0,y0) circle (r1);
                    
      • Draw a bezier curve
                    \draw (x0,y0) .. controls (px1,py1) and (px2,py2) .. (x1,y1);
                    
      • Draw a grid
                    \draw[help lines] (0,0) grid (3,2);
                    
      • Draw (x,y) axis
                    \draw[<->] (0,10.1) -- (0,0) -- (10.1,0);
                    \draw[snake=ticks,segment length=1cm] (0,10) -- (0,0) -- (10,0);
        
                    \foreach \x/\xtext in {-1/-0.1,0/0.0,1/0.1,2/0.2,3/0.3}
                        \draw[shift={(\x,0)},thick,color=gray!40,dashed] (0,2.5) -- (0,0) node[color=black,below] {\scriptsize $\xtext$};
                    \foreach \y/\ytext in {-1/-0.1,0/0.0,1/0.1,2/0.2,3/0.3}
                        \draw[shift={(0,\y)},thick,color=gray!40,dashed] (2.5,0) -- (0,0) node[color=black,left] {\scriptsize $\ytext$};
        
                    \foreach \x in {0,1,2,3,4,5}
                        \draw (\x,3) -- (\x,-3);
        
                    \draw[help lines] (0,0) grid (8,5);
                    \draw[->] (0,0) -- (8,0) node[right] {x};
                    \draw[->] (0,0) -- (0,5) node[above] {y};
                    \foreach \x in {0,...,7}
                        \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\x};
                    \foreach \y in {0,...,4}
                        \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\y};
                    
      • Aliases
                    \draw = \path[draw]
                    \fill = \path[fill]
                    \clip = \path[clip]
                    \filldraw = \path[fill,draw]
                    \shade = \path[shade]
                    
      • Draw a curve from (x0,y) to (x1,y1) leaves at angle a1, arrives at an angle e1
                    \draw (x0,y0) to [out=a1,in=e1] (x1,y1);
        
                    \draw (x0,y0) to [out=a1,in=e1] (x1,y1)
                                  to [out=a2,in=e2] (x2,y2)
                                  to [out=a3,in=e3] (x3,y3)
                         ;
                    

        Plot from (x0:x1) curve f(x)=x^3+2x

                    \draw [domain=x0:x1] plot(\x, {\x*\x*\x+2*\x});
        
                    \draw [domain=x0:x1] plot(\x, {sin(\x r) * ln(\x+1)/2 + exp(2*pi)});
                    

        other functions: factorial, sqrt, pow, exp, ln, log10, log2, abs, mod, round, floor, sin(degrees), sin(radian r), cos, tan min, max, rnd, e, pi

      • A closed figure
                    \path[draw] (x0,y0) -- (x1,y1) -- (x2,y2) -- cycle;
        
                    \path[draw] (x0,y0) -- (x1,y1) -- (x2,y2) -- (x0,y);
                    
      • Text at some position
                    \node at (x0,y0) {text};
        
                    \node (label1) at (x0,y0) {text};
                    \node (label2) at (x1,y1) {text};
                    \draw (label1) -- (label2);
                    
    • xypic — simplest way to draw
          \documentclass{article}
          \usepackage[all]{xy}
          \begin{document}
      
          \xymatrix{
          A \ar@<1ex>[dr]^a_{.} \\
          & B \ar@<1ex>[ul]^b \ar@<1ex>[r]^c
          & C \ar@<1ex>[l]^d_{.}
          }
          \end{document}
          
    • pstricks — run the latex file through ps2pdf. Example:
          $> cat f1.tex
            \documentclass{article}
            \usepackage{pstricks}
            \begin{document}
            \begin{figure}
            \psset{gridcolor=green,subgridcolor=yellow}
            \begin{pspicture}(4,5)
            \psgrid
            \psframe[linecolor=blue,
            fillcolor=red,
            fillstyle=solid](0.7,2)(3.3,3)
            \rput(2,2.5){First Example}
            \end{pspicture}
            \end{figure}
            \end{document}
          $> ps2pdf f1.tex
          
    • Picture environment
          \usepackage{picture}
      
          % begin{picture}(xDim,yDim)(leftBottomCoordX,leftBottomCoordY)
          \begin{picture}(110,110)(-10,-10)
            \put(0,0){\vector(1,0){100}}  % x-axis
            \put(0,0){\vector(0,1){100}}  % y-axis
            \multiput(10,-2)(10,0){9}{\line(0,1){2}} % markers (x)
            \multiput(-2,10)(0,10){9}{\line(1,0){2}} % markers (y)
      
            \put(0,-5){\makebox(0,0){0}}   % origin
            \put(100,-5){\makebox(0,0){x}}  % label x-axis
            \put(-10,100){\makebox(0,0){y}} % label y-axis
      
            \qbezier(55,0)(0,0)(1,80)      % draw a curve between (55,0) and (1,80)
      
            \multiput(0,30)(2,0){25}{\line(1,0){1}} % draw a horizontal dotted line
            \multiput(50,0)(2,0){15}{\line(0,1){1}} % draw a vertical dotted line
          \end{picture}
          
    • Flowcharting
          \documentclass{article}
      
          \usepackage[latin1]{inputenc}
          \usepackage{tikz}
          \usetikzlibrary{shapes,arrows}
          \begin{document}
          \pagestyle{empty}
          % Define block styles
          \tikzstyle{decision} = [diamond, draw, fill=blue!20,
              text width=4.5em, text badly centered, node distance=2.5cm, inner sep=0pt]
          \tikzstyle{block} = [rectangle, draw, fill=blue!20,
              text width=5em, text centered, rounded corners, minimum height=4em]
          \tikzstyle{line} = [draw, very thick, color=black!50, -latex']
          \tikzstyle{cloud} = [draw, ellipse,fill=red!20, node distance=2.5cm,
              minimum height=2em]
          \tikzstyle{decision answer}=[near start,color=black]
      
          \begin{tikzpicture}[scale=2, node distance = 2cm, auto]
              % Place nodes
              \node [block] (init) {initialize model};
              \node [cloud, left of=init] (expert) {expert};
              \node [cloud, right of=init] (system) {system};
              \node [block, below of=init] (identify) {identify candidate models};
              \node [block, below of=identify] (evaluate) {evaluate candidate models};
              \node [block, left of=evaluate, node distance=2.5cm] (update) {update model};
              \node [decision, below of=evaluate] (decide) {is best candidate better?};
              \node [block, below of=decide, node distance=2.5cm] (stop) {stop};
              % Draw edges
              \path [line] (init) -- (identify);
              \path [line] (identify) -- (evaluate);
              \path [line] (evaluate) -- (decide);
              \path [line] (decide) -| node [decision answer] {yes} (update);
              \path [line] (update) |- (identify);
              \path [line] (decide) -- node [decision answer] {no}(stop);
              \path [line,dashed] (expert) -- (init);
              \path [line,dashed] (system) -- (init);
              \path [line,dashed] (system) |- (evaluate);
          \end{tikzpicture}
          \end{document}
          
  5. Adding pdf pages to your document

    As an image

    \usepackage{graphicx}
    
    \begin{figure*}[h]
    \centering
    \includegraphics[width=1.0\textwidth]{pg1.pdf}
    \caption{Test}
    \end{figure*}
        

    Selective pages

    \usepackage{pdfpages}
    
    \includepdf[pages={1}]{pg1.pdf} % page 1
    \includepdf[pages={3-last}]{pg1.pdf} % all pages
    \includepdf[pages={3,{},5,7}]{pg1.pdf} % page 3, empty page, 5, 7
    \includepdf[pages=-]{pg1.pdf} % all pages
        
  6. Def equal:
    A \stackrel{\rm def}{=} B
  7. Binomial coefficient
        \binom{n}{r}
        or
        \newcommand{\bc}[2]{\genfrac{(}{)}{0pt}{}{#1}{#2}}
        ...
        \bc{n}{r}
    
        # equivalently (gives a warning)
        {n \choose r}
    
        \dbinom{n}{r}
        
  8. Two columns:
    1. Use: \documentclass[11pt,twocolumn]{article}
      Distance between columns: \setlength{\columnsep}{distance}
      A line at the bottom of column: \setlength{\columnseprule}{thickness}
    2. Use:
                  \usepackage{multicol}
                  \begin{multicols}{2}
                  ...
                  \end{multicols}
                  
  9. Adjust margins
        \usepackage[top=0.5in,bottom=0.5in,left=0.5in,right=0.5in]{geometry}
        
  10. Putting today’s date in your document. Just use \today.
    To get current date+time, use datetime package. \currenttime.

            \usepackage{datetime}
            ...
            \begin{document}
            Printed: \today\ at \currenttime
    
            Printed: {\tiny \ddmmyyyydate\today\ at \currenttime}
            
  11. Indicator function:
        \usepackage{mathbbm}
        ...
        \mathbbm{1}_A
        
  12. Need page numbers in the style “1 of 10”
        \usepackage{fancyhdr}
        \pagestyle{fancy}
        \lfoot{Left Side of footer}
        \cfoot{\thepage\ of \pageref{LastPage}}
        \rfoot{Right Side of footer}
        ...
        \begin{document}
        ...
        
  13. Underline: \underline{}, Underbrace: \underbrace{}
  14. Overline: \overline{}, Overbrace: \overbrace{}
  15. Emphasize: \emph{}
  16. Strike out: \sout{}, needs package ulem. say \usepackage[normalem]{ulem}

Written by curious

November 11, 2010 at 10:27 am

Posted in maths

PROG: Comparison of data types

Type Bit Size Size
char at least 8 bits one byte
short at least 16 bits at least as big as a char
int at least 16 bits at least as big as a short
long at least 32 bits at least as big as int
  1. signed integer types
    signed char        // 8-bits
    signed short int     // 16-bits
    signed int             // 16 or 32 bits
    signed long int      // 32 bits
    signed long long int // 64 bits
    
  2. unsigned integer types
    unsigned char
    unsigned short int
    unsigned int
    unsigned long int
    unsigned long long int
    
  3. floating point types
    float
    double
    long double
    
  4. In addition to signed, unsigned integer types above, the following may also be used as integral values
    bool
    char
    wchar_t
    

Boost types

#include <boost/cstdint.hpp>

boost::int8_t   // signed char
boost::int16_t  // short
boost::int32_t  // long or int
boost::int64_t  // long long or long

boost::uint8_t   // unsigned char
boost::uint16_t  // unsigned short
boost::uint32_t  // unsigned long or unsigned int
boost::uint64_t  // unsigned long long or unsigned long

Note:

  1. char == signed char / unsigned char
  2. short == short int
  3. long == long int
  4. unsigned == unsigned int
  5. signed == signed int

Written by curious

November 10, 2010 at 10:38 am

Posted in C++

PROG: C++ Numeric Limits Options

In C++ there are multiple ways we can specify bounds values (MAX, MIN) for numeric types.

  1. Old C way (#include “limits.h”)
    Name
    CHAR_BIT
    SCHAR_MIN,MAX
    UCHAR_MAX
    CHAR_MIN,MAX
    SHRT_MIN,MAX
    USHRT_MAX
    INT_MIN,MAX
    UINT_MAX
    LONG_MIN,MAX
    ULONG_MAX
  2. STL way
    #include <limits>
    std::numeric_limits<int>::min()
    std::numeric_limits<int>::max()
    std::numeric_limits<int>::is_signed()
    std::numeric_limits<int>::digits() // number of bits
    std::numeric_limits<int>::has_infinity()
    std::numeric_limits<int>::infinity()
    
  3. Boost way
    #include <boost/numeric/conversion/bounds.hpp>
    #include <boost/limits.hpp>
    
    boost::numeric::bounds<int>::highest()
    boost::numeric::bounds<int>::lowest()  // min finite value numeric_limits<T>::min() or -numeric_limits<T>::max()
    boost::numeric::bounds<int>::smallest() // smallest denormalized value for floats, 0 for integral types
    

A safe numeric conversion/cast in Boost

Use it for numeric type to numeric type conversions

Will throw exceptions when it is unsafe to convert

  1. Conversions from an integral type with a wider range than the target integral type
  2. Conversions from unsigned to signed (and vice versa) integral types
  3. Conversions from floating point types to integral types
#include <boost/numeric/conversion/cast.hpp> 

doubled = boost::numeric_cast<double>(intval);

// exceptions
bad_numeric_cast
negative_overflow
positive_overflow

Lexical Cast in Boost

For conversion from non-numeric types

#include <boost/lexical_cast.hpp>

// may throw bad_lexical_cast exception
boost::lexical_cast<short>(stringval);
boost::lexical_cast<std::string>(intval);

Written by curious

November 10, 2010 at 9:54 am

Posted in C++

Protected: QUANT: Trading Software

This content is password protected. To view it please enter your password below:

Written by curious

November 10, 2010 at 9:50 am

Posted in quant-finance

ALGO: Dynamic Programming – example problems

  1. Coin Denominations: Given a set of coins of denominations (V1, V2, …, VN). Find the minimum number of coins that add up to sum S.
    #include <vector>
    #include <iostream>
    #include <limits>
    #include <assert.h>
    
    using namespace std;
    
    unsigned int
    find_min_coins(unsigned int S, const vector<unsigned int>& coins);
    
    unsigned int
    find_min_coins(unsigned int S, const vector<unsigned int>& coins)
    {
        vector<unsigned int> min_coins(S+1, std::numeric_limits<unsigned int>::max());
        min_coins[0] = 0;
        for (unsigned int s = 1; s <= S; ++s)
        {
            for (unsigned int k = 0; k < coins.size() && coins[k] <= s; ++k)
            {
                if (min_coins[s] > min_coins[s - coins[k]]+1)
                    min_coins[s] = min_coins[s - coins[k]]+1;
            }
        }
        return min_coins[S];
    }
    
    int
    main(int argc, const char* argv[])
    {
        unsigned int S1 = 11;
        unsigned int d1[] = { 1, 3, 5 };
        unsigned int count1 =
            find_min_coins(S1, vector<unsigned int>(d1, d1+sizeof(d1)/sizeof(d1[0])));
    
        assert(count1 == 3);
        cout << "Min coins for " << S1 << " is " << count1 << endl;
    
        unsigned int S2=31;
        unsigned int d2[] = { 1, 5, 10, 25 };
        unsigned int count2 =
            find_min_coins(S2, vector<unsigned int>(d2, d2+sizeof(d2)/sizeof(d2[0])));
        assert(count2 == 3);
        cout << "Min coins for " << S2 << " is " << count2 << endl;
    
        return 0;
    }
    
  2. Given a sequence of numbers (A1, A2, …, AN). Find the longest non-decreasing subsequence.

    A humble beginning with O(n2)

    static int
    longest_increasing_subsequence(int[] A)
    {
        int[] L = new int[A.Length];
        L[0] = 1;
        for (int i = 1; i < A.Length; ++i)
        {
            // INVARIANT: for all k < i, L[k] is the length of the longest increasing subsequence ending in A[k]
    
            L[i] = 1;    // initialize with sequence of only one element, A[i]
    
            // find longest subsequence that ends in A[i]
            for (int j = i - 1; j >= 0; --j)
            {
                if (A[i] >= A[j] && L[i] < L[j]+1)
                {
                    // Is (longest_subsequence(A[1:j]) + A[i]) a valid non-decreasing subsequence?
                    // new length max (L[i], L[j]+1)
                    L[i] = L[j] + 1;
                }
            }
        }
        return L.Max();
    }
    
    static void Main(string[] args)
    {
        int[] A = new int[] {
            2, 3, 1, 7, 6, 8, 4, 5, 0, 9, -1, -2, -3
        };
    
        Console.WriteLine( longest_increasing_subsequence(A) );
    }
    

    http://polylogblog.wordpress.com/

  3. Given a undirected graph G (V, E), let us say |V| = N (number of vertices in the graph is N). Find the shortest path from vertex V1 to VN (if a path exists).
  4. Longest Alternating Increasing, Decreasing Sequence: Given a sequence of integers, Find a longest sub-sequence such that all the elements in the subsequence are in an alternating increasing and decreasing pattern. All sequences of 1 and 2 items are always alternating sequence. So {1, -1, 5, 3, 7, 4, 6} is a sequence of alternating increasing and decreasing integers.

    Example: Given {1, 10, -2, 9, 11, 7, 6, 99, 11}, it’s longest alternating subsequence is of length 8, say {1, 10, -2, 9, 7, 6, 99, 11} or {1, 10, -2, 11, 7, 6, 99, 11}

  5. We are given two strings: string S of length n, and string T of length m. Our goal is to produce their longest common subsequence: the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

    Example:

      S = ABAZDC
      T = BACBAD

    In this case, the LCS has length 4 and is the string ABAD

  6. In the knapsack problem we are given a set of n items, where each item i is
    specified by a size si and a value vi. We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

Reference: http://people.csail.mit.edu/bdean/6.046/dp/
Reference: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
Reference: http://www.algorithmist.com/index.php/Dynamic_Programming
Reference: http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf

Written by curious

November 8, 2010 at 4:48 pm

Posted in algorithms

TECH: Some tools

VUE
Visual Understanding Environment (VUE) is an Open Source project based at Tufts University. The VUE project is focused on creating flexible tools for managing and integrating digital resources in support of teaching, learning and research. VUE provides a flexible visual environment for structuring, presenting, and sharing digital information. Website
Zotero
Zotero is a free, easy-to-use tool to help you collect, organize, cite, and share your research sources. It lives right where you do your work—in the web browser itself. Website
Free Plane
Freeplane is a powerful and free software for building the mind maps. Website
yED
yEd is a powerful diagram editor that can be used to quickly and effectively generate high-quality drawings of diagrams. Website, Launch

Find free alternative software website

Written by curious

November 1, 2010 at 8:51 am

Posted in tech-tips