Musings

A random collection

Archive for June 2011

PROG: Divide and Conquer

MIT: Intro to Algos – lect 3

Technique

  1. Divide
  2. Conquer
  3. Combine

Examples:

  1. Merge Sort: a) split array into 2 parts of size N/2, b) sort each part c) Merge the sorted parts
  2. Binary Search: a) split array in the middle, compare the middle element b) search in the relevant part (reject the other part) c) No combine part
  3. Integer Raised to the Power N: a) Split problem into smaller size: (N/2) b) find y=x^{(N/2)} c) multiply y \times y (a little tweak when N is odd)
  4. Fibonacci Numbers:
      f(n) = \begin{cases} f(n-1)+f(n-2) & n > 1 \\ 1 & \text{when } n = 1 \\ 0 & \text{when } n = 0 \end{cases}

    Aha moment:

      \begin{pmatrix} f(n+1) & f(n) \\ f(n) & f(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n
  5. Matrix Multiplication (C = A x B) — Strassen’s method
    a) Split matrices to be multiplied (A, B) into smaller box matrices of 2×2
    b) Find terms P1, …, P7
    c) Combine the terms to find C
  6. VLSI Layout: Goal is to layout a binary tree of N nodes onto a circuit board grid using min area possible

Nice notes from the lectures by CatOnMat.net

Advertisements

Written by curious

June 22, 2011 at 9:27 am

Posted in algorithms

PROG: The Lambdas

  1. C#/.NET
  2.   Action lambda = () => { /* some code */ };
      lambda();
    
      Action lambda = _ => { ... }; // is same as
      Action lambda = m => { ... }; // _ is a valid variable name
    
      Action<int> lambda = (i) => { Console.WriteLine(i); };
      lambda(100);
      
  3. C++/boost
  4. C++0x
  5. Java
  6. Python

Written by curious

June 21, 2011 at 8:58 pm

Posted in programming

PROG: TCP/IP Server, Client

Writing a server application

  1. In perl:
    • Create a socket, and bind it to a port
      use Socket;
      use IO::Socket;
      
      $filebits = '';
      OpenServer();
      
      sub OpenServer {
        $server = IO::Socket::INET->new(Listen    => 5,
                                  LocalPort => 3234,
                                  Reuse => 1,
                                  ReuseAddr => 1,
                                  Timeout   => 0,
                                  Proto     => 'tcp');
        die "Could not create socket $!" unless $server;
      
        $server->blocking(0);
        $server_fileno = fileno($server);
        vec($filebits,$server_fileno,1) = 1;
      
        print STDERR "Starting $server_fileno\n";
      }
      
    • Listen for connect from clients
      my $rout;
      while (1)
      {
        select( undef, undef, undef, 1 );
      
        select( $rout = $filebits, undef, undef, undef );
        my $routs = unpack("b*", $rout);
        print STDERR "Select $routs\n";
        my $pos = index( $routs,'1');
        while ( $pos >= 0 ) {
          # process data
          HandleFile( $pos );
          $pos = index( $routs,'1', $pos+1);
        }
      }
      
      sub HandleFile {
        local( $fileno ) = @_;
      
        print STDERR "HandleFile $fileno\n";
        if ( $fileno == $server_fileno ) {
          HandleServer();
        } elsif ( $connections{$fileno} ) {
          HandleClient( $fileno );
        } else {
          print STDERR "Weird fileno $fileno\n";
        }
      }
      
    • Process requests from connected client
      sub HandleServer {
        my $client = $server->accept();
      
        print STDERR "HandleServer\n";
      
        if ( $client ) {
          my $fileno = fileno($client);
          $client->blocking(0);
          $connections{$fileno}{client} = $client;
          $connections{$fileno}{loggedin} = 0;
          vec($filebits,$fileno,1) = 1;
          print $client "Welcome $fileno\r\n";
          SendMessage( "New Client" );
        } else {
          print STDERR "No accept for server, reopen\n";
          CloseServer();
          OpenServer();
        }
      }
      
      sub HandleClient {
        local( $fileno ) = @_;
      
        print STDERR "HandleClient $fileno\n";
        recv( $connections{$fileno}{client}, $receive, 200, 0 );
        if ( $receive ) {
          my $line = $connections{$fileno}{receive};
          $line .= $receive;
          while ( $line =~ s/(.*)\n// ) {
            my $temp = $1;
            $temp =~ tr/\r\n//d;
            SendMessage( $temp );
          }
          $connections{$fileno}{receive} = $line;
        } else {
          print STDERR "Close client $fileno\n";
          vec($filebits,$fileno,1) = 0;
          $connections{$fileno}{client}->close();
          undef $connections{$fileno};
          SendMessage( "Close Client" );
        }
      }
      
      sub SendMessage {
        local( $message ) = @_;
      
        print STDERR "SendMessage $message\n";
        $message .= "\r\n";
      
        foreach $fileno (keys %connections) {
          if ( $connections{$fileno} ) {
            my $client = $connections{$fileno}{client};
            print $client $message;
          }
        }
      }
      
    • Close socket
      sub CloseServer {
        vec($filebits,$server_fileno,1) = 0;
        $server->close();
        undef $server;
      }
      

    Original author

    Complete Code:

    #!/usr/bin/perl
    
    use Socket;
    use IO::Socket;
    
    $filebits = '';
    
    OpenServer();
    
    my $rout;
    while( 1 ) {
      print STDERR "Loop\n";
    
      select( undef, undef, undef, 1 );
    
      select( $rout = $filebits, undef, undef, undef );
      my $routs = unpack("b*", $rout);
      print STDERR "Select $routs\n";
      my $pos = index( $routs,'1');
      while ( $pos >= 0 ) {
        HandleFile( $pos );
        $pos = index( $routs,'1', $pos+1);
      }
    }
    
    sub SendMessage {
      local( $message ) = @_;
    
      print STDERR "SendMessage $message\n";
      $message .= "\r\n";
    
      foreach $fileno (keys %connections) {
        if ( $connections{$fileno} ) {
          my $client = $connections{$fileno}{client};
          print $client $message;
        }
      }
    }
    
    sub HandleFile {
      local( $fileno ) = @_;
    
      print STDERR "HandleFile $fileno\n";
      if ( $fileno == $server_fileno ) {
        HandleServer();
      } elsif ( $connections{$fileno} ) {
        HandleClient( $fileno );
      } else {
        print STDERR "Weird fileno $fileno\n";
      }
    }
    sub HandleServer {
      my $client = $server->accept();
    
      print STDERR "HandleServer\n";
    
      if ( $client ) {
        my $fileno = fileno($client);
        $client->blocking(0);
        $connections{$fileno}{client} = $client;
        $connections{$fileno}{loggedin} = 0;
        vec($filebits,$fileno,1) = 1;
        print $client "Welcome $fileno\r\n";
        SendMessage( "New Client" );
      } else {
        print STDERR "No accept for server, reopen\n";
        CloseServer();
        OpenServer();
      }
    }
    
    sub HandleClient {
      local( $fileno ) = @_;
    
      print STDERR "HandleClient $fileno\n";
      recv( $connections{$fileno}{client}, $receive, 200, 0 );
      if ( $receive ) {
        my $line = $connections{$fileno}{receive};
        $line .= $receive;
        while ( $line =~ s/(.*)\n// ) {
          my $temp = $1;
          $temp =~ tr/\r\n//d;
          SendMessage( $temp );
        }
        $connections{$fileno}{receive} = $line;
      } else {
        print STDERR "Close client $fileno\n";
        vec($filebits,$fileno,1) = 0;
        $connections{$fileno}{client}->close();
        undef $connections{$fileno};
        SendMessage( "Close Client" );
      }
    }
    
    sub CloseServer {
      vec($filebits,$server_fileno,1) = 0;
      $server->close();
      undef $server;
    }
    
    sub OpenServer {
      $server = IO::Socket::INET->new(Listen    => 5,
                                LocalPort => 3234,
                                Reuse => 1,
                                ReuseAddr => 1,
                                Timeout   => 0,
                                Proto     => 'tcp');
    
      die "Could not create socket $!" unless $server;
    
      $server->blocking(0);
      $server_fileno = fileno($server);
      vec($filebits,$server_fileno,1) = 1;
    
      print STDERR "Starting $server_fileno\n";
    }
    

    I needed this proxy server in TCP on catonmat

  2. In Python:
    • Create a socket
      #!/usr/bin/env python
      
      import socket
      
      host = ''
      port = 50000
      backlog = 5             # keep a backlog of 5 connections
      size = 1024
      s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
      
    • Bind it to a port
      s.bind((host,port))
      s.listen(backlog)
      
    • Listen for connect from clients
      while 1:
          client, address = s.accept()
      
    • Process requests from connected client
          data = client.recv(size)
          if data:
              client.send(data)       # simple echo server
      
    • Disconnect client
          client.close() 
      

    Complete Code

    #!/usr/bin/env python
    
    import socket
    
    host = ''
    port = 50000
    backlog = 5             # keep a backlog of 5 connections
    size = 1024
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.bind((host,port))
    s.listen(backlog)
    while 1:
        client, address = s.accept()
        data = client.recv(size)
        if data:
            client.send(data)       # simple echo server
        client.close() 
    
  3. Using C++/boost
  4. Using C++/ACE
  5. Using C/sockets
  6. Using C#/.NET
  7. Using Java
  8. Using ruby

Written by curious

June 21, 2011 at 7:40 pm

Posted in programming

TECH: SQL Variables

Need to use variables in your SQL script in SQL Server Management Studio. Here you go:

DECLARE @Commodity int
DECLARE @SettleDate datetime

SET @Commodity = 35
SET @SettleDate = '6/14/2011'

SELECT * FROM SettlePrices
WHERE CommodityId = @Commodity
    AND SettleDate = @SettleDate

Written by curious

June 15, 2011 at 3:43 pm

Posted in databases

PROG: Strings

  1. String: A sequence of chars, “Hello, world!”
  2. Declaring strings
    • C++ strings (char*):
      const char* s = "Hello, world";
      
    • C++ strings (STL):
      #include <string>
      using namespace std;
      string s("Hello world");
      string s = "Hello world";
      string *sp = new string("Hello world");
      
  3. Counting length of string
    • C++ strings (char*):
      #include <string.h>
      const char* s;
      int len = strlen(s);
      
    • C++ strings (STL):
      #include <string>
      using namespace std;
      string s;
      int s.length();
      
  4. Is the string empty?
    • C++ strings (char*):
      const char* s;
      (s != NULL && *s != 0) // means not empty
      (s != NULL && *s == 0) // means empty
      
    • C++ strings (STL):
      string s;
      if (s.empty())
        // is empty
      
  5. Print a string to console
    • C++ strings (char*):
      #include <string.h>
      const char* s;
      printf("String=%s\n", s);
      
    • C++ strings (STL):
      #include <iostream>
      #include <string>
      using namespace std;
      string s;
      printf("String=%s\n", s.c_str());
      cout << "String=" << s << endl;
      
  6. Access a character in a string (indexing)
    • C++ strings (char*):
      const char* s;
      char c = s[5];  // read
      char *sp;
      sp[2] = 'A';    // modify
      
    • C++ strings (STL):
      #include <string>
      using namespace std;
      string s;
      char c = s.at(5);   // range checked (may throw std::out_of_range exception)
      char c = s[5];      // no range checking (for efficiency)
      s[2] = 'A';
      s.at(2) = 'A';
      
  7. Passing, returning, assigning, copying string
    • C++ strings (char*):
      const char* sp1;  // src
      char* sp2;        // dest
      strdup(sp2, sp1); // allocates memory
      strcpy(sp2, sp1); // dest <- src (sp1 must be null-terminated)
      strncpy(sp2, sp1, 10);
      sp2[10] = '\0';   // null terminate (strncpy will not put 0 at end)
      strncpy(sp2, sp1, strlen(sp1)+1);  // tell it to copy '\0' too
      memset(sp2, '-', SOMELEN);
      memcpy(sp2, sp1, strlen(sp1)+1);   // warning: sp2, sp1 should not overlap
      memmove(sp2, sp1, strlen(sp1)+1);  // Ok to overlap sp1, sp2
      char* sp3 = sp2;                   // points to same string
      
    • C++ strings (STL):
      #include <string>
      using namespace std;
      string s0, s1;
      string s2 = s0;
      s2 = s1;          // makes a new copy
      s1[2] = 'a';      // does not change s2
      
      string processString(string s);
      string s2 = processString(s1);           // makes copy of s1
      string& processString(string& s);
      string s2 = processString(s1);           // does not make copy of s1 (may modify s1 inside the func)
      const string& processString(const string& s);
      string s2 = processString(s1);           // does not make copy of s1 (can't modify it in the func)
      
  8. Comparing strings, case insensitive comparison, lexicographical ordering
    • C++ strings (char*):
      const char* s1 = "first";
      const char* s2 = "second";
      
      strcmp(s1,s2) == 0
      strncmp(s1,s2,n) == 0
      strcasecmp(s1,s2) == 0   // case insensitive
      strncasecmp(s1,s2,n) == 0
      memcmp(s1,s2,n) == 0
      
    • C++ strings (STL):
      std::string s1, s2;
      s1 == s2, s1 != s2, s1 < s2
      s1.compare(s2) != 0
      s1.compare(s2,n) != 0
      std::string t1, t2;
      std::transform(s1.begin(), s1.end(), t1.begin(), toupper);
      std::transform(s2.begin(), s2.end(), t2.begin(), toupper);
      t1 == t2
      #include <boost/algorithm/string.hpp>
      boost::iequals(s1,s2)
      
  9. Append to a string
    • C++ strings (char*):
      const char* s2 = "second";
      char s[100] = {0}; // need to have a 0 terminated string
      
      strcat(s, s2);
      char c;
      int len = strlen(s)+1;
      s[len++] = c; s[len++] = 0;
      
    • C++ strings (STL):
      char c;
      std::string s, s2;
      s1 += s2;
      s1.append(s2);
      s1.push_back(c); s1 += c;
      
  10. Search a char within a string, find a substring in a string
    • C++ strings (char*):
      const char* sp = "haystack";
      char c = k;
      int pos = strchr(sp, c);
      int rpos = strrchr(sp, c); // start search from end
      int pos = memchr(sp, c);
      
      const char* x = strpbrk(sp, s1); // find any char from set s1
      
      const char* s1 = "stack";
      const char* x = strstr(sp,s1);
      const char* x = strrstr(sp,s1);
      
      int pos = strspn(sp, s1);    // find first char not in s1
      int pos = strcspn(sp, s1);   // find first char in set s1
      
    • C++ strings (STL):
      char c;
      std::string s, s1;
      int pos = s.find(c);
      int pos = s.find(s1);
      int pos = s.find(s1, n);
      int rpos = s.rfind(c);
      
      string ch_set("abcd");
      int pos = s.find_first_of(ch_set); // find any from set of chars
      int pos = s.find_first_of(c);
      int pos = s.find_last_of(s1);
      int pos = s.find_first_not_of(s1); // any char not in this set
      
      
  11. Get a Substring
    • C++ strings (char*):
      const char* s1 = "some long string";
      char s[100];
      strcpy(s, s1+pos);     // from pos to end
      strncpy(s, s1+pos, n);
      
    • C++ strings (STL):
      std::string s1, sub;
      sub = s1.substr(pos, n);
      sub = s1.substr(pos);  // from pos up to end
      
  12. Modify: Insert in a string, Replace a part of a string
    • C++ strings (char*):
      char* s1 = strdup("some long string");
      strncpy(s1+6, "short", 5);               // replace
      
    • C++ strings (STL):
      std::string s1("What day?");
      s1.insert(5, "a hot ");
      s1.insert(s1.begin()+5, "a hot ");
      
      s1.replace(pos, n, newstr);
      s1.replace(pos, n, n2, 'c'); // replace with 'c' repeated n2 times
      s1.replace(s1.begin()+10, s1.begin()+14, "hello");
      
  13. Erase a part of the string
    • C++ strings (char*):
      char *sp;
      sp[pos] = 0;  // terminate string at pos
      strcpy(sp+pos1, sp+pos2); // pos1 < pos2
      
    • C++ strings (STL):
      string s1;
      s1.erase(from, last);
      s1.erase(pos, n);
      s1.erase(pos); // only 1 char
      
      s1.clear();   // empty the string
      
  14. Change case: tolower, toupper
    • C++ strings (char*):
      char *sp;
      while (*sp)
      {
        *sp=tolower(*sp);
        ++sp;
      }
      
    • C++ strings (STL):
      #include <algorithm>
      #include <string>
      #include <cctype>  // for tolower
      string s, s1;
      std::transform(s.begin(), s.end(),pf s.begin(), (int(*)(int))std::tolower);
      
      int (*pf)(int) = std::tolower;
      std::transform(s.begin(), s.end(), std::back_inserter(s1), pf);
      
      class ToLower
      {
      public:
        char operator()(char t) { return std::lower(t); }
      };
      std::transform(s.begin(), s.end(), std::back_inserter(s1), ToLower());
      
  15. Convert numeric types to string, string to numeric types
    • C++ strings (char*):
      char *sp;
      int i = atoi(sp);
      sscanf(sp, "%d", &i);
      
      sprintf(sp, "%d", i);
      sp = itoa(i);
      
    • C++ strings (STL):
      #include <sstream>
      int ival;
      std::stringstream os;
      os << ival;
      string s = os.str();
      
      std::stringstream is(s);
      os >> ival;
      
      template<typename T>
      string toString(const T& t)
      {
        stringstream os;
        os << t;
        return os.str();
      }
      string s = toString(ival);
      
      #include <boost/lexical_cast.hpp>
      
      int ival = boost::lexical_cast<int>("100");
      string sval = boost::lexical_cast<string>(100);
      
      int ival = boost::numeric_cast<int>("200"); // does checks (negative overflow, bad numeric cast, etc)
      

      Ref: String formatters of Manor farm

  16. Read string from a file, or an input stream
    • C++ strings (char*):
      char line[100];
      FILE* fp = stdin;
      fgets(line, sizeof(line), fp);
      
    • C++ strings (STL):
      #include <string>
      
      string line;
      char delim = '|';
      std::getline(std::cin, line);
      std::getline(std::cin, line, delim);     // does not include delimiter
      
      char cstr[256];
      std::cin.getline(cstr, sizeof(cstr)-1);  // does not include delimiter
      
  17. Convert STL string to C-style string
    #include <string>
    std::string s;
    const char* sp = s.c_str();
    
    char sp[100];
    s.copy(sp, n, pos); // copy s[pos -> pos+n] into sp
    sp[n] = 0;          // does not copy terminating 0
    
  18. Reverse a string
    • C++ strings (char*):
      char* reverse(char* s)
      {
          int len = strlen(s);
      	char* sp = s+len-1;
      	char* s1 = s;
      	while (s1 < sp)
      	{
      	    swap(*s1,*sp);
      		++s1;
      		--sp;
      	}
      	return s;
      }
      
    • C++ strings (STL):
      #include <string>
      
      std::reverse(s.begin(), s.end());
      
      string s2(s.rbegin(), s.rend());
      

Reference: CS106X: Programming Abstractions

String Pattern Matching

  1. Brute force/ Naive Algorithm
  2. Deterministic Finite State Automata
  3. Karp-Rabin
  4. Knuth-Morris-Pratt (KMP) – the basic idea is to first pre-process the pattern string P in to a function, Pi(x).

    Pi(x) gives the length of the longest prefix of P[0 … x-1] (excluding P[x]) that is also a suffix of P[0 .. x].

    In other words, if Pi(x) = k

      P[0 … k-1] == P[x-k+1 … x]

    Example: let P=”pompom”, then Pi(5) = length(longest prefix of P[0..4] = “pompo” which is also a suffix of P[0…5]=”pompom”). So Pi(5) = 3.

    Once we have calculated this function, Pi, KMP uses it to make the search more efficient.

    • Implementation in C/C++:
      void
      buildKMPMatcher(const char* P, int* Pi, int n)
      {
        Pi[0] = 0;
        for (int i = 1; i < n; ++i)
        {
          // Pi[i] : length of longest prefix of P[0 .. i-1] that is also a suffix of P[0..i]
          int len = Pi[i-1];
      
          // is P[0..len] going to be a suffix of P[0..i]
          while (len > 0 && P[len]!=P[i])
          {
            len = Pi[len-1];
          }
      
          if (P[len] == P[i])
          {
            len = len+1;
          }
          Pi[i] = len;
        }
      }
      
      int
      findKMP(const char* P, int m, const char* T, int n, int* Pi)
      {
        int j = 0, len = 0;
        for (; j < n && len < m; ++j)
        {
          while (len > 0 && P[len] != T[j])
          {
            len = Pi[len-1];
          }
      
          if (P[len] == T[j])
          {
            len = len+1;
          }
        }
        if (len == m)
        {
          return j-len;
        }
        return -1;
      }
      
      int
      lookup(const char* pattern, const char* textStr)
      {
        char const * P = pattern, *T = textStr;
        int m = strlen(pattern);
        int n = strlen(textStr);
        int *Pi = new int[m];
        memset(Pi, 0, sizeof(int)*(m));
      
        buildKMPMatcher(P, Pi, m);
        int pos = findKMP(P, m, T, n, Pi);
      
      #if DEBUG
        cout << "Pat= ";
        for(int i = 0; i < m; ++i)
        {
          cout << " " << P[i];
        }
        cout << endl;
        cout << "Pi = ";
        for(int i = 0; i < m; ++i)
        {
          cout << " " << Pi[i];
        }
        cout << endl;
      
        cout << "found pattern at index: " << pos << endl;
      #endif
        delete[] Pi;
        return pos;
      }
      
  5. Boyer-Moore

Written by curious

June 13, 2011 at 8:35 am

Posted in programming

Protected: INT: Logic Questions

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

Written by curious

June 8, 2011 at 1:34 pm