the sieve of Eratosthenes

ok,there is a mistake I made in previous post;
I mentioned about selected method,but actually,it's the sieve of Eratosthenes,a most efficient way to list all small prime number,that is less or equal to 10,000,000,000.
Make a list of all the integers less than or equal to n (greater than one) and strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes.
For example, to find all the odd primes less than or equal to 100 we first list the odd numbers from 3 to 100 (why even list the evens?) The first number is 3 so it is the first odd prime--cross out all of its multiples. Now the first number left is 5, the second odd prime--cross out all of its multiples. Repeat with 7 and then since the first number left, 11, is larger than the square root of 100, all of the numbers left are primes.

ehh,after the basic instruction,I need to know some efficient implementation,since it's memory consuming in my idea(it's useless).

probable prime

I'm looking for a nice method to test if a arbitrary integer is prime;
of course,I've heard a method named selected method,but now,I find a better way.It is based on the fermat's theorem:if p is prime,any integer a>1,we have a^p=a(mod p);
fermat's theorem gives us a powerful method to test arbitrary positive integer n,choose any integer a,caculate a^(n-1),if n is a prime,then the result must modulo n,if it's not,then the contrary.
btw,there is a quick way to caculate the value of exponentiation,we call it binary exponentiation.I'll introduce it in the next post,maybe with its source code.

prime

when bathing just now,I remind that the important of prime mentioned in the elementary of number theory;
here is an useful page for prime:
http://primes.utm.edu/
in its categories,u can find a program category...nice;

senior in college.

i'm most likely to be a senior student in college in month?
i don't like this feeling.
today,i chatted with Gaimo Huang,he plans to work after his college life at amoy or at home.that seems to be great,since he has got a scheme for his future.
but,what about me?that's the key problem,it's my time that eagers to my plan.
always,i'm on the road with lots of crosses,that's my way...
what's the end?

ok,it's meaningless for discussing much about this topic,since it'll be fine as time goes.i'm watching friends(it's a soap tv play) these days,that's pretty fun,recommend it.btw,it's a good assistant for english listening.
it's difficult for me to understand the paper for wrls-vff.
that's all today,it's time for bed.

hash table

our next topic is hash table,a technique that used to store,search and get information in O(1) time;
as a instruction,I thought I should show a definition first,what is hash table?here we go,hash table is a dictionary in which keys(or information) are mapped into array positions by hash function.
what is the scheme when we come across a hash table problem?
first,we need to choose a proper hash function to tackle the key;
then,decide how to deal with the value returned from hash function,since there is a hitch called collision,that is,two absolutely different key value will get the same mapped value with the corresponding hash function;

we will open with how to resolve the collision;
there are two methods,one is chaining,the other is open-addressing;
in chaining,we can place all elements in a linked list which hash to the same slot,whose fundamentle operations are easy to be implemented,such as insert,search,delete...etc;

about hash function;
there are three schemes for devising a suitable hash fucntion;
ps.in what follows,we interpret keys as natural numbers;
one is division method,one is multiplication method,the last is universal hashing;
for the division method we have model likes h(n)=n mod m,for which we get the rmainder of the natural number n divided by m,whos optimal value may be a prime not too close to a power of 2.

to be continued...
with candy heart.

at amoy again

I'm on my way to school this afternoon,for I need to fetch some books on my subjects and my pc also.
It's quite difficult for me to get my pc,the reason is easy,every body are busy with our project,scispeech.though disease follows me,I can't quit while the pretty important time:we need a good ending,you see?
I'm shame now,after all,I have to quit...every thing is ready,if it's sun tomorrow morning,I will leave in plan.
for my annoying roomate,he bring his gf for night,I have to leave just after arriving.in a mass,I forget to get my data structure,os,compiler principles...oh,my god,that's the main purpose this travel.

google's blogger in beta

august 14,google released the blogger's beta version;
with new features;
you can categorize your posts in labels,this new function is useful;with this,u don't need to write all in a bunch,which is pretty similar to my first blog server;

control who can read your post;ok,I've to said,this new thing expected to be;

change your blog's appearance and content with your mouse instead of html;for me,html may be much more useful;

of course;there are restrictions;limited users can experience it,I'm out of this range,since I found nothing on my dashboard as mentioned on buzz of blogger;
but,I will as time goes;;

skipping elementary data structure

among kinds of data structure,I will ignore the stacks, queues, linked lists,binary tree etc...
of course some key data structure won't be skipped,since I didn't understand them well during the first meet before, such as hash table; there are lots of wonderful manipulations that are tricky;
beside hash table,binary sreach tree,red-black tree and so on are as important as hash table;

why I review introduction to algorithms?

several days ago,while talking with bealone,I said I'm reviewing introduction to algorithms;to this, he said why?
I don't really know why; if I'm just preparing for my graduate life or the exam,it may be redundant,which is quite correct.
I'm pretty sorry for I don't precisely know what I need; can I looking forwards a better university? or maintain current situation?
for my rank-list is not at the top,I am not confident for my choice?
maybe time will confirm what I need to do; now just prepare and wait;
conbadei...hihi;

soucce code for counting sort

#include "iostream"
#include "malloc.h"
using namespace std;

#define SIZE 10

void countingsort(int *A,int lengthA, int k)
{
int *C;
int i,j;
C = (int*)malloc(k*sizeof(int));
for ( i = 0; i < k; i++ )
C[i] = 0;
for ( i = 0; i < lengthA; i++ )
C[i]++;
for ( i = 0, j = 0; i < k; i++ )
while ( C[i]-- ) A[j++] = i;
}

int main(void)
{
freopen("org.txt","w",stdin);
int A[SIZE];
int i;
for ( i = 0; i < SIZE; i++ ) {
A[i] = rand()%SIZE;
cout << A[i];
}
countingsort(A,SIZE,SIZE);
freopen("res.txt","w",stdin);
for ( i = 0; i < SIZE; i++ ) {
cout << A[i];
}
return 0;
}

counting sort

there is a restriction for counting sort,that is we must know the range of the elements;
we can count the number of each integer in range among array to be sorted,since we can create a array with length of the range as a temporary working storage;that's why we call it counting sort;
once we know the algorithm,it's easy to design a pseudocode as follow;
procedure counting-sort(A,lengthA,k) //A to be sorted,k range of integer;
for(i = 0; i < k; i++ ) {
__C[i] = 0;
}
for(i = 0; i < lengthA; i++ ) {
__C[A[i]]++;
}
for(i = 0, j = 0; i < k; i++ ) {
__while(C[i]--) A[j++] = i;
}
end procedure;
that's all;

linear time sort algorithms

all comparison algorithms's best upper running time is O(nlgn);
here goes three algorithms,whose upper running time is O(n);
counting sort;
radix sort;
bucket sort;

source code for quicksort

#include "iostream"
using namespace std;

#define SIZE 100000

int partition(int *A, int p, int r)
{
int x = A[r];
int i,j, tmp;
for ( i = j = p; j < r; j++ ) {
if(A[j] <= x) {
tmp = A[j];
A[j] = A[i];
A[i] = tmp;
i++;
}
}
tmp = A[r];
A[r] = A[i];
A[i] = tmp;
return i;
}

void quicksort(int *A, int p, int r)
{
int q;
if ( p < r ) {
q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}

int main(void)
{
freopen("org.txt","w",stdout);
int A[SIZE];
int i;
for ( i = 0; i < SIZE; i++ ) {
A[i] = rand()%SIZE;
cout << A[i] << endl;
}
quicksort(A,0,SIZE-1);
freopen("res.txt","w",stdout);
for ( i = 0; i < SIZE; i++ ) {
cout << A[i] << endl;;
}
return 0;
}

algorithm for quicksort

subroutine's psedocode:
procedure partition(A,p,r) //p,r are upper and bottom of the subarray;
x=A[r];
for( i = j = p; j < r; j++) {
__if(A[j] <= x) {
____tmp=A[j];
____A[j]=A[i];
____A[i]=tmp;
____i++;
__}
}
tmp=A[i];
A[i]=A[r];
A[r]=tmp;
return i;
end procedure;

procedure quicksort(A,p,r)
if(p < r) {
__q=partition(A,p,r);
__quicksort(A,p,q-1);
__quicksort(A,q+1,r);
}
end procedure;
that's all;

description of quicksort

quicksort is a sorting algorithm who is the most popular algorithm.
quicksort,likes merge sort,is based on divide-and-conquer paradigm;here is the three-step divide-and-conquer process for sorting a typical subarray A[p..r];
Divide:partition the array A into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q],which is,in turn,less than or equal to each element of A[q+1..r].compute the index q as part of this partitioning procedure.
Conquer:sort the two subarrays by recursive calls to quicksort.
combine:since the subarrays are sorted in place,no work is needed to combine them:the entire array A[p..r] is now sorted.

here,I just want to remind the solution of quicksort;
after this,there will be algorithm and source code for this method.

source code for heap sort

#include "iostream"
using namespace std;

#define SIZE 100000

void maxHeapIfy(int *A,int i,int lengthA)
{
int l,r,largest,tmp;
l=2*(i+1)-1;
r=2*(i+1);
if( l < lengthA && A[l] > A[i])
largest=l;
else
largest=i;
if( r < lengthA && A[r] > A[largest])
largest=r;
if( largest != i ) {
tmp=A[i];
A[i]=A[largest];
A[largest]=tmp;
maxHeapIfy(A,largest,lengthA);
}
}

void buildMaxHeap(int *A,int lengthA)
{
int i;
for ( i = (int)(lengthA/2);i>=0;i-- )
maxHeapIfy(A,i,lengthA);
for ( i = 0; i < lengthA; i++ ) {
}
}

void heapSort(int *A,int lengthA)
{
int i, tmp;
buildMaxHeap(A,lengthA);
for( i = lengthA-1; i > 0; i-- ) {
tmp = A[i];
A[i] = A[0];
A[0] = tmp;
maxHeapIfy(A,0,i);
}
}

int main(void)
{
freopen("org.txt","w",stdout);
int A[SIZE];
int i;
for ( i = 0; i < SIZE; i++ ) {
A[i] = rand()%SIZE;
cout << A[i] << endl;
}
heapSort(A,SIZE);
freopen("res.txt","w",stdout);
for ( i = 0; i < SIZE; i++ ) {
cout << A[i] << endl;;
}
return 0;
}

algorithms for heap-sort

here is the algorithms for heap-sort,which is another solution for the sorting,better than insertion-sort,equal to merge-sort.
there are several subroutines assisting heap-sort;
one is max-heapify:
procedure max-heapify(A,i,length_A) //to make subtree i to fit the properties of max-heap;
l=2*i; //left child;
r=2*i+1; //right child;
if(lA[i])
__largest=l;
else
__largest=i;
if(rA[largest])
__largest=r;
if(largest!=i) {
__tmp=A[i];
__A[i]=A[largest];
__A[largest]=tmp;
__max-heapify(A,largest,length_A);
}
end procedure;

one is build-max-heap;
procedure build-max-heap(A,length_A)
for(i=(int)(length_A/2);i>=0;i--)
__max-heapify(A,i,length_A);
end procedure;

with these two subroutines,we can define the algorithms for heapsort;
procedure heap-sort(A,length_A)
build-max-heap(A,length_A);
for(i=length_A-1;i>0;i--){
__tmp = A[i];
__A[1] = A[0];
__A[0] = tmp;
__max-heapify(A,i,length_A-1);
}
end procedure;

brain age

brain age is a game on nds;
it's a game to create a virtual village;
and Virtual Villagers depicts the lives of simple people who often need help even with the obvious;
They populate Virtual Villagers, a quirky, low-budget game from Last Day at Work that falls somewhere between the Sims and a pet simulator.

life-tree

I reach another node of the life-tree;
and,the question is:
how to estimate the profit of each subtree?
the algorithm is hard to be designed,since I can not have a try;
consequently,I need help;aha;yes,help.
aim to tackle this,I'm busy with sending and receiving letters these days;
but...darkness still on;
p.s.:what is the number of algorithms to estimate the value of a tree?
still now,details are still not explicit;
only several steps are confirmed:
one is enter-exam is given up;
another is what disciplines to review? discrete mathematics is important in glance;
buddies,a za a za fighting^_^

introduction to algorithms:problem 4-2

assume that it's 32 bits per integer;
we can compute an integer's value in O(32) time converting from binary to decimal;
so,including this added step,the total time we spend must be O(32n);
of course,the coefficient can be omitted;
consequently,we trivially get the result O(n);
that is all;

source code for fibonacci numbers

to confirm if the values are precise,I write this program to compare the results between two different methods.
one is fibonacciOriginalDefiniton(n) following the original definition using recurrece formulas;
another is fibonacciGoldenRatio(n) following the direct and easy way to compute the value directly;

#include "iostream"
#include "math.h"
using namespace std;
int fibonacciOriginalDefinition(int n)
{
__if ( n == 0 || n == 1 ) return n;
__return fibonacciOriginalDefinition(n-1)+fibonacciOriginalDefinition(n-2);
}

float fibonacciGoldenRatio(int n)
{
__int i;
__float x1,x2,y1,y2;
__x1 = y1 = (1+sqrt(5))/2;
__x2 = y2 = (1-sqrt(5))/2;
__for ( i = 0; i < n-1; i++ ) {
____x1 *= y1;
____x2 *= y2;
__}
__return (x1-x2)/sqrt(5);
}

int main(void)
{
__freopen("data.txt","r",stdin);
__freopen("res.txt","w",stdout);
__int n;
__while ( cin >> n ) {
____cout << fibonacciOriginalDefinition(n) << "\t" << fibonacciGoldenRatio(n) << endl;
__}
__return 0;
}

comparison:
sample input:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
sample output to comparison:
org________goldenRatio
0__________0
1__________1
1__________1
2__________2
3__________3
5__________5
8__________8
13_________13
21_________21
34_________34
55_________55
89_________89
144________144
233________233
377________377
610________610
987________987
1597_______1597
2584_______2584
4181_______4181
6765_______6765

from the sample output, we can easily find out they're not different,though,their data type one is integer one is float;
so,the problem is solved,that is,the advanced method works.

fibonacci numbers

the fibonacci numbers are defined by the following recurrence:
F[0]=0;
F[1]=1;
F[i]=F[i-1]+F[i-2]; for i >= 2;
this definition is known as before,but,there is another tricky way to compute fibonacci number F[i],which is nicer than it's original definiton;
this method is related to the golden ratio x and its conjugate !x,which are given by the following formula:
x = (1+5^(1/2))/2 = 1.61803;
!x = (1-5^(1/2))/2 = -0.61803;
with help of these two formulas, we can redefine the fibonacci number in a much more direct and useful way as the following formula:
F[i] = (x^i-!x^i)/5^(1/2);
of courese,it's not the precise value of fibonacci number,since it may be a real number but integer expected.but,it's useful still,since the exact result is the nearest integer of the real number computed by above formula.
after simple consideration,it's not easy to compute the value of x^i,since x itself is a complex expression to represent in computer.maybe it's useless.

what is modular arithmetic

for any integer a and any positive integer n,the value a mod n is the the remainder(or residue) of quotient a/n, that is:
a mod n = a - floor(a/n)*n;
but,we've met a problem when we manipulate scilab's function modular,where a or n may be negative.
we can find that we get different answers between modular and remainder, so the definition metioned above isn't precisely correct if without the restriction that n is positive integer.

roulette wheel problem

there is a general formula for arbitrary N interger;
w = floor(N/K)+1/2*k^2+5/2*k-3, k = floor(N^(1/3));

source code for divide-and-conquer

#include "iostream"
#include "malloc.h"

using namespace std;

#define SIZE 100000

void merge(int *A, int p, int q, int r)
{
__int i,j,k,n1,n2;
__int *L,*R;
__n1 = q-p+1;
__n2 = r-q;
__L = (int*)malloc(n1*sizeof(int));
__R = (int*)malloc(n2*sizeof(int));
__for ( i = 0,j = p; i < n1; i++,j++ )
____L[i] = A[j];
__for ( i = 0,j = q+1; i < n2; i++,j++ )
____R[i] = A[j];
__for ( i=0,j=0,k=p; i < n1 && j < n2; ) {
____if ( L[i] <= R[j] )
______A[k++] = L[i++];
____else
______A[k++] = R[j++];
__}
__if ( i != n1 && j == n2 ) {
____for ( ; i < n1; i++,k++ ) {
______A[k] = L[i];
____}
__}
__if ( i == n1 && j != n2 ) {
____for ( ; j < n2; j++,k++ ) {
______A[k] = R[j];
____}
__}
__free(L);
__free(R);
}

void mergeSort(int *A, int p, int r)
{
__int q;
__if ( p < r ) {
____q = (int)((p+r)/2);
____mergeSort(A,p,q);
____mergeSort(A,q+1,r);
____merge(A,p,q,r);
__}
}

int resource[SIZE];

int main( void )
{
__int i;
__freopen("src.txt","w",stdout);
__for ( i = 0; i < SIZE; i++ ) {
____resource[i] = rand()%10000;
____cout << resource[i] << endl;
__}
__mergeSort(resource,0,SIZE-1);
__freopen("res.txt","w",stdout);
__for ( i = 0; i < SIZE; i++ ) {
____cout << resource[i] << endl;
__}

__return 0;
}

introduction to algorithms:exercise 2.3-2

as request in this exercise, we won't use sentinels any more.
here we go, pseudocode followed;
merge(A,p,q,r)
__n1 = q-p+1; //note the trivial operation with the indices;
__n2 = r-q; //concern with how we value q;
__L = malloc(n1);//we just need the proper memory for we won't use sentinels any more;
__R = malloc(n2);
__for ( i = 0, j = 0, k = 0; i < n1 && j < n2; ) {
____if ( L[i] <= R[j] )
______A[k++] = L[i++];
____else
______A[k++] = R[j++];
__}
__if ( i == n1 && j != n2 ) {
____for ( ; j < n2; j++,k++ ) {
______A[k] = R[j];
____}
__}
__if ( i != n1 && j == n2 ) {
____for ( ; i < n1; i++,k++ ) {
______A[k] = L[i];
____}
__}
__free(L);
__free(R);
merge end;

that's all.

introduction to algorithms:exercise 2.3-1

here is merge-sort in concise:
merge-sort(A,p,r) //A array to sort,p and r are indices;
__if ( p < r ) then //here we use '_' instead of ' '(white space);
____q = floor((p+r)/2); //take the merge-point as floor of middle position;
____merge-sort(A,p,q); //be careful with the indices;
____merge-sort(A,q+1,r);
____merge(A,p,q,r);
merge-sort end;

now, we will use this algorithm to operate the array A=[3,41,52,26,38,57,9,49];
______________________A=[3,41,52,26,38,57,9,49]
_________________________________|__________________
_____________________|_____________________________|
______________[3,41,52,26]____________________[38,57,9,49]
_____________________|_______________________________|________________
____________|_____________|___________________|______________________|
_________[3,41]________[52,26]_____________[38,57]_________________[9,49]
___________|______________|___________________|______________________|____
______|_________|______|______|____________|______|_______________|______|
_____[3]_______[41]____[52]____[26]__________[38]___[57]_____________[9]____[49]

above is the divide-conquer tree,and the operation sequence in left recurrence is followed:
[3,41,52,26,38,57,9,49]
[3,41,26,52,38,57,9,49]
[3,26,41,52,38,57,9,49]
[3,41,52,26,38,57,9,49]
[3,41,52,26,38,57,9,49]
[3,41,52,26,9,38,49,57]
[3,9,26,38,41,49,52,57]

that is all of the solution.

divide-and-conquer

here is a approach named divide and conquer:
Divide the life into a number of sublifes;
Conquer the sublifes by solving them recursively.if the sublife sizes are small enough,however,just solve the sublifes in a straightforward manner.
Combine the solved sublifes into the original life.

exercise 2.2-2 in introduction to algorithms

writing these is mainly to improve my writing, not mere to finish exercise for these are trivial and solved.
pseudocode(selection sort):
input:array A[n];
output:array A'[n] with all elements sorted;
procedure:
n = length(A);
for ( i = 0; i < n-1; i++ ) { //indices start with zero.
__max = i;
__for ( j = i+1; j < n; j++ ) {
____if ( A[j] > A[max] ) max = j;
__}
__if ( max != i ) { //replacing the ith greatest element in correct position.
____tmp = A[i];
____A[i] = A[max];
____A[max] = tmp;
__}
}
procedure end;
pseudocode end;

in this algorithm, the loop invariant is A[0..i];
in each iteration, the subset A[0..i] is always sorted;
here is the mathematical induction:
basis:it's sorted prior to all iterations for there is only one element in this subset.
maintenance:assume at current iteration step, the value of i is k, due to the mathematical induction, we have, the subset A[0..k] is in sorted and for each position of m denote the mth greatest element.after current iteration, we will get the (k+1)th greatest element and replace it at the position of k+1.to the next iteratin, subset of A[0..(k+1)] is in sorted(this is trivial).
termination:after procedure, A[0..(n-2)] contains the previous n-1 greatest elements, so, the last one must be the least one.it's explicit that we get a sorted array at last.

the best-case: we need to do nothing for it's sorted.O(c),c constant.
the worst-case: it may be O(n^2).

that's all of the solution.

integer function: floors and ceilings

these two are fundamental notations, which are defined as follow(x arbitrary real number):
floor[x]=the greatest integer less than or equal to x;
ceiling[x]=the least integer greater than or equal to x;
there are several properties which accompany these two definition.
if x integer then floor[x]= ceiling[x];
if x isn't integer then ceiling[x]-floor[x]=1;
floor[-x]=-ceiling[x];
ceiling[-x]=-floor[x];
x-1<*floor[x]<=x<=ceiling[x]from the previous rule, we can have a set of extended rules;
floor[x]=n, iff n<=xceiling[x]=n, iff n-1floor[x+n]=floor[x]+n, if n integer;
etc...