Wednesday, December 28, 2011

Quick Sort

Quick Sort運用到Divide and Conquer的觀念，即是當我們把問題分到很小很小的時候，小問題相對容易解決，而每一個小問題解決之後，大問題也順勢被解決了。其中，把資料分成一半，一半再分成一半...的循環是很常見的。

Qucik Sort的方法是在原本資料中隨意取出一個element當作pivot，將所有小於此資料的elements放到pivot的左邊，大於者放到右邊，接著分別在左右邊的所有elements中另外各取一個pivot，遞迴地重複一樣的事情，直到分割出來的資料大小是零或是一後便不再分割，最後把所有被分割的資料依序組合起來，整個資料便會照順序排列了。

```#include <stdio.h>

// Function Declarations
void qsort(int *arr, int left, int right);
int partition(int *arr, int left, int right, int pivInd);
void swap(int *a, int *b);
void printArr(int *arr, int len);

/*
* Function : main
*/
int main(void){

int arr[8] = {6,5,2,3,8,1,7,4};

// print out original array
printArr(arr, sizeof(arr)/sizeof(arr[0]));

// qsort here
qsort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);

// print out the array after sorting
printArr(arr, sizeof(arr)/sizeof(arr[0]));

return 0;
}

/*
* Function : qsort
* By using divide and conquer, we keep finding a pivot
* and make the elements which are smaller than it in
* front of the pivot.
*/
void qsort(int *arr, int left, int right){

if(right &gt; left){

//divide
int pivInd = (right + left) / 2;
pivInd = partition(arr, left, right, pivInd);

//conquer
qsort(arr, left, pivInd-1);
qsort(arr, pivInd+1, right);

}

}

/*
* Function : partition
* Make the elements which are smaller than arr[pivInd] in
* front of the pivot. And return the index of the original
* arr[pivInd].
*/
int partition(int *arr, int left, int right, int pivInd){

// pivot value, store index
int pivVal = arr[pivInd];
int stoInd = left;

// swap the pivot and the last element
swap(&amp;arr[pivInd], &amp;arr[right]);

// scan through the arr from left to right-1
// make the elements which are smaller than pivVal in the font
int i;
for(i=left ; i&lt;=(right-1) ; i++){
if(arr[i] &lt; pivVal){
swap(&amp;arr[stoInd++], &amp;arr[i]);
}
}

// swap back the pivot and the last element
swap(&amp;arr[stoInd], &amp;arr[right]);

// return the index where the original arr[pivInd] stores
return stoInd;
}

/*
* Function : swap
* Swap to variables by passing two pointers.
*/
void swap(int *a, int *b){
int t;
t = *a;
*a = *b;
*b = t;
}

/*
* Function : printArr
* Print out the array
*/
void printArr(int *arr, int len){
while(len--)
printf("%d ",*arr++);
printf("\n");
}
```

```qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);
```

```#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b){
return ( *(int *)a - *(int *)b);
}

void printArr(int *arr, int len){
while(len--)
printf("%d ",*arr++);
printf("\n");
}

int main(void){

int arr[8] = {6,5,2,3,8,1,7,4};
int len = sizeof(arr)/sizeof(arr[0]);

printArr(arr, len);

// qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(arr[0]), compare);
qsort(arr, len, sizeof(arr[0]), compare);

printArr(arr, len);

return 0;
}
```

檔案讀取的兩種方法

1. 使用fscanf/fprintf：先定義FILE指標*fin, *fout指到檔案，之後使用fscanf/fprintf時，把fin/fout當作第一個參數，而第二個、第三個分別與scanf/printf的第一個、第二個相同。
```#include

int main(int argc, char *argv[]){

// define fin, fout as a FILE pointer
FILE *fin = fopen(argv[1], "r"),
*fout= fopen(argv[2], "w");

// copy whatever in the fin to fout
char c;
while(fscanf(fin, "%c", &c) != EOF){
fprintf(fout, "%c", c);
}

fclose(fin);
fclose(fout);

return 0;
}
```
2. 使用freopen：此時我們把原本的鍵盤輸入輸出(standard input/output, or stdin/sdtout)改成檔案的輸入輸出，於是乎之後的所有print, scanf會直接輸入/輸出到檔案。
```#include

int main(int argc, char *argv[]){

// redirect stdin/stdout to file read/write
freopen(argv[1], "r", stdin);
freopen(argv[2], "w", stdout);

// copy everything
char c;
while(scanf("%c", &c) != EOF){
printf("%c", c);
}

return 0;
}
```

• 第一種方法(fscanf/fprintf)執行起來比較沒有效率，因為每一次都要透過FILE指標，找對應的檔案。
• 第二種方法執行過freopen就沒有辦法再使用stdin/stdout的printf/scanf了。

queue像是排隊，先排進隊伍的東西，會先被取出queue，也就是(FIFO, first in first out)，因而我們可以得知queue和stack的差別即queue是一頭放入、另一頭取出，然而stack中放入、取出的都是同一邊。queue實作上我們需要有兩個指標指向分別指向頭和尾。

• 放入、取出的函式命名不同，有：pop/push, enqueue/dequeue, etc.
• queue指標定義為廣域(global)或區域(local)
• pop函式傳回值為裡面的data或整個node
• 被handle的error數量

```#include
#include

#define PUSH 1
#define POP  2
#define DISPLAY 3

#define EMPTY_MESSAGE 2147483647

/*
* Struct Node Declaration
*/
struct node{
int data;
struct node *next;
};

struct node *head = NULL, *tail = NULL;

/*
* Function Declarations
*/
static void push(int new_data);
static int pop();
static void display();

static int isEmpty();

/*
* Function : main
*/
int main(void){

while(1){

int sel;
printf("[Queue] (1)push\t(2)pop\t(3)display >> ");
scanf("%d", &sel);

// do different operations according to the
// user's selection
int new_data, pop_data;
switch(sel){

// push
case PUSH:
// read data from the user
printf("push >> ");
scanf("%d", &new_data);
// push it in the queue
push(new_data);
break;

// pop
case POP:
pop_data = pop();
if(pop_data != EMPTY_MESSAGE){
printf("pop >> %d\n", pop_data);
}
break;

// display the queue
case DISPLAY:
display();
break;

// handle the problem if the user insert
// something wrong
default:
printf("Wrong Selection.\n");

}

}

return 0;
}

/*
* Function : push
* Push in a new data to the queue.
*/
static void push(int new_data){

// create a new node and store the new data in it
struct node *new;
new = (struct node *)malloc(sizeof(struct node));
new->data = new_data;

// if there's nothing in the queue
}
else{
// link the new node after the original tail node
tail->next = new;
tail = new;
}

}

/*
* Function : pop
* Pop out the topped node in the queue.
*/
static int pop(){

int pop_data;

// handle the issue if the queue is empty
if(isEmpty()){
printf("The queue is empty.\n");
return EMPTY_MESSAGE;
}
else{
// store the data of the head into pop_data

// delete the head node and free the memory
free(dump);

// if the user pops out the last node,
// let tail point to NULL
if(head == NULL) tail = NULL;
}

return pop_data;
}

/*
* Function : display
* Display all the data in the queue.
*/
static void display(){

// if the queue is empty
if(isEmpty()) printf("The queue is empty.\n");

// go through the link list
while(ptr){
printf("%d\n", ptr->data);
ptr = ptr->next;
}

}

/*
* Function : isEmpty
* Return whether the queue is empty or not.
*/
int isEmpty(){
}
```

Tuesday, December 27, 2011

Stack Using List List 2

• pop所移除掉的值以函式回傳值的方式呈現
• 使用free()函式釋放掉不需要的記憶體空間（pop時）

```#include
#include

#define PUSH 1
#define POP  2
#define DISPLAY 3

/*
* Structure node declaration
*/
struct node{
int data;
struct node *next;
};

struct node *top = NULL;

/*
* Functions declarations
*/
static void push(int num);
static int pop();
static void display();

int main(void){

while(1){

// let user select which operation to do on the stack
int sel;
printf("[Stack]\t(1)push\t(2)pop\t(3)display >> ");
if(scanf("%d",&sel)==EOF) break;

// do the operation depends on the selection from the user
int temp;
switch(sel){

// push
case PUSH:
// scan in a integer
printf("push >> ");
scanf("%d", &temp);
// push it into the stack
push(temp);
break;

// pop
case POP:
printf("pop >> %d\n", pop());
break;

// display all the items in the stack
case DISPLAY:
display();
break;

// wrong selections handler
default:
printf("Wrong Selection.\n");

}

}

//end
printf("Exit Program.\n");

return 0;
}

/*
* Function : push
*/
static void push(int num){

// declare a new node pointer
struct node *temp;

// let temp point to a new node which store the new data
temp = (struct node *)malloc(sizeof(struct node));
temp->data = num;

// let temp link to next
temp->next = top;

// let temp become top
top = temp;

}

/*
* Function : pop
*/
static int pop(){

// declare a int variable to store the pop out data
int popData = -1;

// if there's something in the stack
if(top!=NULL){

// declare dump as a pointer, which points
// to the node going to be deleted
struct node *dump;
dump = top;

// store the data and return it at the end of function
popData = top->data;

// let top point to the next node
top = top->next;

// free/release the memory which stores the deleted node
free(dump);
}
// if the stack is empty
else{
printf("Stack Bottom.\n");
}

return popData;
}

/*
* Function : display
* Display all the elements in the stack.
*/
static void display(){

// deleclare ptr as same as top
struct node *ptr = top;

// scan through the link list until ptr==NULL
while(ptr){

// print out the data
printf("%d\n", ptr->data);

// ptr points to the next node
ptr = ptr->next;

}

}

//end
```

Monday, December 26, 2011

• push：將東西放入。
• pop：將東西取出。
• display：顯示堆疊中的所有東西。

• push：將新進來的資料存到一個新的node（在此稱temp）裡面，再將這個node的下一個node指標指向top（temp->next = top），最後將top指向這新的node（即top = temp）。
• pop：將top裡的數據印出，透過top = top->next的方式刪除掉最上層的node。
• display：定義一個新指標指向top，然後讀取該node裡面的數據，之後再將自己指向next，再讀取數據，不斷循環至該指標為NULL（沒有指向任何node）為止。

```#include
#include

#define PUSH 1
#define POP 2
#define LIST 3
#define EXIT 4

struct node
{
int data;
struct node *next;
};

struct node *top = NULL;

/*
* Functions Declarations
*/
static void push(int num);
static void pop();
static void display();

int main(void)
{

while(1)
{

int sel;
printf("[Stack]\t(1)push\t(2)pop\t(3)display >> ");
if(scanf("%d",&sel)==EOF) break;

int temp;
switch(sel)
{
case PUSH:
printf("push >> ");
scanf("%d",&temp);
push(temp);
break;

case POP:
pop();
break;

case LIST:
display();
break;

default:
printf("Wrong Selection.\n");

}

}

//end
printf("Exit Program.\n");

return 0;
}

/*
* Function : push
*/
static void push(int num){

struct node *temp;

temp = (struct node *)malloc(sizeof(struct node));
temp->data = num;
temp->next = top;
top = temp;

}

/*
* Function : pop
*/
static void pop(){

if(top!=NULL)
{
printf("pop : %d\n", top->data);
top = top->next;
}
else
{
printf("Stack Bottom.\n");
}

}

/*
* Function : display
* Display all the elements in the stack.
*/
static void display(){

struct node *ptr = top;

while(ptr){

printf("%d\n", ptr->data);
ptr = ptr->next;

}

}

//end
```

Sunday, December 25, 2011

Draw A Simple Rectangle Using GTK

本想用GTK繪製一些幾何地圖，然而發現網路上多只有Reference，而實作類似的簡易GTK程式不多，於是寫了一個當作練習。

其中GtkWidget *window表示最外層的視窗，GtkWidget *drawingArea被包在window裡面，為可以畫畫的地方(這裡在上面畫一個Rectangle)。

```#include <"gtk/gtk.h">

// Three main elements of this program.
GtkWidget *window;
GtkWidget *drawingArea;
GdkPixmap *pixMap;

// Functions
static void createWindow();
static void createDrawingArea();
static void layoutSetting();
static void show();

static void draw();

// Event handlers
static gboolean expose_event(GtkWidget *widget, GdkEventExpose *event);
static gboolean configure_event(GtkWidget *widget, GdkEventConfigure *event);
static gboolean delete_event(GtkWidget *widget, GdkEvent *event, gpointer data);
static void destroy(GtkWidget *widget, gpointer data);

/*
* Main Function
*/
int main(int argc, char **argv){

gtk_init(&argc, &argv);

//initializations
createWindow();
createDrawingArea();

//setup layout
layoutSetting();

//show
show();
draw();

gtk_main();

return 0;
}

/*
* Function : createWindow
* Setup window as a new gtk_window, and connect the "delete_event" and
* "destroy" signal to handlers.
*/
static void createWindow(){

window = gtk_window_new(GTK_WINDOW_TOPLEVEL);
gtk_container_set_border_width(GTK_CONTAINER(window), 40);
gtk_window_set_title(GTK_WINDOW(window), "Blocking Practice");

//event handling
g_signal_connect(window, "delete-event", G_CALLBACK(delete_event), NULL);
g_signal_connect(window, "destroy", G_CALLBACK(destroy), NULL);

}

/*
* Function : createDrawingArea
* Setup the drawingArea, and connect the "expose_event" and "configure_event"
* events to their handlers.
*/
static void createDrawingArea(){

drawingArea = gtk_drawing_area_new();

//event handling
gtk_signal_connect(GTK_OBJECT(drawingArea), "expose_event",
(GtkSignalFunc)expose_event, NULL);
gtk_signal_connect(GTK_OBJECT(drawingArea), "configure_event",
(GtkSignalFunc)configure_event, NULL);

//setup size
gtk_drawing_area_size(drawingArea, 600, 600);

}

/*
* Function : layoutSetting
* Contain "drawingArea" into "window".
*/
static void layoutSetting(){
}

/*
* Function : show
* Show the elements.
*/
static void show(){
gtk_widget_show(drawingArea);
gtk_widget_show(window);
}

/*
* Function : delete_event
* Event handler for the "delete_event" from "window"
*/
static gboolean delete_event(GtkWidget *widget, GdkEvent *event, gpointer data){
g_print("Quit!\n:");
gtk_main_quit();
return FALSE;
}

/*
* Function : destroy
* Event handler for the "destroy" from "window"
*/
static void destroy(GtkWidget *widget, gpointer data){
gtk_main_quit();
}

/*
* Function : draw
* Draw a sample rectangle located at (100,150) with 20-width and
* 30-height.
*/
static void draw(){

//setup a gdk rectangle
GdkRectangle rect;
rect.x = 100;
rect.y = 150;
rect.width = 20;
rect.height = 30;

//draw on "drawingArea"
gdk_draw_rectangle(pixMap,
drawingArea->style->white_gc,
TRUE,
rect.x, rect.y,
rect.width, rect.height);
gtk_widget_queue_draw_area(drawingArea, rect.x, rect.y, rect.width, rect.height);

}

/*
* Function : expose_event
* Event handler for the "expose_event" from "drawingArea"
*/
static gboolean expose_event(GtkWidget *widget, GdkEventExpose *event){
gdk_draw_drawable(widget->window,
widget->style->fg_gc[GTK_WIDGET_STATE(widget)],
pixMap,
event->area.x, event->area.y,
event->area.x, event->area.y,
event->area.width, event->area.height);
return FALSE;
}

/*
* Function : configure_event
* Event handler for the "configure_event" from "drawingArea"
*/
static gboolean configure_event(GtkWidget *widget, GdkEventConfigure *event){

if(pixMap) g_object_unref(pixMap);

pixMap = gdk_pixmap_new(widget->window,
widget->allocation.width,
widget->allocation.height,
-1);

gdk_draw_rectangle(pixMap,
widget->style->black_gc,
TRUE,
0, 0,
widget->allocation.width,
widget->allocation.height);

return TRUE;

}
```

Sunday, December 18, 2011

實驗室參觀心得

今天到數個交大的實驗室，有多媒體系統、多媒體嵌入式系統、電腦視覺與模擬、...（名字我沒有記很清楚），發現這些實驗室都不約而同地各有張實驗桌是做3D Computer Vision用的，有人用兩台攝影機、有人用單張影像、有人用Kinect，大家都想要準確有效率的抓到實物的3D模型，詢問那兒研究生，他們表示這是幾十年都一直在研究的問題。我不禁有幾個疑惑：
1. 大家都在為同一個目的而做實驗，沒人有很好的成果甚至商品化？
2. 既然能想到的大家都研究的差不多了（這句話來自今天跟我談話的研究生），那麼大家現在又是在研究什麼？
學長：XBox Kinect 不算是 3D computer vision 商品化的產品嗎？

A virtual Easter egg is an intentional hidden message or an in-joke in a work such as a computer program,web page, video game, movie, book or crossword. -- Wikipedia
Easter egg(復活節彩蛋)是隱藏在程式裡面的小驚喜，許多我們常用的程式、網頁蔵有這樣的東西，主要目的是讓使用者覺得有趣一些。

Let it Snow

Do A Barrel Roll

Monday, December 12, 2011

Stanford Courses Starting 2012

Stanford從今年開始提供很多完整且免費的網路課程，我在今年已快上完Machine Learning，接下來的2012又有更多的課程，多為一、二月開始，我發現到其中Computer Security的部份也有Bekerley的教授一同教學。

Entrepreneurship

Medicine

Civil Engineering

Electrical Engineering

Complex Systems

Computer Science