Sunday, November 26, 2006

[TECH] Algorithm to find euler circuit in a graph in O(|E|)

Important observation I found is that, if we delete a cycle (delete all the edges which form a cycle) from the graph which has a Euler circuit, the property of the graph still remains, i.e the necessary and sufficient condition for the graph to have a Euler cycle is that every vertex should have even degree. And also there has to be a cycle at every vertex.

INPUT: G =(E,V)
v = v
euler_cycle = NULL;
while(|E| > 0){
 /*Find a cycle in G, start
   the search at v, returns c0 around 
  which cycle is formed*/
 c0 = FIND_CYCLE(G,v);
 v = GET_NON_ZERO_DEGREE_VERTEX(c0); 
/*Above can be done in constant time,
 using some space while finding the cycle
 */
 MERGE(c0,euler_cyle);
/*constant time operation,
 put c0 after an edge e1 in
 euler cycle which ends at 
 vertex 'v', we can just remember 
 the position of v n euler_cycle
 every time we merge*/

}

[TECH] Building tags on the complete source code...

I see that sometimes

  $ctags -R *  
don't work. I just typed
$ctags -R *
in my cygwin it crashed
 ctags.exe.stackdum 
. Well now the question is how do I build the tags on the complete source recursively if
  -R 
don't work, we can use the the following to build the tags


$find . -name "*.c" -exec ctags -a \{\} \; -print; sort tags > tags1; mv tags1 tags;

The -a option appends to the existing tags file build

I initially thought that ctags keeps some seek information of the file in tags file,but just was amazed its a 3 column multientry text file, the first column is the tag which you are searching, second column is the file where is tag is and the most interesting part the 3 column is the search string for vim....hmmm see every one takes advantage of the plethora of things vim can do :)

Make_bp_profile ./RNAlib/ProfileDist.c  /^PUBLIC float *Make_bp_profile(int length)$/
Make_swString   ./RNAlib/stringdist.c   /^PUBLIC swString *Make_swString(char *string)$/

.........luv.......Vamsi

Saturday, November 25, 2006

[TECH] Never use a file stream for lookahead reading while using lex.....

Just got the parser working....I did a lot of modification to mac's code, especially the grammar rules which have the lookahead information while parsing. The code tries to read from the

yyin
file stream of lex, but that is really pathetic because lex code is now optimize and it position in the lex buffer may not correspond to the position in the filestream...well this is what is the bug in code, well it took a while to fix. But its a good one.

I added lookahead rules

(st,bt)\n[\+]{linenum++;}
(st,bt)\n[\*].*${linenum++;}
for lookahead extensions and comments in the spice syntax.

Tomorrow I'll get the layout printed ,,,,,,

Apart from this folks from india called and were telling me about the issues regarding priya pickles, well I think its really a slander against Ramoji Rao, any way I support this guy...yes may be after that great 3 day party at ramoji film city makes me baised, I guess you too will be baised once you receive that wonderful hospitality at hotel sitara in ramoji film city...when our team (verification group) went out there I saw mithun chakraborthy

..........luv..........Vamsi

Thursday, November 23, 2006

[TECH] SPICE layout generator.......

I have been a bit of slackish this week, but sure I want to start running soon.

Last night I read about the BPlane (Binned Plane datastructure used in micromagic, I need to implement that in magic soon).

Tonight, I thought about backing up my CVS repository regularly into my external hardrive, so that I can keep all my projects safe.

SPICE Layout generator

My new project, which generates cell layout from by reading from the SPICE files (transistor netlist) directly. I need to rewrite some of the code for the algorithm which tries to find the EULER trace in the transistors graph (and also its p-stack dual graph). Its exiting for me start it today....

I'am in love with my life for the first time.......writing code is what I loved apart from all other tensions in life I love it

Tomorrow morning I'll be running for the sale in circuit city and best buy

[TECH] SRM327

http://www.topcoder.com/stat?c=problem_statement&pm=6871&rd=10007

/*
 * topcoder_class1.java
 *
 * Created on November 22, 2006, 1:41 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package topcoder_srm1;

/**
 *
 * @author vamsi
 */
import java.lang.Math;

public class NiceOrUgly{


   
    private boolean checkNice(char[] s_arr,int len){

 int vcount=0;
 int ccount=0;
 int i;
 for(i=0;i

I challenged some guy in this SRM got 50 bonus points.

..........luv......vamsi

Monday, November 20, 2006

[TECH] DAG's and Dynamic Programming......

Directed Acyclic Graph (DAG), directly embeds into dynamic programming....as from Vazirani's notes, the useful property of the DAG is that its nodes can be linearized (topologically). So if we process these nodes in the topological order we have sub-problems solved and the solution can be used for the next level. In the simple example of shortest path, we need (u1,v) , (u2,v) are the edges adjacent on the node v. To solve the shortest path problem we need the shortest path to u1, u2 to get the shortest path to v. The wonderful property of the DAG's is that if we start with the topological SOURCE (may be hypothetical by adding 0 weight edges), we are sure that we solved u1,u2 before solving v (if we process the nodes in topological order)

Longest monotonic subsequence in a given sequence, suppose the given sequence is '5,2,8,6,3,6,9,7' (The longest monotonically increasing sequence) in this is 2,3,6,9. On the first look, it appears that it doesn't have sub-optimality inside it. In the sense take a subsequence '5,2,8' the longest monotonically increasing subsequence in this is is (5,8) or (2,8) but neither (5,8) and (2,8) is not in the overall longest monotonic subsequence, so the question is how dynamic programming works here??.....well people don't talk about the sub-optimality here......but still this can be solved by dynamic programming...
Let me restate the principle of optimality here...."If a optimization problem involves of sequences of decisions d1,d2,d3,d4...dn . The principle of suboptimality states that what ever decision you make initially the rest of the decisions should still optimize whats remaining after making decision d1...i.e would form a sequence of decisions to save a smaller optimization problem
Any way I wrote the following code segment , S[i] = length of the longest monotonic subseqence ending at index i, input is a array of integers A[i].

global_max_length=-INFINITY;
PATH[N];
for(i=0;i0;j--){
      if(A[j] < A[i]){
         if(S[j]+1 > S[i]){
             S[i] = S[j]+1;
             if(S[i] > global_max_length){
                 global_max_length = S[i];
                 PATH[N] = j;
             }
             PATH[i] = j;
         }
      }
   }
}

void printSeqence(){

 int j=N;
 do{
  print("%ld ",A[PATH[j]]);
  j = PATH[j];
 }while(j!=PATH[j])

}

global_max_length , returns the length of the longest monotonic increasing sequence, and also prints the sequence

Apart from this life has been very cold, man today was REALLY_ __FREEZING__ here, I have cold the damn cold, I cannot drink cool drinks, eat any cold stuff it sucks......Well , I'll be going to India soon meet swapna,chamu...just talked to chamu on the phone, hope to see her and swappy soon...............THE LIFE GOES ON ON ON...by the way the GYM is closed till 26th and its cold outside I cannot even jog its really HELL out here

With love ...............Vamsi...............

Tuesday, November 14, 2006

[TECH] Channel Router for cell synthesis......

Its quite an effort to get this thing working.....started on saturday night , worked on sunday, and monday night its done


perl had lot of kookups especially my $a,$b and my ($a,$b) are not the same, I pulled it from the manual. sometimes its really hard to fix this kind of errors, thanks for that wonderful debugger 'perl -d' , its really great to work with.

But I did'nt see if perl debugger has a backtrace kind of facility? just a gdb?


Life apart for my passion of the CGEN2MAGIC project, is quite slow need to study a lot about that Border Minimization Problem, also got the home work done on parallel algorithms and network flows.


I guess I'have started loving algorithms/problem solving...its really kewl


Take care....HAPPY CHILDRENS DAY.

Saturday, November 11, 2006

[TECH] Setting up VNC on LAN

Today I got my laptop dell-inspiron-640m, I have linux desktop running fedora connected to a wireless router which my friend uses, so totally we have 3 computers connected to the wireless router. Actually we have cloned the MAC address of my desktop onto the wireless router. Now I want to use my laptop and start working with vnc on my desktop. By default the port 5901 was firewalled, I had to setup the firewall to accept the tcp:5901. After which I had the probelems with the window manager, by default kde starts the twm& . So I edited the xstartup file to get the kde.


kwin & kdesktop & kicker &


You need all the three things to get the kde desktop up and running

Well thats all the infrastructure work, now I'am back to write the CHANNEL ROUTER for CGEN which I have not worked on for the last three days, due that motif-algorithm which I have been working on, last week I also had the polynomial algorithm for FINDING OUT ALL THE CUTS in the network flow graph.

Take care guys, I also had a long chat with swapna and that was really wonderful.

Monday, November 06, 2006

[TECH]Crippled mmap

I was trying to use a anonymous memory mapping to use in the first version of the Tile database memory manager which I was writing,

mmap(void *start_address,size_t length,int prot,int flags,int fd,off_t offset)

. I had prot = MAP_ANONYMOUS , (I thought its equivalent to MAP_ANON | MAP_PRIVATE , the man page says MAP_ANON , is depreciated). Well any way I got it fixed by MAP_ANONYMOUS | MAP_PRIVATE.


Last time I had problem with this syscall is when I need to mmap to actual address's , i.e the start_address argument is not NULL, once again WHEN YOU DO A MMAP FOR A STATIC ADDRESS YOU NEED TO HAVE OFFSET OF THE FILE ALIGNED TO THE PAGE BOUNDARY.