Tutorial for Lex

A short tutorial for Lex.

http://dinosaur.compilertools.net/lex/

Tutorial for regular expression

Find a very good tutorial for regular expression!

http://www.regular-expressions.info/quickstart.html

This is a quick start for regular expression. Within this article, there is also a detailed version.

Write script to login a remote machine

As a cs student, I have remotely login many times every day. The name of the remote machine is pretty long and my password is even longer. So I decided to do something.

Firstly, I wrote a scipt like this


#!/bin/bash
ssh username@machinename

Here, username stands for your login name and machinename represents the address of the remote machine.

By running this script, I saved a lot of time to type the long name of the machine. But, another question is I still have to enter the code after running the script. I searched the Internet, keygen seems to be a cool command for me.

http://www.debian-administration.org/articles/152

This website has detailed instructions about how to use keygen. For mac users, we have no ssh-copy-id command. I found an alternative way to copy the public key to the server. The command is

cat ~/cat ~/.ssh/id_rsa.pub | ssh username@machinename "mkdir ~/.ssh; cat >> ~/.ssh/authorized_keys"

install Ctags and Taglist without root

Ctags and Taglist seem to be quite popular plugins for vim editor. Since I'm novice to Linux. It took me several hours to figure out how to configure them for my vim on the department machine. It's kind of tricky because I have no root right on that machine.

I mainly borrowed methods from the following three places,

http://www.thegeekstuff.com/2009/04/ctags-taglist-vi-vim-editor-as-sourece-code-browser/

This one intrigues my curiosity to try out Ctags and Taglist.

http://superuser.com/questions/66367/is-it-possible-to-install-ctags-without-root-privs

The above site introduces how to install Ctags without root.

http://vim-taglist.sourceforge.net/installation.html

The last one is for installing taglist without root.


The main idea of installing Ctags without root is to compile it by yourself and install it in your home directory.

First download Ctags from its webpage and type in the following commands.

$ tar zxf ctags-5.8.tar.gz
$ cd ctags-5.8
$ ./configure --prefix=$HOME
$ make && make install


This will compile and install ctags in your home directory. The resulting binary will be: $HOME/bin/ctags

That's all I did to make Ctags work in my vim. If it doesn't work for you. Just check the second webpage. I omitted several steps which seems not critical to me.

For the Taglist, just follow the instructions in the third page. I only finished the first step - download taglist.zip and uzip it to .vim folder and it works.

The first website contains detailed description about how to use Ctags and taglist in vim. Have fun!

Fix vertical split of screen command in Mac

Screen is a cool command to split the terminal. In Mac, however, only the horizontal split works. I searched the web for a long time and luckily find a way to fix this problem!

$ cvs -z3 -d:pserver:anonymous@cvs.savannah.gnu.org:/sources/screen co screen
$ curl http://old.evanmeagher.net/files/gnu-screen-vertsplit.patch > gnu-screen-vertsplit.patch
$ cd screen/src
$ patch < ../../gnu-screen-vertsplit.patch
$ ./configure --enable-locale --enable-telnet --enable-colors256 --enable-rxct_osc
$ make
$ sudo make install

Good luck to you all!

Quadratic sorting algorithm

Bubble sort:
Time complexity: O(n^2)
Can be used to detect whether an array is sorted.

Selection sort:
Time complexity: O(n^2)

Insertion sort:
Time complexity: O(n^2)
Very efficient on almost sorted array.
In practice, it is more efficient than other simple quadratic sorting algorithms such as selection sort and bubble sort.

Here are the source code for the sorting algorithms above.


void mySort::myBubbleSort(int *Q, int begin, int end){
bool isSorted=0;
int temp;
while(!isSorted){
isSorted=1;
for(int i=0; i<end; i++){
if(Q[i]>Q[i+1]){
temp=Q[i];
Q[i]=Q[i+1];
Q[i+1]=temp;
isSorted=0;
}
}
}
}

myMin mySort::myFindMin(int *Q, int begin, int end){
myMin minValue;
minValue.value=Q[begin];
minValue.pos=begin;
for(int i=begin; i<=end; i++){
if(Q[i]<minValue.value){
minValue.value=Q[i];
minValue.pos=i;
}
}
return minValue;
}
void mySort::mySelectionSort(int *Q, int begin, int end){
myMin minValue;
int temp;
for(int i=0; i<end;i++){
minValue=myFindMin(Q,i,end);
//cout<<"The minimum element is:"<<minValue.value<<" @ "<<minValue.pos<<endl;
temp=Q[i];
Q[i]=Q[minValue.pos];
Q[minValue.pos]=temp;
}
}

void mySort::myInsertionSort(int *Q, int begin, int end){
int temp;
int j;
for(int i=1; i<=end; i++){
temp=Q[i];
for(j=i-1; j>=0;j--){
if(Q[j]>temp)
 Q[j+1]=Q[j];
else{
break;
}
}
Q[j+1]=temp;
}
}

Heap and Heap sort

The following is the code of basic heap operations and heap sort.

//Here is the header file myHeap.h


#ifndef MYHEAP_H
#define MYHEAP_H
class myHeap{
int heapSize;
public:
int parent(int i){
return i/2;
}

int left(int i){
return 2*i;
}

int right(int i){
return 2*i+1;
}

void maxHeapify(int *A, int i);
void makeHeap(int *A, int size);
void myHeapSort(int *A, int size);
};

#endif

//Here is the source file myHeap.cpp


#include "myHeap.h"
void myHeap::maxHeapify(int *A, int i){
int l=left(i);
int r=right(i);
int temp=0;
int large;

if(l<=heapSize && A[l-1]>A[i-1]){
 large=l;
}
else
 large=i;

if(r<=heapSize && A[r-1]>A[large-1]){
 large=r;
}

if(large!=i){
temp=A[i-1];
A[i-1]=A[large-1];
A[large-1]=temp;
maxHeapify(A, large);
}

}

void myHeap::makeHeap(int *A, int size){
heapSize=size;
for(int i=heapSize/2; i>0; i--)
 maxHeapify(A,i);

}

void myHeap::myHeapSort(int *A, int size){
makeHeap(A,size);
for(int i=heapSize;i>1;i--){
int temp=A[0];
A[0]=A[i-1];
A[i-1]=temp;
heapSize--;
maxHeapify(A,1);
}
}

Things need to pay close attention to when designing the heap code:

1) The index of an array begins from zero. The index of a heap tree begins from one.

2) The use of "large" in maxHeapify is quite beautiful. You need to first compare A[l] with A[i] and assign the larger one to large. Then compare A[r] and A[large].